  ## 14-Mar-2008

### Archimedes simplified

Filed under: math — jlm @ 12:15

In the third century BC, Archimedes calculated an amazing approximation to π, bettering the old value of 256/81 worked out by 17th century Egyptians.
How did he do it? He circumscribed and inscribed a hexagon around a circle, then bisected each hexagon’s central angles to make a dodecagon, then a 24-gon, 48-gon, and finally a 96-gon. The perimeters of the polygons bound π above and below, and each pair of perimeters is related to the ones before.
Consider a pair of polygons being bisected: If the radius AO = 1, then AB = tan α and AC = tan ½α.
If it has n sides, the outer perimeter P = 2n tan α and the new polygon has perimeter P’ = 4n tan ½α. The inner perimeter is p = 2n sin α, with the new polygon’s perimeter being p’ = 4n sin ½α.

Now, 1/P + 1/p = 1/(2n tan α) + 1/(2n sin α) = (sin α + tan α)/(2n sin α tan α) = (1 + sec α)/(2n tan α) = (cos α + 1)/(2n sin α) = (cos² ½α – sin² ½α + 1)/(4n sin ½α cos ½α) = (2 cos² ½α – 1 + 1)/(4n sin ½α cos ½α) = (1/2n) cot ½α = 2/P’
And, P’ p = (4n tan ½α)(2n sin α) = 16n² tan ½α sin ½α cos ½α = 16n² sin² ½α = p’²
So, we have easy ways to calculate successive perimeters from our basic hexagons, with p = 6, P = 4 √3, using only simple arithmetic and square roots.

n P p
6 6.928203 6
12 6.430781 6.211657
24 6.319320 6.265257
48 6.292172 6.278700
96 6.285429 6.282064

which puts 3.1427 > π > 3.1410.

Now, Archimedes didn’t have trigonometric functions to utilize in his calculations, so he calculated the perimeters using similar triangles, a much more complicated process. But it gives the same values. He also lacked decimals, so he worked with rationals instead, producing the bounds 3 1/7 > π > 3 10/71.

## 4-Mar-2008

### Song chart

Filed under: humor, math — jlm @ 20:18

I recently was amused by the “song chart” meme, so decided to give it a try. ## 30-Mar-2007

### Distance between points on a sphere

Filed under: math — jlm @ 15:22

If you try and find out how you compute the distance between points on a sphere, you’ll get a bunch of sites which offer to calculate it for you if you enter the coordinates. If you search harder, you can even get the formula. But no one seems to be offering a derivation. So here you go.

First, some preliminaries. The half angle formulas give us 2 sin² ½ψ = 1-cos ψ. (Easily derivable from cos 2α = cos² α – sin² α.) The straight-line distance (cutting through the inside of the sphere) between two points on a unit sphere with an angle ψ between them is 2 sin ½ψ. (Bisect the triangle formed by the two points and the center of the sphere.) Consider A and B to be our two points we want to get the distance between, with latitudes φA and φB, and longitudes which differ by Θ. We’ll operate mostly on the disk formed by the parallel through B. The point where it intersects the pole is D, and the projection of A onto it is C. Let EB be perpendicular to DC.

The radius of the parallel through A is cos φA = DC; the one through B is cos φB = DB. Angle CDB is Θ, so EB = rB sin Θ and ED = rB cos Θ.
EC = CD – ED = rA – rB cos Θ.
BC² = EC² – EB² = rA² – 2 rA rB cos Θ + rB² cos² Θ + rB² sin² Θ = rA² + rB² – 2 rA rB cos Θ.

AC = |sin φA – sin φB|.
AB² = BC² + AC² = rA² + rB² – 2 rA rB cos Θ + sin² φA + sin² φB – 2 sin φA sin φB
= 2 – 2 rA rB cos Θ – 2 sin φA sin φB.

If ψ is the angle AOB (which is also the along-surface distance between A and B), then
AB² = 4 sin² ½ψ = 2 – 2 cos ψ.
So, 1 – rA rB cos Θ – sin φA sin φB = 1 – cos ψ.
ψ = arccos(cos φA cos φB cos Θ + sin φA sin φB).

## 25-Jan-2006

### Combinatorics: Counting with replacement

Filed under: math — jlm @ 05:14

Everyone knows the number of ways you can choose k items out of n without replacement is nCk = n!/k!(n-k)!. Often forgotten is that the number of ways to choose k items from n with replacement is n+k-1Ck. I think this is because a) it doesn’t come up as much, and b) there’s a clear intuitition behind the first formula but not so the second. So, why is the value n+k-1Ck? Proving it with induction is a simple matter, but doesn’t shed much light.

