October 2013 - mathfun@mailman.xmission.com

[math-fun] Three flake frames
by Bill Gosper 05 Oct '13

05 Oct '13

(Easy for YOU to say.) gosper.org/flakes.png First frame is swing angle π/3, confirming DanA's guess about trisected areas. 2nd frame is implausible swing angle 7π/33, or VERY nearly, showing subflake at a peculiar angle. 3rd frame is even weirder angle that seems to make a triskelion out of ten tiny flakes. Doubt this one. --rwg Note that I answered DMakin about when Mike Stay did, but mine was delayed three hours. Death to spammers. Also, an embarrassing Fibonacho postscript: In[997]:= Sum[Binomial[n - k, k], {k, 0, n}] + Sum[Binomial[n - k, k], {k, n + 1, n + 1}] Out[997]= Binomial[-1, 1 + n] + Fibonacci[1 + n] In[998]:= Table[%, {n, 0, 9}] Out[998]= {0, 2, 1, 4, 4, 9, 12, 22, 33, 56} should be the same as In[999]:= Sum[Binomial[n - k, k], {k, 0, n + 1}] Out[999]= ((3 + n) Hypergeometric2F1[1/2 - n/2, -(n/2), -n, -4] + Binomial[-2, 2 + n] (-1 + Hypergeometric2F1[(2 + n)/2, (3 + n)/2, 2 + n, -4]))/(3 + n) In[1001]:= Simplify[Table[%%, {n, 0, 9}]] Out[1001]= {1/10 (5 - Sqrt[5]), 5/2 - 3/(2 Sqrt[5]), 2 - 2/Sqrt[5], 1/10 (55 - 7 Sqrt[5]), 1/10 (65 - 11 Sqrt[5]), 13 - 9/Sqrt[5], 37/2 - 29/(2 Sqrt[5]), 65/2 - 47/(2 Sqrt[5]), 50 - 38/Sqrt[5], 1/10 (835 - 123 Sqrt[5])} I.e., how to compute√5 as a finite sum of integers.

1 2

[math-fun] another kind of math genius...
by Warren D Smith 05 Oct '13

05 Oct '13

http://www.youtube.com/watch?v=BRS1H2TBRcU -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Three flake frames
by Adam P. Goucher 05 Oct '13

05 Oct '13

Bill wrote: > (Easy for YOU to say.) gosper.org/flakes.png > First frame is swing angle π/3, confirming DanA's guess about trisected > areas. > 2nd frame is implausible swing angle 7π/33, or VERY nearly, Actual value = ArcTan[(5 Sqrt[3])/11] ~ 0.666946 whereas 7 Pi/33 ~ 0.666398 That's a pretty massive difference. Indeed, it's closer to the even more implausible value of 2/3. In general, all of your swing angles will be arctangents of things in the quadratic field Q[Sqrt[3]], since they can be expressed as arguments of solutions to linear equations, the coefficients of which are complex numbers in the imaginary quadratic field Q[Sqrt[-3]]. The process of obtaining the equation and solution is pretty easy and boring. Sincerely, Adam P. Goucher http://cp4space.wordpress.com

1 0

[math-fun] math novels?
by Warren D Smith 05 Oct '13

05 Oct '13

>Dan Asimov: >But as long as we're on the subject, are there any books > or short stories involving math that math-fungi have liked? --er, hate to bring up the obvious, but if somebody named "Asimov" does not know the answer to this question... who does? I actually thought the "foundation" N-ogy by I.Asimov & posthumous others, was sort of mathematical. Not in the sense of actual math theorems, but there was a lot of logical deduction going on, and there was a collection of mathematicians/statisticians/political scientists who were sort of secretly in charge of everything, and you know you like that idea. Vernor Vinge & Larry Niven have written various works with a lot of pretend science or future math in them, and they sometimes write followups explaining how related/not their fiction is to actual science. So they at least try. Maybe some of you should try your hand at creating math-fiction. Vast unsatisfied unrecognized market for it... right?

3 2

[math-fun] a voting/stats puzzle
by Warren D Smith 05 Oct '13

05 Oct '13

That arose the other day with some aid+confusion provided by Jameson Quinn, is this. V voters each provide a score for each of C candidates (V*C scores in all) from some fixed set of allowed scores, e.g. the integer interval [0,1,2,...,9999]. Now plain "range voting" would be, the candidate with greatest average score, wins. We here instead consider this voting system, which might be called "(N,V) maxprob winner": If N voters were selected as a random subset of the V (0<N<=V) then the candidate with the greatest probability that his sample mean is maximal, wins. Note that if N=1, this is plain plurality voting. If N=V it is plain range voting. If done using pairs of candidates and N=1 then it is "Condorcet voting." So this is an interesting way to "hybridize" several proposed voting systems as one. Anyhow, QUESTION: is there any efficient algorithm to compute the (N,V) maxprob winner, or is this task #P-hard or NP-hard? (I have a pseudopolynomial time algorithm, i.e. if C and the score-set-cardinality are bounded, then it runs in polynomial time.) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

