December 2011 - mathfun@mailman.xmission.com

[math-fun] BBP functions (Bailey-Borwein-Plouffe)
by Warren Smith 22 Dec '11

22 Dec '11

As you probably know, Plouffe invented a famous formula for pi which basically enables computing its Nth decimal place (but in radix 16 not 10) without computing previous decimals(!), in about O(N) steps and O(logN) memory. Other versions appeared collectively called BBP formulas. http://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/bbp-formulas.pdf Constants now known to be in BBP class include pi, ln2, ln3, atan2, atan(4/5), pi*sqrt(2), pi*sqrt(3), sqrt(2)*ln(1+sqrt(2)), pi^2, (ln2)^2, pi*ln(2), CatalanConstant, zeta(3), zeta(5). Anyhow, this has probably been thought of before, but I did not see it in those sources... so I'd like to ask: WHICH FUNCTIONS F(x) have Maclaurin series which yield BBP formulae as their special cases when x=1/radix? In MAPLE notation, define (where A>=0 and B>0 and C>0 and k>=0 and D,E,F... are integers and x is complex or real) F0 := (A,B,C,x) -> x^A / (1-x^B)^C; F1 := (A,B,C,D,x) -> int( x^D * F0(A,B,C,x), x ); F2 := (A,B,C,D,E,x) -> int( x^E * F1(A,B,C,D,x), x ); F3 := (A,B,C,D,E,F,x) -> int( x^F * F2(A,B,C,D,E,x), x ); etc. [You must not take D,E,F... too negative or the integrals will not converge near 0.] THEOREM: All rational-function linear combinations of the Fk(A,B,C,..., x) are BBP class (where the rational functions of x have integer coefficients). For example, (x+3)/(3*x) * F2(2,5,1,0,0,x) + (11/7) * F1(3,4,2,0,x) and F2(3,4,1,-1,-1,x) are in BBP class, and if you ask MAPLE what these are, it will do the integrals and spit out some enormous closed form formula for you. I think this set includes all the formulas in the Bailey compendium above (though I'm not sure of that). But despite its enormity, the set I have described is not the full BBP class. For example Goofy(x) = sum( x^n / (n^2+1), n=0..infinity) = 3F2([1, i, -i], [1 + i, 1 - i], x) is in BBP class but not in my set. A larger set, which comes a lot closer to being the whole BBP class, is as follows. Redefine F0 to be the class of rational functions of x (with integer coefficients of course). Now for k>0 redefine Fk to be the class of rational-fn linear combinations of functions in F[k-1] and integrals(dx) of rational-fn linear combinations of functions from class F[k-1]. Disallow members including integrals which are nonanalytic at x=0. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] "Unit intervals" with complex bases
by Joerg Arndt 22 Dec '11

22 Dec '11

After wasting some time rendering the "unit intervals" for complex bases I put a few of the nicer images online. First see http://jjj.de/tmp-rd/00readme.txt ( http://jjj.de/tmp-rd/ gives a list of all files ) Then I'd recommend to peek at http://jjj.de/tmp-rd/rd-naf-m1p1-d0.png which is a pretty variation (using non-adjacent forms (NAF)) of the well known twindragon http://jjj.de/tmp-rd/rd-m1pi-twindragon-d0.png terdragons in packs of 3 (raixd i*sqrt(3)): http://jjj.de/tmp-rd/rd-p0ps3-terdragon-d0.png A NAF gives them "isolated": http://jjj.de/tmp-rd/rd-naf-w17.4p0ps2-terdragon-d0.png Gospers island comes with radix 1/2*(5+i*sqrt(3)) http://jjj.de/tmp-rd/rd-hp5ps3-gosper-d0.png Kindly do not repost the URL, I'd dislike massive amounts of downloads (at the moment). cheers, jj

1 0

Re: [math-fun] mental factoring
by Bill Gosper 21 Dec '11

21 Dec '11