Let’s look at it differently… We can number our items 1, 2, …, n and order the k chosen items accordingly, making a non-decreasing sequence. So the problem becomes counting the non-decreasing sequences a1a2 ≤ … ≤ ak. Turn each sequence into a bar graph, so that for n=7, k=4 the sequence [3,5,5,6] becomes We can make the graph into a path from (0,1) to (k,n) This path has n-1+k steps, n-1 vertical and k horizontal. Choosing one such path is choosing the k horizontal steps from the n+k-1 total, hence n+k-1Ck.

Another way to think about it is to consider the items chosen to be bins to fill with balls: Choosing at item becomes putting a ball in the bin, and the number of balls in a bin represents how many times that item was chosen. So the problem becomes count the number of ways you can put k identical balls in n bins. Start with bin 1. At each step you can put a ball into the current bin, or move to the next bin. You’ll place balls in k of the steps, and move bins in n-1 of them, so it’s a matter of choosing the k steps out of the k+n-1 total in which to place balls.

## 24-Sep-2005

### Spokes

Filed under: math — jlm @ 08:27

So, can spokes help hold our Orbital (see below post) together? After all, internal tension acts mostly transverse to the centrifugal force whereas a spoke would act mostly along it. How about attaching the spoke to its opposite point on the Orbital?

Well, centripetal acceleration at a distance r from the center we already worked out to be a = r·4π²/d². If the spoke has linear density σ, then the mass of a bit of spoke Δr long would be ΔM = σΔr and have weight Δw = aΔM = r·(4π²/d²)·σΔr. So the total weight of the spoke half would be w=∫dw=∫r·(4π²/d²)·σdr = (4π²/d²)·σ∫r dr = (4π²/d²)·σ·(r²/2) = (2π²/d²)·σr²   (integrating from 0 to the Orbital’s radius).

The tension on the spoke just from its own weight is that of both halves, or T = (4π²/d²)·σr². This gives a T/σ of (4π²/d²)·r² just for the spoke to be strong enough to support itself. With d = 86400 s and r = 2×109 m, we’d need a strength of 2×1010 m²/s², which is as much as we’d need for the Orbital to support itself with internal tension anyway! Tweaking values won’t help, as in both cases the equations work out to T/σ = a·r. I think this means that diametric spokes can only be less effective than a band at holding a spinning structure (of any size) together.

What if we add a hub? Then the tension on the spoke is halved, but we have the problem of holding the hub together. We can also vary the spoke thickness, because tension is not uniform over it: Near the Orbital, it’s only carrying the support load, but at the hub it has the load from its own weight as well. With constant specific material strength S = T(r)/σ(r) and support load s, and Orbital radius R, we get the integral equation T(r) = s + ∫rR dw = s + ∫rR r·(4π²/d²)·σ(r) dr, or σ(r)·S = s – ∫Rr r·(4π²/d²)·σ(r) dr.

This gives the differential equation σ'(r)·S = -r·(4π²/d²)·σ(r) with initial condition σ(R) = s/S. At this point, I had to go and dust off my old math books. In standard form, the diff. eq. is σ'(r)+(4π²/Sd²)·rσ(r) = 0. This has solution σ(r) = (s/S)·exp(-A(r)) where A(r) = ∫Rr(4π²/Sd²)·r dr = (4π²/Sd²) ∫Rr r dr = (2π²/Sd²)·(r² – R²).

This simplifies to σ(r) = (s/S)·exp((2π²/Sd²)·(R²-r²)). At the hub r=0, so we have σ(0) = (s/S)·exp(2π²R²/Sd²). So the tension on the hub is T(0) = s·exp(2π²R²/Sd²). Kevlar has a S = 2500 MPa/(g/cm³) = 2.5×106 m²/s². So, for each pound the Orbital supports, this would place exp(4000) = 101800 lb of tension on the hub. That’s farther beyond scrith’s capabilities than scrith is beyond ours. How about that miracle nanotube cable? S = 37 GPa/(g/cm³) = 3.7×107 m²/s², so T(0)/s = exp(286) = 10124. Trying to hold it together with a hub makes the problem much harder, not easier.

### How big is an Orbital?

Filed under: math — jlm @ 06:38