5 7

Re: [math-fun] Fractals are now recondite?
by Bill Gosper 04 Oct '13

04 Oct '13

What do you mean "works"? The new thing isn't a hexagon. No self-similarity. Re areas: They're the same as the original hexagon for all iterations of the construction --rwg. DMakin>Surely some mistake - the fractal version also works with hexagons ? i.e. with something of unit boundary dimension. Or am I going insane ? On 4 Oct 2013, at 21:29, Dan Asimov wrote: Guess: It's 1/21 of the large figure. --Dan On 2013-10-04, at 1:27 PM, Dan Asimov wrote: That's a really cool demo! I wonder what the area is of the triangular figure of the map-of-France at the moment the 3 "segments" first touch. --Dan On 2013-10-04, at 11:47 AM, Bill Gosper wrote: Mike Stay>That's great! May I suggest that when the area is smallest, you should give those three regions the labels 1, 2, and 3? Thanks! How's http://gosper.org/flaky.gif ? --rwg On Fri, Oct 4, 2013 at 2:41 AM, Bill Gosper <billgosper(a)gmail.com> wrote: Funster Gary Antonick (NYT NumberPlay) fears that the Franceflake fractal boundary paradox might be too hairy for his readers, even though Martin Gardner explained it in his original Flowsnake piece. So I made an mgif (gosper.org/flake.gif) illustrating the problem, and offering a URL for an (indirect) explanation. --rwg Re fibonachos, In[984]:= Sum[Binomial[n - k, k], {k, 0, Floor[n/2]}] Out[984]= Fibonacci[1 + n]

1 0

[math-fun] Fractals are now recondite?
by Bill Gosper 04 Oct '13

04 Oct '13

Funster Gary Antonick (NYT NumberPlay) fears that the Franceflake fractal boundary paradox might be too hairy for his readers, even though Martin Gardner explained it in his original Flowsnake piece. So I made an mgif ( gosper.org/flake.gif) illustrating the problem, and offering a URL for an (indirect) explanation. --rwg

2 1

[math-fun] Another fibonacho
by Steve Witham 03 Oct '13

03 Oct '13

>Date: Tue, 10 Sep 2013 16:39:57 -0700 >From: Henry Baker <hbaker1(a)pipeline.com> > >Go to this page & click on "Fibonachoes": > >https://www.facebook.com/IFeakingLoveScience/photos_stream Had trouble with the reference at first (you mean the Foxtrot, right?) But stumbled on this one, new to me: http://www.thedailyoldman.org/2011/02/fibonacho-series.html 1 = 1 |\ 1 = 1 | |\ 2 = 1 + 1 |\| |\ 3 = 2 + 1 | |\| |\ 5 = 1 + 3 + 1 |\| |\| |\ 8 = 3 + 4 + 1 | |\| |\| |\ 13 = 1 + 6 + 5 + 1 |\| |\| |\| |\ 21 = 4 +10 + 6 + 1 | |\| |\| |\| |\ 34 = 1 +10 +15 + 7 + 1 |\| |\| |\| |\| |\ 55 = 5 +20 +21 + 8 + 1 | |\| |\| |\| |\| |\ 89 = 1 +15 +35 +28 + 9 + 1 ... not to mention http://mathworld.wolfram.com/PascalsTriangle.html --Steve

1 0

[math-fun] linear psu-random generators with linear "feed-in"
by Warren D Smith 01 Oct '13

01 Oct '13