DanA>What got me started on this was trying to factor 2257, and after finding no small prime factors, noticing that 2257 = 37 + 2220 = 37 + 20*111 = 37 + 20*3*37 = 37*61. But that was just a lucky break, and I was wondering if there are better ways than routinely checking each prime in order (or relying on luck). --Dan I did 2257 -> 257-2 ->255 *2 ->51, so 7,11,13,fail 257-1 so 23,29 fail (2001=3 23 29) 257+2 -> 259 = 222-37, 37 win (111=3*37). Had that failed 257-3*2 ->251, so 17,59 fail 257-7*2->243, so 19,53 fail, 2*2257 = 4514 -> 514+1 *2 ->103, so 31,43 fail (3999 = 3*31*43) ... I.e., memorize a bunch of multiples of the small primes near multiples of 1000. My favorite factorization was of a friend's phone #, 3367. Hmm, 1/3;2/3. Muliply by 3: 10101. Multiply by 11: 111111 = 1001*111, so 7 11 13 3 37/3/11 But all this is lame vs JHC's and Rich's methods. Rich sketched his on Date: Tue, 4 Oct 2005 18:47:46 -0700 . Conway sent many methods, e.g. >From conway(a)math.Princeton.EDU Wed Feb 7 12:24:59 1996 Some time ago I was boasting about my mental factorization algorithm, but when rwg asked "how fast?" I could only reply "pretty fast", because I hadn't done any systematic timing, and of course the times taken vary dramatically with the form of the number. I forgot to display my prowess to rwg when I met him at the Gathering for Gardner, too, dammit. However, I now have some results. I still suffer greatly from insomnia, and have been playing "The Nsomniac's Game". This is played in the small hours by an insomniac with a luminous digital clock by the bedside, which shows a 3-digit number n. [For example, at 3:49 am, n would be 349.] Then the "current number" in the Nsomniac's game is | 1000N + n |. (I allow negative N.) The game is to factorize the successive current numbers while they remain current, except that the first one need only be factorized before the second one ceases to be current (because your first glance at the clock might be only a few seconds before it changes). I can play up to the 15somniac's game quite well, but am particularly comfortable with the 10somniac's one. I think it was last Saturday night (of course I mean Sunday morning) that I played 10somniac for about 4 consecutive hours. Usually I was factorizing numbers quite a few minutes ahead of the current one, so that every now and then I could take 5 minutes off; but since sleep still didn't come I was always able to take up where I left off. The only failure to meet the time limit was a technical one. I did find the correct factor 79 of 10349 in time (i.e., before 3:50 am), but then couldn't get it to divide this number correctly, so presumed I must have slipped, and redid the algorithm, finding 79 again, but the clock had changed to 350 by the time I'd sorted this out. Any factorisation gives a check, but it's quite possible that I wrongly declared some numbers to be prime. I actually caught myself just about to do this at 4:43, when I'd found "3 times 3481" and had apparently shown the second factor prime, when I recalled that in fact it's 59^2. I had the feeling that my 10somniac times are usually less than 30 seconds per number. I've reorganized the algorithm slightly, and the version I use now tests primes up to 100, which is all that's needed for 10somniac, since the only composites < 11000 with no factor < 100 are easily remembered: 10201, 10403, 10609, 10807. For use up to 15somniac, I supplement the basic algorithm by an ad hoc way of finding the next few primes, using 101.109 = 11009, 103.107 = 11021, 97.113 = 11000 - 39. (Namely I subtract 11000, then subtract 9, then subtract 12, then add 60, at each stage checking the appropriate primes. This allows me to miss the 97 test from the main algorithm, and carries me up to 127^2 = 16129.) Well, you're not all interested in my sleeping problems. During a few of my real waking hours, I've been working on a speeded-up mental way of finding large factors by differences of squares, in which a few of you MAY be interested; I'll report on it soon. [My basic algorithm will test numbers well beyond 10^4; certainly up to 10^5, for factors below 100, and my ground plan is to use the new method for factors beyond 100. However, factorizers who are slightly less keen could use it over other ranges.] John Conway But I haven't been able to find his most impressive one, which turned out to be only part of an even superior method published by a Harvard(?) professor in the 1920s(?) --rwg

1 1

Re: [math-fun] Chess game in current Sherlock Holmes movie
by Henry Baker 21 Dec '11

21 Dec '11

