September 2013 - mathfun@mailman.xmission.com

[math-fun] Size of the Cherbakul Lake Meteorite Fragment
by Hans Havermann 16 Oct '13

16 Oct '13

From a National Post (newspaper) article today: "Viktor Grokhovsky, who led the expedition from Urals Federal University, said Monday the meteorites plucked from the ice-covered Chebarkul Lake so far are less than a centimeter and had an iron content of about 10 percent. Locals saw a big meteorite fall into the lake on Friday, leaving a six-meter-wide hole in the ice. Grokhovsky said a meteorite up to 50-60 centimeters could eventually be found in the lake." When the initial reports of the 6 m hole surfaced, I thought (looking at a picture of the hole in the ice): That must be a 4 m (or more) chunk of rock. But .5 m? An impact in a surface ice layer surely is not like an impact on ground where a wider hole might be expected.

6 9

[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

[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 29 Sep '13

29 Sep '13

>Hum, interesting but what is t ? what type of number is it ? >what is the rule for t ? >Simon Plouffe --well, I'd like to know that myself... I do not have a full explanation/understanding for what is going on here... However, I observe the following pattern for the particular t that I gave: t = 101000100000000111111111111111100000000000000000000000000000001(binary) note the "gap sizes" between the 1's (or -1's) are 1, 3, 7, 15, 31 a sequence I'm sure you recognize. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

[math-fun] Ford circle blues
by Stuart Anderson 29 Sep '13

29 Sep '13

http://www.squaring.net/downloads/ford-circle-blues.ps http://www.squaring.net/downloads/ford-circle-blues.pdf % an adaption of Noam Elkies ford.ps (postscript that recursively draws Ford circles) % original at http://www.math.havard.edu/~elkies/Misc/ford.ps % see http://www.math.havard.edu/~elkies/Misc/#pstrix (added some reflections and colouring in shades of blue) Stuart Anderson

2 1

Re: [math-fun] math-fun Digest, Vol 127, Issue 37
by Stuart Anderson 29 Sep '13

29 Sep '13

Nice > Triangularly linking three flowsnakes and then polygon-filling looks > unexpectedly nice, > so I rewrote gosper.org/flowsnakes.pdf yet again. > --rwg > > > >

1 0

Re: [math-fun] exact flowsnake spacefilling function
by Bill Gosper 29 Sep '13

29 Sep '13

Wouter> should be about (5 - I Sqrt[3])/14 , no? W. ARRGGH! Right. I'll fix the pdf. --rwg -----Original Message----- From: Wouter Meeussen Sent: Saturday, September 28, 2013 11:36 AM To: math-fun Subject: Re: [math-fun] exact flowsnake spacefilling function Bill, what is the value of w? Wouter.

1 1

[math-fun] exact flowsnake spacefilling function
by Bill Gosper 28 Sep '13

28 Sep '13

>From gosper.org/flowsnakes.pdf (q.v. for pix): FlowS[t] gives the exact value for rational t. E.g., In[148]:= FlowS /@ {0, 1/7, 1/3, 1} Out[148]= {0, 5/14 - (I Sqrt[3])/14, 4/7 + (2 I Sqrt[3])/7, 1} It's a continuous function: In[149]:= FlowS /@ {7/22, 113/355} Out[149]= {1693/2762 + (543 I Sqrt[3])/2762, 13159704187...887406573947767669/ 21456243153017...26366300007824801961964892568 + (152317993023640247...951911649014 I)/ (268203039412723583...100245245611571 Sqrt[3])} In[150]:= N[%] Out[150]= {0.612962 + 0.340515 I, 0.613328 + 0.327889 I} As usual, it redefines itself twice and has no obvious termination condition: In[119]:= Clear[FlowS]; FlowS[t_, a_: 1, b_: 0] := FlowS[t, x_: 0, y_: 0] = (FlowS[t, s1_: 1, s0_: 0] = (b - s0)/(s1 - a); Module[{u = t*7, n}, u -= (n = Floor[u]); ComplexExpand[Switch[n, 0, w*FlowS[u, a*w, b], 1, w*(1 + (-1)^(1/3) + (-1)^(4/3)* FlowS[1 - u, a*(-1)^(4/3)*w, b + a*w*(1 + (-1)^(1/3))]), 2, w*((-1)^(1/3) + FlowS[1 - u, a*w, b + a*w*(-1)^(1/3)]), 3, w*((-1)^(1/3) + (-1)^(2/3)* FlowS[u, a*(-1)^(1/3)*w, b + a*w*(-1)^(1/3)]), 4, w*(Sqrt[-3] + FlowS[u, a*w, b + a*w*Sqrt[-3]]), 5, w*(2*(-1)^(1/3) + FlowS[u, a*w, b + a*w*2*(-1)^(1/3)]), 6, w*(2 + (-1)^(1/3) + ((-1)^(1/3) - 1)* FlowS[1 - u, a*w*((-1)^(1/3) - 1), b + a*w (2 + (-1)^(1/3))]), 7, 1]]]) Toward the end of the pdf are two plots that suggest there may be a typo in this definition. --rwg

2 3

Re: [math-fun] minimal dissection of cube into simplices
by Bill Gosper 27 Sep '13

27 Sep '13

NJAS>There's a much simpler question: what's the smallest number of pieces for dissecting a square into (pieces that can be rearranged to form) an equilateral triangle? 4 is possible - see http://oeis.org/A110312, especially the last link. 3 seems impossible, but is there a proof? The pieces must be bounded by simple curves. Neil What? No jhinged animation?-) Somewhat apropos: http://gosper.org/shardway.PNG (My G4G8(?) exchange gift.) --rwg On Thu, Sep 26, 2013 at 10:47 PM, Victor Miller <victorsmiller(a)gmail.com>wrote: Scott, this is discussed (rather tersely) here: http://www.ics.uci.edu/~eppstein/junkyard/cube-triangulation.html . Also, if you don't know about David Eppstein's Geometry Junkyard, you should. It's a treasure trove of all sorts of wonderful things: http://www.ics.uci.edu/~eppstein/junkyard Victor On Thu, Sep 26, 2013 at 8:51 PM, <rcs(a)xmission.com> wrote: This is from Scott Huddleston <scott.huddleston(a)intel.com> --Rich --- What's the minimum number of pieces for dissecting an n-cube into n-simplices? You can always dissect into n! simplices, but that's not minimal for n>2. This was an open problem when I was in grad school (awhile back). Is there always a minimal dissection that includes a maxvol simplex? - Scott

1 0

[math-fun] minimal dissection of cube into simplices
by Warren D Smith 27 Sep '13

27 Sep '13

I wrote a paper on this, see http://rangevoting.org/WarrenSmithPages/homepage/works.html paper #41. This at the time (still?) was the best known lower bound on simplexity of the N-cube, it was simply hyperbolic volume ratio. Another good lower bound method called "linear programming method" arises by noting that each face of the N-cube needs to be dissected into simplices also (and so on, for lower dimensional flats than "faces" too) so you can by combining all these constraints write a linear program whose solution provides a lower bound on simplexity. Even better lower bounds presumably would result from combining both hyperbolic volume and linear programming ideas, but last time I looked nobody had ever worked out the result of that. Meanwhile for upper bounds, it is a matter of finding good triangulations. Sallee, Cottle, and Haiman have got various ways to produce triangulations better than the naive-recursive triangulation involving N! simplices. Last I looked the best lower bounds had behavior (N/2)! * C^N for some C>1, and the best upper bounds had the form N! * K^N for some constant K with 0<K<1. Note the large gap. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0