February 2014 - mathfun@mailman.xmission.com

[math-fun] convergence speed of continued fractions
by Bill Gosper 24 Feb '14

24 Feb '14

WDS> Usually you can find the answer by viewing CFs as infinite product of 2x2 matrices, and considering the eigenvalues of those matrices in the limit.<WDS Warren, before wading into your generous followup, I have a stupid question: Scaling a matrix scales the eigenvalues, but doesn't change the value of the C.F. What gives? --rwg

1 0

[math-fun] meteors hit moon
by Warren D Smith 24 Feb '14

24 Feb '14

Since 2005, NASA's moon impact-monitoring program has observed more than 300 meteorite strikes on the lunar surface as visible flashes. But I presume they can only detect (in this way) flashes on the part of the moon facing the Earth and not facing the sun. The largest was 11 Sept 2013 and dug a crater about 40 meters in diameter. It was thought to be due to a 400 kg rock traveling at 17 km/sec and the flash would have been easily visible with the naked eye (if you were looking and it was night). Allegedly: Rock diameter 0.6 to 1.4 meters; energy 15 tons TNT. Obviously, it was a plot by Al Qaida. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] continued fractions for pi; analysis of convergence speed
by Warren D Smith 24 Feb '14

24 Feb '14

The general continued fraction a0 + b1/(a1+) b2/(a2+) b3/(a3+...) is associated with the product of matrices [an bn] [ 1 0] whose eigenvalues are [a + sqrt(a*a+4*b)]/2 and -2*b / [a + sqrt(a*a+4*b)] and in most cases where an and bn depend "smoothly enough" on n these eigenvalues will govern convergence speed. So for example, the continued fractions I mentioned in a previous post were F1(z) = (sqrt(pi)/2)*erfc(z) F2(z) = (sqrt(pi)/2)*erf(z) so that for any z>0 we have sqrt(pi)/2 = F1(z) + F2(z) and F1(z) = exp(-z^2) * 1/(2z+) 2/(2z+) 4/(2z+) 6/(2z+) 8/(2z+...) F2(z) = exp(-z^2) * z/(1-x+) (2x/(3-x+)) (4x/(5-2x+)) (6x/(7-2x+)) (8x/((9-2x+...) where x=2*z*z. The F1 continued fraction's convergence then is governed by the eigenvalues of [2z 2n] [ 1 0] or more precisely by the |ratio| of the eigenvalues, when n-->infinity. This ratio is e1/e2 where e1 = z + sqrt(z*z+2*n) e2 = -2*n / (z+sqrt(z*+2*n)) ratio = -1 - sqrt(2*z/n) - z*z/n + O(n^(-3/2)) and hence the convergence ultimately is slow, specifically after n decks of the F1 continued fraction we expect error of order exp(-const*sqrt(n)) i.e. order sqrt(n) correct decimal places. This is "slower than geometric" albeit still fast enough to get polynomial time. The F2 continued fraction's convergence similarly is governed by the eigenvalues of [2*n+1-2*x 2*n*x] [1 0 ] yielding ratio = -2*n/x - 2*(1-x)/x - O(n^(-1)) which predicts ultimately very rapid, factorial style, convergence, namely n decks ought to yield error of order (x/2)^n / n!. Now returning for a more careful look at the slow continued fraction F1, its eigenvalue ratio is exactly - (z + sqrt(z*z+2*n)) / (2*n) which for large n ultimately sucks, i.e. approaches -1; but if z is large then you can get fast convergence for quite a while, only slowing down once n reaches order z. So if we only use about z terms of the F1 continued fraction with z large, then we expect error of order 1/z! very roughly. Remember, for the purpose of computing pi, we are free to choose any z we like in an effort to get faster speed. Choosing large z makes the F1 fraction converge faster at least initially. Unfortunately large z makes the F2 fraction converge slower! You need n of order x or more before the ultimate fast convergence sets in where x=2*z*z. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] convergence speed of continued fractions
by Warren D Smith 23 Feb '14

23 Feb '14

Usually you can find the answer by viewing CFs as infinite product of 2x2 matrices, and considering the eigenvalues of those matrices in the limit.

1 0

[math-fun] continued fractions yielding pi
by Bill Gosper 21 Feb '14

21 Feb '14

[image: Add contact] RCS> I think F1 below (for erfc) has crummy convergence. The numerators in the cf terms are increasing linearly, while the denominators are constant. The recurrence for successive convergents' numerators & denominators will overemphasize the older term over the newer term, which retards the decay of the oscillation around the limit. Gosper can likely say more. Rich I had an Mma function for CF convergence, but I forgot how it works and broke it.-{ But I seem to recall linerar/constant converges "T3" (see below). WDS> On 2/21/14, Warren D Smith <warren.wds(a)gmail.com> wrote: Well, two natural questions arise: Q1. is there any known series expansion for pi (or something closely related) which, like the usual series for e, converges factorially rather than merely geometrically? If said series arose from an analytic function's Taylor series, then this would necessarily be an "entire" function, ruling out stuff like arcsine, arctan, elliptic functions, elliptic integrals, log, and polylogs, but permitting, e.g, the reciprocal of the Gamma function, and erf and erfc, and new functions. --various continued fractions for erf and erfc are available here:http://functions.wolfram.com/GammaBetaErf/Erfc/10/01/http://functions.… These would allow computing pi using a sum of two continued fraction evaluations to compute integral_0^infinity exp(-t^2) dt = sqrt(pi)/2. For example, let F1(z) = (sqrt(pi)/2)*erfc(z) F2(z) = (sqrt(pi)/2)*erf(z) so that for any z>0 we have sqrt(pi)/2 = F1(z) + F2(z) and could choose the value of z to maximize convergence speed or whatever. Then we have such continued fractions as F1(z) = exp(-z^2) * 1/(2z+) 2/(2z+) 4/(2z+) 6/(2z+) 8/(2z+...) F2(z) = exp(-z^2) * z/(1-x+) (2x/(3-x+)) (4x/(5-2x+)) (6x/(7-2x+)) (8x/((9-2x+...) where x=2*z*z. Similarly one could compute pi in a different way via a sum of continued fractions by computing certain gamma function values as a sum of two incomplete gamma functions to get the whole Euler-gamma-integral. <WDS See 2010 mail near end. In the 70s, Rich, Gene, and I dreamed that we could show the algebraic independence of π and e by proving the empirical "fact" that e was T2 and π was T3, where Tk means time complexity n (log n)^k loglog n for n digits. Multiplication, and, more generally, algebraic functions are T1. Confluent hypergeometric series are T2, and (p+1)Fp are T3. Then Gene ruined everything by finding the T2 AGM method for π. --rwg Subj: Re: [math-fun] sqrt(pi) Date: 2013-03-24 02:10 2013-03-24 02:10 The slower converging "half" of this formula is the [w,oo) integral, w^z/(E^w*Gamma[z, w]) == MProd[MatrixForm[{{-1 + 2*n + w - z, n*(-n + z)}, {1, 0}}], {n, 1, Infinity}] where MProd is matrix product, and the matrices a1 b1 . a2 b2 . . . 1 0 1 0 compute the continued fraction a1+b1/(a2+b2/(... . Unfortunately, this K quadratic/linear is not a special case of the path invariant system at the bottom of p13 of http://www.tweedledum.com/rwg/stanfordn3.pdf, so I couldn't accelerate it. Finally, I found the {n,j} pair n: {{a + j + 2 n, -n (j + n)}, {1, 0}}, j: {{-a - n, (-1 + n) (j + n)}, {-1, j + n}} but the first few contours proved disappointing, so I sought a third dimension k. Usually this would be no easier (nor likelier to happen) than dredging up the original j matrix, but I found a cheap trick which seems too good to be true (and probably is, in most cases): The system is free of k, so the k matrix is obviously {1,0;0,1} : In[330]:= updatemat[k, IdentityMatrix[2]] Out[330]= {{n, {{a + j + 2 n, -n (j + n)}, {1, 0}}}, {k, {{1, 0}, {0, 1}}}, {j, {{-a - n, (-1 + n) (j + n)}, {-1, j + n}}}} Then In[331]:= recoord[n -> n + k] Out[331]= {{n, {{a + j + 2 (k + n), -(k + n) (j + k + n)}, {1, 0}}}, {k, {{a + j + 2 (k + n), -(k + n) (j + k + n)}, {1, 0}}}, {j, {{-a - k - n, (-1 + k + n) (j + k + n)}, {-1, j + k + n}}}} making the k matrix the same as the n matrix. Then In[332]:= recoord[j -> j - k] Out[332]= {{n, {{a + j + k + 2 n, -(j + n) (k + n)}, {1, 0}}}, {k, {{-((a + j + n)/(1 + a)), ((-1 + j + n) (k + n))/(1 + a)}, {-(1/(1 + a)), (k + n)/(1 + a)}}}, {j, {{-a - k - n, (j + n) (-1 + k + n)}, {-1, j + n}}}} Now the n matrix is symmetric in j and k, so k is highly legitimate! But why aren't the j and k matrices analogous? They are, but all the elements of k are divided by 1+a. Scaling the whole matrix (even by a function of k) is irrelevant to path invariance, so In[333]:= updatemat[k, (1 + a)*mats[k]] Out[333]= {{n, {{a + j + k + 2 n, -(j + n) (k + n)}, {1, 0}}}, {k, {{-a - j - n, (-1 + j + n) (k + n)}, {-1, k + n}}}, {j, {{-a - k - n, (j + n) (-1 + k + n)}, {-1, j + n}}}} In[334]:= picheck[%] Out[334]= True (Path invariance check.) This matrix functions package is from Corey Ziegler Hunts. Early results from these {j,k,n} matrices are inconclusive. I'm hitting a lot of numerical instability, which seems inherent: When a CF matrix a b c d converges, a/c approaches b/d. And thus the matrix approaches singularity. --rwg On Tue, Aug 3, 2010 at 4:09 PM, Bill Gosper <billgosper(a)gmail.com> wrote: Pairwise combining the terms of A&S 6.5.31 (upper Gamma CF), then adding last week's lower gamma CF: In[185]:= Equal[Gamma[ z], ((y^z*((1/(cfk[n*(z - n), -z + y + 2*n + 1, List[n, Infinity]] - z + y + 1)) + (1/(z + cfk[n*y, z - y + n, List[n, Infinity]] - y))))/(E^y))] z 1 Gamma[z] == (y (------------------------------------------- + -y + z + cfk[n y, n - y + z, {n, Infinity}] 1 y -----------------------------------------------------------)) / E 1 + y - z + cfk[n (-n + z), 1 + 2 n + y - z, {n, Infinity}] where cfk:=ContinuedFractionK and y>0 can be chosen to optimize convergence. Specializing, In[186]:= % /. z -> 1/2 /. y -> 1 Out[186]= 1 Sqrt[Pi] == (-------------------------------------- + 1 1 -(-) + cfk[n, -(-) + n, {n, Infinity}] 2 2 1 ------------------------------------------) / E 3 1 3 - + cfk[(- - n) n, - + 2 n, {n, Infinity}] 2 2 2 In[192]:= N[List @@ %186 /. cfk[num_, den_, _] :> ContinuedFractionK[num, den, {n, 9}]] Out[192]= {1.77245, 1.77244} This is the first non-asymptotic sum or CF I've seen for sqrt(pi). But the sum behind the lowergamma cf has been there all along, so I must not have been paying attention. --rwg

1 0

[math-fun] continued fractions yielding pi
by Warren D Smith 21 Feb '14

21 Feb '14

On 2/21/14, Warren D Smith <warren.wds(a)gmail.com> wrote: > Well, two natural questions arise: > > Q1. is there any known series expansion for pi (or something closely > related) which, > like the usual series for e, converges factorially rather than merely > geometrically? > > If said series arose from an analytic function's Taylor series, > then this would necessarily be an "entire" function, ruling out stuff like > arcsine, arctan, elliptic functions, elliptic integrals, log, and polylogs, > but permitting, e.g, the reciprocal of the > Gamma function, and erf and erfc, and new functions. --various continued fractions for erf and erfc are available here: http://functions.wolfram.com/GammaBetaErf/Erfc/10/01/ http://functions.wolfram.com/GammaBetaErf/Erf/10/01/ These would allow computing pi using a sum of two continued fraction evaluations to compute integral_0^infinity exp(-t^2) dt = sqrt(pi)/2. For example, let F1(z) = (sqrt(pi)/2)*erfc(z) F2(z) = (sqrt(pi)/2)*erf(z) so that for any z>0 we have sqrt(pi)/2 = F1(z) + F2(z) and could choose the value of z to maximize convergence speed or whatever. Then we have such continued fractions as F1(z) = exp(-z^2) * 1/(2z+) 2/(2z+) 4/(2z+) 6/(2z+) 8/(2z+...) F2(z) = exp(-z^2) * z/(1-x+) (2x/(3-x+)) (4x/(5-2x+)) (6x/(7-2x+)) (8x/((9-2x+...) where x=2*z*z. Similarly one could compute pi in a different way via a sum of continued fractions by computing certain gamma function values as a sum of two incomplete gamma functions to get the whole Euler-gamma-integral.

2 1

[math-fun] neat wind map of the earth
by Joerg Arndt 21 Feb '14

21 Feb '14

Clicky: http://earth.nullschool.net/ Click lower left "earth" to change settings and to hide settings click it again (now being on to of the panel; a case of "mystery meat navigation") P.S.: Got it from ElReg: http://www.theregister.co.uk/2013/12/19/earth_wind_maps/ Also (about "mystery meat navigation") http://en.wikipedia.org/wiki/Mystery_meat_navigation

3 2

[math-fun] pi / factorial base (versus e)
by Warren D Smith 21 Feb '14

21 Feb '14

Well, two natural questions arise: Q1. is there any known series expansion for pi (or something closely related) which, like the usual series for e, converges factorially rather than merely geometrically? If said series arose from an analytic function's Taylor series, then this would necessarily be an "entire" function, ruling out stuff like arcsine, arctan, elliptic functions, elliptic integrals, log, and polylogs, but permitting, e.g, the reciprocal of the Gamma function, and erf and erfc, and new functions. Q2. Of course pi could be defined via sin(pi)=0, or cos(pi/2)=0, or... and such equations are somewhat easier to work with if you are working with factorial-base numbers.

1 0

Re: [math-fun] Possibility puzzle
by Bill Gosper 21 Feb '14

21 Feb '14

-------- Original Message -------- Subject: Re: [math-fun] Possibility puzzle Date: 2014-02-16 10:43 From: "Adam P. Goucher" <apgoucher(a)gmx.com> To: "math-fun" <math-fun(a)mailman.xmission.com> > Bill Gosper wrote: > > Apparently, possibility is the intersection of probability with Boolean > algebra. A certain > 4th grade teacher decided to enrich Saxon Math with a few days of What's Saxon Math? Does it involve the Angle bisector theorem? > reduced to > bluffing with ambigrams: gosper.org/logic.png I can remember an anecdote that in some Cambridge lecture on propositional logic, the lecturer wrote a few axioms such as this: (S ^ H) v N <==> (S v N) ^ (H v N) And then rotated the blackboard through 180° to give the remaining axioms. By the way, has anyone else realised that Soddy's hexlet generalises by adding extra layers of spheres? http://cp4space.wordpress.com/2014/02/15/soddys-hexlet/ Sincerely, Adam P. Goucher -------------- Frightful generalizations follow from http://mathworld.wolfram.com/BowlofIntegers.html . Related: http://www.tweedledum.com/rwg/Sodddy.htm The homeschoolers I know refer to Saxon Math as Drill and Kill, which has apparently switched from swords to pikes. --rwg

10 17

Re: [math-fun] Julian's dodecahedron
by Bill Gosper 19 Feb '14

19 Feb '14

On 2013-09-02 15:15, Adam P. Goucher wrote: > The legendary Bill Gosper wrote: I'd rather be young. > >> is made by replacing ten of the regular pentagons of a dodecahedron with >> concave equilateral pentagons, preserving the topology: >> http://gosper.org/dodohedron.png >> ( !#%&*@! was deleted again. Apologies to any of you who looked for it.) >> >> http://en.wikipedia.org/wiki/Dodecahedron glaringly omits it: > > Even worse, the Wikipedia article omits the much more well-known > _endo-dodecahedron_ (the Symmetries of Things, page 328), which has > concave regular pentagonal faces and is *face-transitive*. And it's equilateral! > Its symmetry group is pyritohedral (3*2), and it is defined as: > > "The spaces left over by positioning dodecahedra of maximum size in > the natural orientation, centred on the points of the FCC lattice" > > The faces are different from the concave pentagons of the > tympanohedron, having internal angles of {7pi/5, pi/5, 3pi/5, 3pi/5, > pi/5} in cyclic order. > > > Sincerely, > > > Adam P. Goucher > > http://cp4space.wordpress.com Actually the concave figure in http://en.wikipedia.org/wiki/Pyritohedron is probably your endododecahedron, but they don't say. It would appear in their stupid throbbing animation, if the author wasn't so hung up on convexiity. Here's my stupid throbbing animation: ListAnimate[ Table[Graphics3D[ Polygon[Join[#, -#] &@ Join[#, Map[RotateLeft, #, {2}], Map[RotateRight, #, {2}]] &@{{{-(1/2) + 2 z^2, -(1/2) + z, 0}, {-(1/2), -(1/2), -(1/2)}, {0, -(1/2) + 2 z^2, -(1/2) + z}, {1/2, -(1/2), -(1/2)}, {1/2 - 2 z^2, -(1/2) + z, 0}}, {{1/2 - 2 z^2, -(1/2) + z, 0}, {1/2, -(1/2), 1/ 2}, {0, -(1/2) + 2 z^2, 1/2 - z}, {-(1/2), -(1/2), 1/ 2}, {-(1/2) + 2 z^2, -(1/2) + z, 0}}}]] /. z -> (5*Sin[t] + Sin[5*t])/12, {t, -\[Pi]/2, \[Pi]/2, \[Pi]/30}], AnimationRunning -> True, AnimationDirection -> ForwardBackward] The mgif: gosper.org/dodex.gif --rwg BTW, yesterday Neil predictively sketched the key frames of this on a small piece of paper while riding in a car in the Santa Cruz Mountains.

4 8