November 2011 - mathfun@mailman.xmission.com

[math-fun] An alternative way to count the rationals?
by Warren Smith 11 Nov '11

11 Nov '11

I erred in a previous post in saying my algorithm to determine the ordinal N of a rational a/b ran in O(log(a)+log(b)+1) time. There are counterexamples. It genuinely runs in O(1+logN) time but that's a weaker bound. The runtime is a bit like the runtime for a hamstrung variant of the "binary GCD" algorithm on (a,b) but the problem is if a<<b and a,b have opposite parities, then your grandparent in the Calkin-WIlf tree is (a, b-2a) which is pathetically slow progress toward the tree-root. However, it seems to me we can speed things up in this case by doing many steps at once. After 2M to-parent steps which automatically all will be in the same "direction" you go directly to (a, b-2Ma) and we can choose M=floor((b-a)/(2a)) so that this is a big reduction. That makes the speed more like the Euclidean GCD algorithm. Then, the runtime bounds I was erroneously claiming, become true again... provided you output N's binary expansion in a "runlength encoded" data-compressed format instead of straight binary. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Warren D Smith enters math-fun list
by Warren Smith 11 Nov '11

11 Nov '11

Hello everybody... Gosper finally prodded me into joining this list. My papers are currently available rather badly here: http://rangevoting.org/WarrenSmithPages/homepage/works.html I need to update that and create a nicer webpage to stash my papers. Which leads to my question: Where would you recommend that I set up my (new) web page? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Scientific American Weekly
by Hans Havermann 10 Nov '11

10 Nov '11

If you appreciate 19th-century American science/mechanics ephemera, Scientific American has made accessible for a few weeks its digital archive of Scientific American Weekly (28 Aug 1845 - 25 Dec 1909): http://www.nature.com/scientificamerican/archive/index_1909.html A small heads-up... I came across dozens of unreadable (damaged) pdf- files, missing and misdirecting links, and other organizational flaws that put a slight damper on this "treasure trove". The text is OCR of course so, while a complete issue may be searchable in your pdf- viewer, don't expect too much.

1 0

Re: [math-fun] BBC - Bletchley Park Code Breakers - Tutte and Flowers
by Henry Baker 10 Nov '11

10 Nov '11

I was able to find the program online, but it requires a bit of fiddling to download & play it. It is 1.5 GBytes & 60 minutes in length, but well worth watching. It describes Colossus, which used paper tape as its input. From the brief description in the TV program, the German code appeared to be a "one-time" XOR pad, except that the "random" bits were generated by a pseudo-random bit generator that wasn't random enough. It would be interesting to see if the methods in Knuth on testing pseudo-random bit generators would work on this German code. Because storage in the form of vacuum tubes ("valves") was so expensive, the paper tape input was tied end-to-end and cycled endlessly for each scan of the input data. Because of these long loops of paper tape, Colossus looked a lot like a late 19th century factory where a system of belts conveyed power before the invention of small electric motors. I guess these recirculating paper tapes became the paradigm for the later ultrasonic delay lines which recycled data in the form of sound waves. Ditto for drum & disk drives, which recycled data on magnetic "tapes". At 06:48 PM 11/8/2011, Stuart Anderson wrote: >A new BBC documentary has been screened on Bletchley Park Code >Breakers, on how the Nazi Lorenz cipher was cracked. (Lorenz has >been described as Hitlers 'Blackberry' - not to be confused with >Enigma). The doco provides new archival material on the contributions >of William Tutte and Tommy Flowers. Tutte with his reconstruction of >the Lorenz cypher/decypher mechanism, based only on intercepted >messages and later his statistical algorithm which required a >computer. This was Tommy Flowers contribution. He invented and >constructed of the worlds first electronic programmable computer, 2 >years before ENIAC, to run Tutte's algorithm. The rest as they say is >history, but for most of the last 60 years this history has been kept >secret. > > Some secrets have been kept for too long. > >http://www.youtube.com/watch?v=bMu8UiHJHgs > >Stuart

1 0

[math-fun] BBC - Bletchley Park Code Breakers - Tutte and Flowers
by Stuart Anderson 09 Nov '11

09 Nov '11

A new BBC documentary has been screened on Bletchley Park Code Breakers, on how the Nazi Lorenz cipher was cracked. (Lorenz has been described as Hitlers 'Blackberry' - not to be confused with Enigma). The doco provides new archival material on the contributions of William Tutte and Tommy Flowers. Tutte with his reconstruction of the Lorenz cypher/decypher mechanism, based only on intercepted messages and later his statistical algorithm which required a computer. This was Tommy Flowers contribution. He invented and constructed of the worlds first electronic programmable computer, 2 years before ENIAC, to run Tutte's algorithm. The rest as they say is history, but for most of the last 60 years this history has been kept secret. Some secrets have been kept for too long. http://www.youtube.com/watch?v=bMu8UiHJHgs Stuart