In science fiction, it’s fairly common to use centrifugal force to simulate gravity in space. This is usually used for ships or space stations, but Larry Niven took it to an extreme with his famous Ringworld, which circles a star at orbital distance and spins enough faster than orbital speed to provide Earth-equivalent “gravity” against its inside. Iain Banks thought this was too extreme even for fantastically-powerful civilizations, so toned it down a bit by having a ring that revolves once per day and provides 1 g from its spin. (Niven’s Ringworld needed “shadow squares” between the ring and the star to provide night.) Banks calls these “Orbitals”, places them in planetary orbits, and implies that they’re of planetary dimensions. But, how big is an Orbital really?

Well, we want a period of about an Earth day (d), and centripetal acceleration of about an Earth gravity (g). Consider a point x on the Orbital at angle θ. x = r î cos θ + r ĵ sin θ. To provide an Earth day, the Orbital revolves through 2π radians in 1 d, so dθ/dt = 2π/d. Acceleration is the second derivative of position, so a=d²x/dt²=(-r î cos θ-r ĵ sin θ)(4π²/d²). We want ∥a∥ to be 1 g, so ∥a∥ = r·(4π²/d²) = g, or r = g·(d²/4π²). To match Earth, g should be about 9.8 m/s² and d about 86400 s, which puts r at about 1.9×109 m.

That’s huge! (Though not Ringworld huge.) The radius of the Earth is only 6×106 m, and Jupiter is “only” 7×107. An Orbital is 300 times as wide as the Earth. (Though potentially much shorter.) But still not orbital distances– it’s only 1% of the size of Earth’s orbit.

Now, how strong does an Orbital have to be? Well, let’s consider a small section of the Orbital subtending an angle Δθ. This will have length Δl = r·Δθ. If the Orbital has a linear density σ, this section will have mass ΔM = σ·Δl and weight Δw = g·ΔM = gσr Δθ. If the tension is T, the internal force at the edge of the section will be T î sin ½Δθ + T ĵ cos ½Δθ. The i component of this force holds “up” half of the section’s weight, the other edge providing the other half. Using the small angle approximation for sine, we get ½Δw = T·½Δθ, or T = gσr. So the strength we need is T/σ = gr = 2×1010 m²/s². If the Orbital’s cross-sectional area is τ, then the internal tensile pressure is P=T/τ so T = P·τ. If its material density is δ, then σ=δ·τ, so T/σ = P·τ / δ·τ = P/δ, which tells us that the 2×1010 m²/s² is the ratio of tensile strength to density we need. This is 10000 times as strong as existing high-tension materials like Kevlar (stuff like steel and titanium and diamond isn’t particularly strong in the tension department) and still 600 times as strong as the supposed carbon nanotubes that they say may make a space elevator possible. And this is just enough for the structure to not tear itself apart by its own spin, much less support anything you want to have on the Orbital. I thought solar tides might be an issue, being about 9×1020 N for each Earth mass of the Orbital, but the spin tension blows that away at 6×1025 N per Earth mass. So, sadly, even through this is orders of magnitude more feasible than the Ringworld, it’s still never going to work.

## 20-Aug-2005

### Information theory applied to word puzzles

Filed under: math — jlm @ 19:12

You know those coin weighing puzzles? For the most part they can all be solved easily by using elementary information theory: At each step just make the weighing which maximizes your expected information gain. But what about word puzzles, can the math help us here?

Well, lately I’ve been playing this word game sometimes called “Jotto”. The idea is you pick a six letter word, and the person you’re playing against also picks a word. Then you each try to guess the other’s word. You do this by selecting a word, then they tell you how many letters match their secret word.

For example, if my word is “spaces” and you guess “guests”, I’d tell you that 1 letter was right. Then I’d get a chance to guess your word.

But what’s a good strategy? Well, I often try “throw out a lot of vowels” then once I think I have those pegged I play hot-and-cold with the rest of the word. But more ideally, you’d pick a word which divides up the word space as evenly as possible so you’ll get to small sets of possibilities quickly. Or put another way, you want to maximize the amount of information you acquire at each guess. Now, estimating information content is hard to do (how many words are one-letter matches of “spaces” as compared to zero-letter matches? Now take the logarithm…) but it’s easy enough for a computer to calculate, so I built a “Jotto Bot” which does just that. It plays pretty well — sometimes amazingly, but it doesn’t learn, so once you’ve found a word in the information boondocks, it’ll always do poorly on it… for now.

You can play with it here. Nicest is “you vs. computer”, but “computer guesses your word” shows you what’s going on behind the scenes.