March 2013 - mathfun@mailman.xmission.com

[math-fun] Binary recursive GCD algorithms?
by Henry Baker 25 Mar '13

25 Mar '13

I'm looking for the _simplest_ binary _recursive_ GCD algorithm that has "pretty good" performance. I.e., a GCD algorithm that takes two length 2m integers and reduces this to a number of computations on length m integers. I did a quick Google search, and there seems to be a plethora of different such algorithms, but most are worried about the best possible performance at the expense of simplicity. I'm looking for something about as simple as Karatsuba squaring: (a+bx)^2 = a^2 + b^2x^2 + (a^2+b^2-(a-b)^2)*x

1 0

Re: [math-fun] X^2, ln(X), repeat...
by Keith F. Lynch 25 Mar '13

25 Mar '13

"Huddleston, Scott" <scott.huddleston(a)intel.com> wrote: > . . . I think I understand what you're saying. There's a unique fixed point which I can find by alternating between e^X and the negative branch of sqrt(X). It's equal to about -0.703467. There's a unique cycle of length 2 which I can find by alternating between e^X and alternating between the positive and negative branches of sqrt(X). It's equal to about -1.298510. There are two cycles of length 3, whose values are about -1.482929 and -1.840801. (In each case, I'm listing the smallest number that appears in the cycle.) The number of cycles for lengths 1 through 7 are 1,1,2,3,6,9,18, which may be A066313. (Of all the OEIS sequences that begin with those numbers, that's the only one that mentions necklaces.) Trying to go further gets me precision loss. Here's a table: 1 -0.703467 2 -1.298510 3 -1.482929 3 -1.840801 4 -1.402786 4 -2.142474 4 -2.441350 5 -1.428439 5 -1.467677 5 -1.928954 5 -2.004383 5 -2.981728 5 -3.287670 6 -1.405661 6 -1.419140 6 -1.882384 6 -2.047197 6 -2.076965 6 -2.639042 6 -2.709934 6 -4.614471 6 -4.935768 7 -1.422375 7 -1.427156 7 -1.470046 7 -1.477157 7 -1.899349 7 -1.911679 7 -2.021488 7 -2.031539 7 -2.101821 7 -2.121867 7 -2.519123 7 -2.556653 7 -2.788948 7 -2.817744 7 -3.771299 7 -3.847934 7 -10.852741 7 -10.935144 These cycles are all repellers. The process bounces from one to to another pseudo-randomly forever. It might be interesting to graph all these numbers. Are they dense? Are they a cantor dust? What do they look like extended into the complex plane? Or would that just be asking for trouble, since the log function would also become multivalued? Is this really the first time anyone has studied this process/ sequence/system? How can that be answered, anyway? It's very hard to do a Google search on anything mathematical.

2 1

[math-fun] sqrt(pi)
by Bill Gosper 24 Mar '13

24 Mar '13

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

2 3

[math-fun] Tesseract Day!
by rcs＠xmission.com 23 Mar '13

23 Mar '13

Tomorrow is Tesseract Day! Think 4-dimensional thoughts. Rich

4 4

[math-fun] X^2, ln(X), repeat...
by Keith F. Lynch 22 Mar '13

22 Mar '13

Years ago I noticed that if I alternate between hitting the X^2 and the ln(X) buttons on a calculator, the result neither converges nor blows up, but just wanders around, seemingly at random. What, if anything, is known about this sequence? Does it have any fixed points? Any cycles of length N for any N? What is the distribution? The mean value (after the log step) seems to be between 0.15853 and 0.15854. With some values it will blow up. 0 will make it blow up in one step, 1 or -1 will make it blow up in two steps, sqrt(e), -sqrt(e), sqrt(1/e), and -sqrt(1/e) in three steps, etc. The number of such explosive starting values doubles with each step. Is this set of explosive starting values dense, i.e. between any two such values is there always another?

4 3

[math-fun] Toe-curling classical number-theory problem
by Fred lunnon 22 Mar '13

22 Mar '13

The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is). Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} . Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory" Some things were quite definitely not better in the old days! Fred Lunnon

4 7

Re: [math-fun] poisoned wine bottles
by Veit Elser 22 Mar '13

22 Mar '13