Adam Raoof's rating is 2127 !! I'm impressed. Perhaps we should simply ask him; I just cc'd him on this email. At 01:13 PM 12/21/2011, Paul Reiners wrote: >I haven't seen the movie, but I started a discussion here: > >http://www.chess.com/forum/view/general/sherlock-holmes-a-game-of-shadows > >One person said: > >the credits (on IMDB <http://www.imdb.com/name/nm4668958/>) have Adam >Raoof<http://ratings.fide.com/card.phtml?event=405230>(I assume that >is the same guy) listed a technical adviser for chess > >If the director didn't change things up to make it more interesting then I >would guess it was a real game. > >On Wed, Dec 21, 2011 at 11:53 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> I saw this movie yesterday. >> >> http://en.wikipedia.org/wiki/Sherlock_Holmes:_A_Game_of_Shadows >> >> Q: Is the chess game in the movie real? The characters call out their >> moves in usual notation, but the chess board isn't shown. >> >> For those of you chess nuts who can do chess in your heads, would this >> be a real game? >> >> I would imagine that after spending $125 million in making this movie, >> someone must have hired a chess person for a few hundred dollars to >> make the game real.

2 1

[math-fun] Chess game in current Sherlock Holmes movie
by Henry Baker 21 Dec '11

21 Dec '11

I saw this movie yesterday. http://en.wikipedia.org/wiki/Sherlock_Holmes:_A_Game_of_Shadows Q: Is the chess game in the movie real? The characters call out their moves in usual notation, but the chess board isn't shown. For those of you chess nuts who can do chess in your heads, would this be a real game? I would imagine that after spending $125 million in making this movie, someone must have hired a chess person for a few hundred dollars to make the game real.

3 3

[math-fun] Diophantine eq. a^4+b^4=d*c^2 and specialness of d=17
by Warren Smith 21 Dec '11

21 Dec '11

Various people & I made some progress, but then it turned out the full solution of this problem was already known. Theorem: a^4+b^4=d*c^2 for d fixed either has an infinity of nonzero solutions (a,b,c) or none (A.Desboves & WDS). Theorem: When d=1, none (P.de Fermat 1640 or so, see T.Nagell: Intro to number theory Wiley 1951, pp.227-229; L.J.Mordell: Diophantine equations, Academic Press 1969 chapter 4) Theorem: when d=2 the only solutions (a,b,c) are the trivial ones with a=b (Euler 1738, see Mordell: Diophantine Equations, Academic Press 1969 chapter 4 page 18.) Theorem: Wlog we can take d to be squarefree (Phil Carmody). Theorem: Then the prime factors of d all must be of the form 8*k+1 or 2 only (Jaroslaw Wroblewski). Actually both Carmody & Wronblewki's theorems were given on p110 of H.C.Pocklington: Some diophantine impossibilities, Proc Cambridge Philos Soc 17 (1913) 108-121. Corollary of JW's theorem: every allowed squarefree d is a sum of two squares [WDS using Euler 1738]. 16-Theorem: Also d must equal 0,1,2,4,8,9, or 12 (mod 16) [WDS]. 81-theorem: Also (d mod 81) must be in {0,1,2,4,5,8,9,11,13,16,17,18,19,26,27,32,36,38,40,41, 43,45,46,54,59,61,63,65,71,72,76,77,80} [WDS]. Similar mod-p^4 theorems [WDS]: (density of allowed d mod 2^4)=7/16=0.437500 (density of allowed d mod 3^4)=33/81=0.407407 (density of allowed d mod 5^4)=233/625=0.372800 (density of allowed d mod 7^4)=878/2401=0.365681 (density of allowed d mod 11^4)=5406/14641=0.369237 (density of allowed d mod 13^4)=10298/28561=0.360562 (density of allowed d mod 17^4)=35453/83521=0.424480 (density of allowed d mod 19^4)=48901/130321=0.375235 Theorem [WDS proved using an idea by E.B.Escott 1900] If d squarefree then 2*d must be a a "congruent number" i.e. member of this sequence http://oeis.org/A003273 . But most of the above theorems are subsumed by the full solution theorem...: Upon looking in Henri Cohen: Number Theory volume I, Springer 2007 GTM 239, pages 392-395, lo and behold, he has a discussion of the diophantine a*X^4+b*Y^4=c*Z^2 leading to a complete solution of our problem! This 2-volume book by Cohen is packed with very powerful modern stuff and dispenses with a lot of old gunk. Specialized to our case a^4+b^4=d*c^2, here is the result. THEOREM [H.Cohen]. For integer d>=3 fixed, a^4+b^4=d*c^2 either has an infinite number of inequivalent nonzero solutions(a,b,c), or no nonzero solutions. For infinite solutions d must have squarefree part divisible only by 2 and primes 8*k+1. Then the question is related to this elliptic curve EC: y^2 = x*(x^2 + d^2) and we have infinite solutions if and only if the class of d modulo squares belongs to the image of EC's 2-descent map (described in section 8.3 of Cohen). Here is how the problem maps to EC: x=d*a^(-2)*b^2, y=d*d*b*c*a^(-3). Under the Birch/Swinnerton-Dyer conjecture, the rank of EC will always be even. Cohen p395 gives the following table, computed with MAGMA and MWRANK using above theorem, listing every d with 3<=d<=10001 such that infinite solutions exist. 17, 82, 97, 113, 193, 257, 274, 337, 433, 514, 577, 593, 626, 641, 673, 706, 881, 914, 929, 1153, 1217, 1297, 1409, 1522, 1777, 1873, 1889, 1921, 2129, 2402, 2417, 2434, 2482, 2498, 2642, 2657, 2753, 2801, 2833, 2897, 3026, 3121, 3137, 3298, 3329, 3457, 3649, 3697, 4001, 4097, 4129, 4177, 4226, 4289, 4481, 4546, 4561, 4721, 4817, 4993, 5281, 5554, 5617, 5666, 5729, 5906, 6002, 6353, 6449, 6481, 6497, 6562, 6577, 6673, 6817, 6866, 7057, 7186, 7489, 7522, 7537, 7633, 7762, 8017, 8081, 8737, 8753, 8882, 8962, 9281, 9298, 9553, 9586, 9649, 9778, 9857, 10001.