1 0

[math-fun] Cobra Weave Exploding Stick Bomb
by Stuart Anderson 09 Nov '11

09 Nov '11

from Google+; Terence Tao - Yesterday 4:05 PM - Public Allen Knutson originally shared this post: http://tumblr.com/ZmgiAxAXT-Qu Turns out one can weave popsicle sticks into a huge pile of potential energy. The Kid Should See This. - Whoa, how did we miss this?! This is a popsicle stick weave chain reaction called the “Cobra Weave Exploding Stick Bomb,” and you can do it yourself following an Instructables How To. — Time to go out and buy popsicles! cheers, Stuart

1 0

[math-fun] Question about amicable numbers
by David Wilson 08 Nov '11

08 Nov '11

Is there an upper bound to the ratio of amicable numbers? To the ratio of maximum and minimum of an amicable chain?

3 2

[math-fun] Solvable, irreducible quintic trinomials
by Bill Gosper 08 Nov '11

08 Nov '11

The only ones of height<=5 are x^5 - 5 x^2 - 3, 2*x^5 - 5*x + 4, and 4*x^5 + 5*x + 4 (modulo x->1/x). The only real root of the 2nd one is (1/(2^(2/5) 5^( 3/5)))(-(150 - 100 Sqrt[2] + Sqrt[10 (4250 - 2999 Sqrt[2])])^( 1/5) + (-150 + 100 Sqrt[2] + Sqrt[10 (4250 - 2999 Sqrt[2])])^( 1/5) - (150 + 100 Sqrt[2] - Sqrt[10 (4250 + 2999 Sqrt[2])])^( 1/5) - (150 + 100 Sqrt[2] + Sqrt[10 (4250 + 2999 Sqrt[2])])^(1/5)) This seems almost a case of "*a stupid man asking such a question to which one hundred wise men would not be able to answer*." Various sources, e.g., http://en.wikipedia.org/wiki/Quintic_function give a pair of equations which have rational roots iff x^5+ax+b is solvable and irreducible, but sometimes reducible cases that fail this test, e.g., {3/8 - (5 x)/8 + x^5, 8/3 + (5 x)/3 + x^5}, yield to the quintic solver, producing obscure radical identities of the form biquadratic = sum of four fifth roots of biquadratics, which paralyze FullSimplify. I don't know if it's proven or merely conjectured that there are no solvable irreducible septic trinomials. See http://www.math.harvard.edu/~elkies/trinomial.html --rwg

1 0

[math-fun] Tetrahedon test-case
by Fred lunnon 08 Nov '11

08 Nov '11

A useful minimal "Heronian" tetrahedron with integer edge-lengths, face-areas, volume etc (due to Rathbun?) is given at http://mathworld.wolfram.com/HeronianTetrahedron.html Warning: the sides have been shuffled on that page: for consistency with other examples given there, they should instead be re-ordered as 51 52 53 80 117 84 . Furthermore the areas and volume given there are bizarrely garbled [although correct for other examples, with the ordering repaired] --- they should actually read 1170, 1890, 2016, 1800 (in some order); 18144 [is Eric Weisstein online?]. To utilise this as a test-case requires coordinates: one pose has vertices [w,x,y,z] = [1,0,0,0], [1,51,0,0], [17,416,780,0], [1105,-43680,63756,-51408], where a point has Cartesian coordinate [x/w, y/w, z/w] ; and faces [d,a,b,c] = [0,0,0,1], [0,0,204,-253], [0,45,24,-68], [835380,-16380,9471,20128], where a plane has equation a x + b y + c z + d w = 0 . Almost certainly, a cunningly chosen isometry would reduce the size of these components substantially; but I don't have any ideas about a good algorithm for finding the optimal pose. Any ideas, anybody? Fred Lunnon

1 2

[math-fun] Tetrahedral Centers
by ed pegg 07 Nov '11

07 Nov '11

Since this has come up, here's a long time question I've had.... Take a random tetrahedron. For a given triangle center, connect it to the opposing corner of the tetrahedron. Repeat for each face of the tetrahedron. For which triangle centers are the 4 lines concurrent? If X333 had that property, I suppose Y333 would be a fine name for that Tetrahedral center. Links: http://faculty.evansville.edu/ck6/encyclopedia/ETC.htmlhttp://bernard.giber… Ed Pegg Jr

5 10