THEOREM: The linear congruential generator x <-- x*a + R mod 2^w (where w>=2 and a mod 4=1) has period = 2^w if R is any odd constant. If however R is actually ANOTHER psu-random generator with odd period and odd period-sum, then the result is a generator whose period is the product of R's period with 2^w. Here R's "period-sum" means the sum of all the R-values in R's period. EXAMPLE (in C language using 32-bit unsigned integers) if(z >= 1588146105U){ z -= 1588146105U; }else{ z -= 1588146108U; } implements a Weyl generator modulo 2^32-3, using step size 1588146105 which is chosen because 1588146105/(2^32-3) has only 1s and 2s in its continued fraction expansion. Its period-sum is odd because 2^32-3 mod 4 = 1. Hence x *= 2891336453U; if(z >= 1588146105U){ z -= 1588146105U; }else{ z -= 1588146108U; } x += z; (output x) implements a generator with period = (2^32-3) * (2^32) using the two state-variables w and x. (Here 2891336453 is spectrally-good multiplier mod 2^32.) THEOREM: If y <-- T y where y is an n-bit vector and T is an nXn matrix over GF(2) is a psu-random generator with period=2^n-1 for nonzero vectors y, then y <-- (T y) XOR R also is a period=2^n-1 generator if R is any constant n-vector. If however R is itself a psu-random generator whose period is relatively prime to 2^n-1, then the result is a psu-random generator whose period is the product of the two original periods. EXAMPLE (again in C with 32-bit unsigned int words): y ^= (y << 5); y ^= (y >> 7); y ^= (y << 22); is a psu-random generator with period-2^32-1 (state is a nonzero 32-bit word y). We could feed the output of the preceding example into it to get a generator with period = (2^32-1) * (2^32-3) * 2^32: x *= 2891336453U; y ^= (y << 5); y ^= (y >> 7); y ^= (y << 22); if(z >= 1588146105U){ z -= 1588146105U; }else{ z -= 1588146108U; } x += z; y ^= x; (output y) and so on. It also would be possible, of course, to combine two generators by just (say) XORing (or adding mod 2^32) their outputs. However, it seems intuitively that "feeding in" generator 1 to generator 2 usually will produce a result "more random" than just XORing their outputs, whenever generator 2 "amplifies randomness." The feed-in option is open to us essentially whenever generator 2 is a "linear recurrence" in some ring. For nonlinear psu-random generators, such as v <-- v*(975403184785438903-2*v)+856300274470584321 mod 2^64 (I chose these numbers randomly subject to 975403184785438903 mod 4 = 3 and 856300274470584321=odd, here the state is odd 64-bit unsigned int v and the period is 2^63) I have no feedin theorem, but these can still be used as "generator 1." For example in C now with 64-bit unsigned integers: v = v*(975403184785438903-2*v)+856300274470584321 x ^= x<<7; x ^= x>>9; x ^= v; (output x) is a generator with period=(2^64-1)*2^63. Here x is a linear-GF2 generator with state being nonzero 64-bit words; it has feed-in from the quadratic v-generator with state being odd 64-bit words. Richard Brent devised a class of generators he calls "xorgens" http://arxiv.org/pdf/1004.3115.pdf which are linear over GF2 and have period=2^(n*w)-1 which is maximal considering their state is n words, each w bits, not all zero. He then wanted to combine these with a 1-word Weyl generator with period=2^w. In doing so, Brent made two small mistakes, in my opinion (better would be calling them "missed opportunities" not "mistakes"). First, he could have "fed in" the Weyl generator into his xorgen instead of just combining their two outputs. Second, he used step size in the Weyl generator based on the golden ratio times 2^w where w is the word size. Better would have been to employ an odd step size S chosen so S/2^w had only 1's and 2's in its continued fraction expansion. With w=32 the following 5 S's work: S=1774682003=69C77F93, S=1812433253=6C078965, S=2482534043=93F8769B, S=2520285293=9638806D, S=3140748093=BB34033D. With w=16 this S works: S=46073=B3F9. I'm not sure whether it will be feasible to find such an S for w=64, but it is feasible to find examples with max partial quotient <=3 for every word size w, see H.Neiderreiter: Dyadic fractions with small partial quotients, Monatshefte fur Mathematik 101,4 (1986) 309-315. [If anybody could send me a pdf of this, would appreciate that.] Although I have no feedin theorem for nonlinear generators, sometimes nonlinear generators are really linear ones "in disguise" in which case feedin theorems can be made. For example, the lagged Fibonacci generator x[n] = x[n-55] * x[n-24] where the x's are odd numbers and multiplication is mod 2^w, is linear using discrete log as the disguise. Hence one could use multiplicative feedin like this x[n] = x[n-55] * x[n-24] * R where R is any generator that always outputs odd values, and has an odd period relatively prime to 2^55-1. The resulting generator will have period of (x mod 4) equal to (2^55-1)*period(R). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

7 11

[math-fun] curious dyadic rationals t/b, b=2^f, t=sum of few +-2^e, ContinuedFraction(t/b) has 1's and 2's only
by Warren D Smith 01 Oct '13

01 Oct '13

As an example, consider b = 2^63 = 9223372036854775808(decimal) = 8000000000000000(hexadecimal) = 1000000000000000000000000000000000000000000000000000000000000000(binary) t = 5836946587753906177(dec) = 5100FFFF00000001(hex) = 101000100000000111111111111111100000000000000000000000000000001(binary) ContinuedFraction(t/b) = [0; 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2] I have found that there are many such examples, and they are easy to find by computer search because t is a sum of few signed powers of 2. In the present example, t is a sum of 6 of them, and since binomial(64,6) * 2^5 = 2399179776 = 2.4 * 10^9 it would be feasible to consider all possibilities. Another example has t' = 101000100000000111111111111111011111111111111111111111111111111(binary) which yields a very "nearby" continued fraction to the first example: ContinuedFraction(t'/b) = [0; 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2] -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2