1 0

Re: [math-fun] Finding representation as sum of 2 or 4 squares using Gausian & Quaternion GCDs
by N. J. A. Sloane 21 Dec '11

21 Dec '11

On this subject there are useful references (especially one by Richard Bumby) listed in entry A001481 in OEIS. Neil

1 0

Re: [math-fun] Finding representation as sum of 2 or 4 squares using Gausian & Quaternion GCDs
by Warren Smith 20 Dec '11

20 Dec '11

RCS: I'm not sure about the rigor, but a very practical method of finding 3-square reps is to look at N-k^2, with k decrementing from floor(sqrtN)). Remove small prime factors, give up when there are an odd number of 3s or 7s, and hope that the cofactor is a 4K+1 prime. WDS: actually, I was just going to suggest exactly that. Now it seems plausible that the chance a number Q is prime is of order 1/lnQ hence this would find about sqrt(N)/ln(N) representations, and with the mean time between reps-found being of order logN. However, that reasoning was not rigorous. But it dawns on me that we can in fact get both rigor and decent speed as follows: ALGORITHM: Choose k at random in {1,2,...,floor(sqrt(N))}. If N-k^2 happens to be representable as a sum of 2 squares, you are done. Otherwise try again. It is a theorem of C.L.Siegel, re-proved in 1 page by Dorian M. Goldfeld: A simple proof of Siegel's theorem, Proc. Nat. Acad. Sci. U.S.A. 71 (1974) 1055 http://www.pnas.org/content/71/4/1055.full.pdf+html that the "class number" is lower bounded by constant*N^(1/2-epsilon) which tells us as a corollary (via work by Gauss) that every number N which is representable as a sum of 3 squares has at least constant*N^(1/2-epsilon) representations for any fixed epsilon>0. We also know you can factor N into primes in N^o(1) randomized time. We also know that numbers N have at most N^o(1) representations as sum of 2 squares. Putting all those things together, we conclude THEOREM: Above algorithm will run in expected N^o(1) time to find a representation of N as sum of 3 squares (if it has any). (Also, N is representable as the sum of 3 squares iff N is NOT of the form 4^a * (8*k+7) so it is trivial to decide representability.) Also Erich Hecke proved [proof published by E.Landau: Gottingen Nachr. (1918) 285-295] assuming the extended Riemann hypothesis that the number of 3-square reps was >constant*sqrt(N)/logN. So we might hope algorithm above will run in O(logN) expected primality tests, except that perhaps for a finite set of N it won't work. That's not a theorem, it's merely a hope, at present. RCS: If you have one rep as A^2+B^2+C^2, you can walk to more: a 5step move is see if any of the pairs A^2+B^2, A^2+C^2, or B^2+C^2 is divisible by 5; if so, multiply by (3+-4i)/5 to find the other 2-square rep for that pair; rinse & repeat. A 3step move is more interesting: fudge the signs so that 3 | (A+B+C); then subtract 2*(A+B+C)/3 from each of A,B,C. There are 7steps, etc.; roughly a commutative group; usually one or two kinds of step will cover all the 3-square representations. 3-step example: 1001 = 30^2 + 10^2 + 1^2; signs +30+10-1; 39*(2/3)=26; (30,10,-1) - (26,26,26) = (4,-16,-27); 16+256+729 = 1001. Gauss showed relationship between 3-square reps and binary quadratic forms; the steps are equivalent to composition of BQFs by constant forms. Steps exist for more general ternary quadratic forms like A^2+A*B+2*B^2+3*C^2. WDS: excellent. RCS: also said stuff about continued fractions and gaussian integers vis-a-vis the 4-square problem... WDS: indeed, for that see G. Rousseau: On a construction for the representation of a positive integer as the sum of four squares, L'Enseignement Math. (2) 33,3-4 (1987) 301-306.