I have no improvement to report on the 10-rat case, but here's a surprise development we owe to my former student Mike Quist. Shortly after I explained the poisoned bottle problem to him he pointed out that one shouldn't make the assumption that a uniform partition of the bottles is always going to be optimal. To prove his point, Mike constructed, for 7 rats, a 4-unique code of size 19. When the bottles are partitioned evenly this would give a discard fraction of 4/19, inferior to what one gets with Michael's size 21 4-unique code reported Nov. 28. However, by unequally partitioning the bottles you can get a discard fraction of 2/11 with Mike's code! Rather than show you Mike's code I'll give you the simplest case of this phenomenon which requires 6 rats. Using a mixed-integer program I checked that for less than 6 rats the equal partition is optimal. The same linear programming method found the following code for 6 rats: Construct the 2+2+2 product code from the 2-rat code {00,01,10}. This has 27 codewords. Now remove all the codewords of weight 3; that gives a code having 1 word of weight 0, 6 words of weight 1, and 12 words of weight 2, for a total of 19 codewords. Partition the wine bottles so 7/49 are assigned to the zero word, 1/49 to each of the weight 1 words, and 3/49 to each of the weight 2 words. You can check that for any union of codeword pairs you never have to discard more than the fraction 12/49 -- a modest improvement over 1/4. For example, there are some unions where 6 codewords are implicated (it is a 6-unique code), but in all these cases the bottle partition has the form (1+1+1+3+3+3)/49=12/49. Are unequal bottle partitions going to be the rule for optimal codes? So far we only know it is true for 6 and 7 rats. When I relax the equal partition condition and optimize the good codes we found in the past with respect to this I get no improvement (the optimal partition is the uniform one). So it seems we need a new approach to get the truly optimal codes. I can send the *.lp file for 7 or more rats to anyone interested with access to a big computer. At this point we only have optimal solutions up to 6 rats: n 1 2 3 4 5 6 f 1 2/3 1/2 2/5 1/3 12/49 The gurobi solver finds the last entry in 2 sec when I restrict the codewords to weight 2 and 15 minutes when I allow weight 3. For 7 rats it finds the 4/21 solution, that is optimal for weight < 3 , in 15 sec. But finding Quist's 2/11 solution, which includes weight 3, is not going to happen on my laptop! -Veit On Jan 6, 2013, at 4:46 PM, Veit Elser <ve10(a)cornell.edu> wrote: > Wow -- that was fast! > > wax & wane has found several more 50/4's, all with the same > (quaternion unit) symmetry group. I'll try a deeper search to > see if something else turns up. > > -Veit

2 5

[math-fun] Subject Re: A129935
by Bill Gosper 21 Mar '13

21 Mar '13

Phil, can't you just modify the Mma code, e.g. In[321]:= $MaxExtraPrecision=999999999;Reap[For[{lo={0,1},hi={1,0},nu={0,0},n=0},n<20,nu=lo+hi;For[{k=nu[[2]]},Floor[k*2/Log[2]]!=Ceiling[2/(2^(1/k)-1)],k+=nu[[2]],Sow[Short[{++n,k}]]]; If[nu[[1]]*Log[2]>2*nu[[2]],hi=nu,lo=nu]]][[2,1]] Out[321]= {{1,777451915729368},{2,140894092055857794},{3,1526223088619171207},{4,3052446177238342414},{5,54545811706258836911039145},{6,624965662836733496131286135873807507},{7,1667672249427111806462471627630318921648499},{8,36465374036664559522628534720215805439659141},{9,72930748073329119045257069440431610879318282},{10,2424113537313479652351566323080535902276508627},{11,123447463532804139472316739803506251988903644272},{12,246894927065608278944633479607012503977807288544},{13,370342390598412418416950219410518755966710932816},{14,97841697218028095572510076719589816668243339678931971},{15,5630139432241886550932967438485653485900841911029964871},{16,67828503903932028724406381<<5>>41860326049085269592368999},{17,13565700780786405744881276<<6>>83720652098170539184737998},{18,31224882396890130461213552<<32>>82642817828920779530446911},{19,51263782972844760095024321<<33>>77185206388903158084832387},{20,18682663844967088406936829<<36>>55972395912786276854715767}} Or are you angling for an outside opinion (which would indeed be welcome)? --rwg From: Neil Sloane <njasloane(a)gmail.com> I've added Bill Gosper's Mma code to A129935. Phil, does your Pari code need any changes? If so, could you make them please? PhilC>I can do a very quick change (basically bump the loop limit to c[n+1]) right now, and that that's good for 100 terms, but I'd like to test it *much* more thoroughly first. My code explodes with new terms in vast quantities as soon as it reaches 500 digits, and I'd like to investigate that to check it's not a bug. Can someone send me (offlist, obviously) the Mma output up to *big*, (say, the 5000 terms, and maybe some additional larger terms with indices for spot-checking?) please? Phil

1 0

Re: [math-fun] A129935
by Phil Carmody 20 Mar '13

20 Mar '13

From: Neil Sloane <njasloane(a)gmail.com> > I've added Bill Gosper's Mma code to A129935. > Phil, does your Pari code need any changes? If so, could you > make them please? I can do a very quick change (basically bump the loop limit to c[n+1]) right now, and that that's good for 100 terms, but I'd like to test it *much* more thoroughly first. My code explodes with new terms in vast quantities as soon as it reaches 500 digits, and I'd like to investigate that to check it's not a bug. Can someone send me (offlist, obviously) the Mma output up to *big*, (say, the 5000 terms, and maybe some additional larger terms with indices for spot-checking?) please? Phil -- () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani]

1 0

Re: [math-fun] Twenty-dollar question
by Adam P. Goucher 20 Mar '13

20 Mar '13

Catenaries and parabolae are only distinguishable at large scales: http://en.wikipedia.org/wiki/File:Comparison_catenary_parabola.svg > ----- Original Message ----- > From: James Propp > Sent: 03/18/13 07:03 PM > To: math-fun > Subject: [math-fun] Twenty-dollar question > > Is the hanging chain on the back of the $20 bill mathematically correct? It > looks more like a parabola than a catenary to me. > > Jim Propp > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

6 6