1 0

[math-fun] Finding representation as sum of 2 or 4 squares using Gausian & Quaternion GCDs
by Warren Smith 20 Dec '11

20 Dec '11

Theorem of Lagrange: If N>0 is an integer then it has a representation as a sum of 4 squares N=a^2+b^2+c^2+d^2. Theorem of Euler: If, further, N's squarefree part is divisible only by primes 2 and 4*k+1, then (and only then) N=a^2+b^2. But: How can one QUICKLY FIND a,b,c,d given N?. Answer: Using GCDs over the Gaussian integers a+i*b and the quaternions a+i*b+j*c+k*d respectively! Here are the details. N=SUM OF TWO SQUARES: If N is square we are done. If N=2 then 2=1^2+1^2. If N is a prime of form 4*k+1 then use Shanks-Tonelli algorithm to solve x^2+1=0 (mod N) for x. Then find the Gaussian integer GCD(x+i, N). The result is a+i*b where a^2+b^2=N. Otherwise factor N into primes and squares, apply above methods to represent all the primes and squares, and multiply all the Gaussian integers you get. N=SUM OF FOUR SQUARES: We may factor N to find its squarefree part. So wlog we need only consider squarefree N. But actually I think it will suffice merely to remove all factors of 4 from N (which is way faster than factoring N to remove *all* squares) in the below. And now: If N=odd, then 2N-1+4*k*N is (for some k) a prime that is 1 mod 4, and hence of form a^2+b^2 where a and b found as above. If N=even, then, since N=squarefree, N=2(mod 4), in which case N-1+4*k*N is prime and 1 mod 4 (for some k), hence is expressible as a^2+b^2 as above. [Actually it is not necessary to choose k to get a prime since some composite N that are 1 mod 4 also are expressible as sum of two squares. But primes are frequent so that random k's will yield primes often, and primality testing is fast.] Let g=a+b*i. We know by construction that N divides a^2+b^2+1. Now take the quaternion (right) GCD(N, g+j) to find a representation of N as the sum of 4 squares. These algorithms run in time polynomial in the number of bits in N provided: * the prime factorization of N is available (for the 2 squares problem) * we are allowed to use a random number generator (for the 4 squares problem). What about 3 squares?

1 0

[math-fun] dense sets of points on curves, with only rational interpoint distances
by Warren Smith 20 Dec '11

20 Dec '11

1. You can show using trig identities that the set S of points on the unit circle {x^2+y^2=1} at angle t with tan(t/4)=rational, is dense and has the property that all point coordinates are rational and that all interpoint distances are rational. 2. Now in 4-dimensional space (x,y,u,w) consider the radius=3 circle in the xy plane and the radius=4 circle in the uw plane. [This is based on the pythagorean triple 3,4,5, but you can use any other.] We thus get a dense set of points on this circle-pair with all interpoint distances rational and all coordinates rational. 3. Similarly in 6-dimensional space (x,y,u,w,p,q) we can use three circles in the xy, uw, and pq planes with radii 240, 117, 44 [Any integer 3-tuple forming an "Euler brick" can be used, http://en.wikipedia.org/wiki/Euler_brick ]. 4. Can this be extended to 8 dimensions? For that we'd need a "4-dimensional Euler brick": a 4-tuple of integers a,b,c,d with all 6 sums of two-squared, equal to squares, i.e. a^2+b^2=square, a^2+d^2=square, ..., c^2+d^2=square. I do not know whether such a 4brick exists, but none exist with max(a,b,c,d)<=99999.

1 0