January 2012 - mathfun@mailman.xmission.com

Re: [math-fun] math-fun Digest, Vol 106, Issue 44
by Tom Duff 03 Jan '12

03 Jan '12

> Then, by chance I got a couple emails in a row from members of the Cult > of 137 [3], and I decided to prove to myself (and to them) that it is > easy to make all sorts of meaningless formulas for any number you > choose. Strangely, the number 237 has its partisans, some of whom contribute to this list. See HAKMEM for examples. Personal note: 237 Erskine Avenue in Toronto was the house I lived in as a young (pre-HAKMEM!) child. -- Tom Duff. Employee number 70068288.

2 1

[math-fun] min(x, y) and sorting without if(), mod without divide or if
by Warren Smith 03 Jan '12

03 Jan '12

On a 32-bit machine in C where x,y are ints, min(x,y) = y+(((x-y)>>31)&(x-y)); max(x,y) = x-(((x-y)>>31)&(x-y)); A related cute one is where you have X with 0<=X<M then you add some alteration to X which might move it into the interval [M, 2M) and we want to take the result mod M so as to return to the interval [0, M). Slow way: X = X%M. Faster way: if(X>=M) X -= M; no-if way: X -= ((M-1-X)>>31)&M; If X due to a subtractive alteration might have moved into [-M, 0) so to get it back you add M, if(X<0) X += M; no if-way: X += (X>>31)&M;

2 1

Re: [math-fun] Fracfac expansions (fractions in factorial base)
by Dan Asimov 02 Jan '12

02 Jan '12

Thanks for the correction of my careless error. What I should have written is that uniqueness holds if the greedy algorithm is used. (For each n = 1,2,3,... choose c_n, 0 <= c_n <=n, to be as large as possible such that the partial sum c_1/2! + c_2/3! + . . . + c_n/(n+1)! does not exceed the real number x being represented.) Which brings up the question: Is the greedy algorithm the most efficient? (Say in terms of minimizing the number of nonzero coefficients when x is rational.) It's well-known that this is not the case for Egyptian fractions. But for factorial denominators this seems more likely. --Dan Joerg wrote: << I wrote: << Since high school I've thought factorial base is an interesting way to express real numbers in the unit interval (0,1). That is, since 1/2! + 2/3! + 3/4! + ... = (d/dx((e^x-1)/x))(1) = 1, every x in (0,1) has a unique representation of the form x = Sum_{n=1..oo} c_n/(n+1)! if the integers c_n satisfy 0 <= c_n <= n. >> I do not think so: 1/2 = 0.1 = sum( n>=2, n/(n+1)! ) The problem (same as 1.0 = 0.999.. ) stays with all mixed radix representations. For uniqueness I'd should check non-adjacent forms (no two adjacent digits nonzero), e.g., digits 0,+1,-1 in binary. >> ________________________________________________________________________________________ It goes without saying that .

2 1

[math-fun] hyperelliptic curves and AGM?
by Warren Smith 02 Jan '12

02 Jan '12

Victor Miller's cite of PhD thesis by Robert Carls was pretty useless to me -- seems to be a hellish marriage of number theory and topology (??!) without what I wanted, which is complex or real analysis. It seems amazing that they've somehow translated Gauss's AGM into the p-adic number theory world and now use it to do things like count points on finite field versions of "curves"... but at the same time, for mundane analysis purposes this seems useless. However, google then revealed these papers: Takayuki Kato and Keiji Matsumoto: http://www.math.sci.hokudai.ac.jp/~matsu/pdf/FD.pdf we define a (generalized) arithmetic-geometric mean among four terms and express it by Lauricella’s hypergeometric function FD of three variables. Kenji Koike & Hironori Shiga: http://mitizane.ll.chiba-u.jp/metadb/up/irtoroku2/06001.pdf A 3-variable AGM-like iteration yields a certain hyperelliptic integral, also an Appell 2-variable hypergeometric fn. There also are other papers by these same authors. They seem to in some of them be claiming a more general theory. This all seems an impressive breakthrough in analysis which probably will (or should) lead to various new "superfast" algorithms. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 5

Re: [math-fun] Fracfac expansions (fractions in factorial base)
by Dan Asimov 01 Jan '12

01 Jan '12

Using mere long doubles in C, here are the fracfac coefficients that I believe, for 1/p, p prime <= 19. Apparently, we always have: a) (p-1)/2 is the coefficient of 1/(p-2)! (for p > 3), b) 0 is the coefficient of 1/(p-1)!, and c) p-1 is the coefficient of 1/p!. Can someone give a nice proof of these apparent patterns? --Dan coefficient of 1/factorial of 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ------------------------------------------------------------------------------------------------------------- prime p ------- 2: 1 3: 0 2 5 0 1 0 3 7: 0 0 3 2 0 6 11: 0 0 2 0 5 3 1 4 0 10 13: 0 0 1 4 1 2 5 4 8 5 0 12 17: 0 0 1 2 0 2 3 6 8 9 0 9 2 7 0 16 19: 0 0 1 1 1 6 2 0 9 5 2 6 11 11 13 8 0 18 ------------------------------------------------------------------------------------------------------------- coefficient of 1/factorial of 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 I wrote: << . . . [E]very x in (0,1) has a unique representation of the form x = Sum_{n=1..oo} c_n/(n+1)! if the integers c_n satisfy 0 <= c_n <= n. . . . >> ________________________________________________________________________________________ It goes without saying that .

2 1

Re: [math-fun] Heron tetrahedra: Proof of 3D integer-lattice posability
by Warren Smith 01 Jan '12

01 Jan '12

This is the same as my old 3D posability proof I posted before, but with some typos and poor writing corrected (think only about 5 characters changed, but they were characters with high confusion potential :) ===================Warren=D=Smith=====Dec=2011============== A "heron tetrahedron" is one with integer edge lengths, face-areas, and volume. Fred Lunnon and Jan Fricke both conjectured, both based on considerable computer evidence, that every Heron tetrahedron could be rotated & translated so that all its vertices had integer xyz coordinates. Indeed, Lunnon has now found at least one such "integer lattice pose" for every Heron tetrahedron with diameter<100,000. In this post, I will prove their conjecture. Idea behind proof: 3D integer lattice points will be regarded as "Lipshitz quaternions" i.e. integer linear combinations of 1,i,j,k, where i*j=-j*i=k, j*k=-k*j=i, k*i=-i*k=j, i^2=j^2=k^2=-1. Fact: Any 3-dimensional (zero real part) Lipshitz quaternion E with integer length |E|, if scaled up by 2 times its length to get 2*|E|*E, becomes a square. Proof: Let R=|E|+E. Then R^2 = 2*|E|*E where E can be any pure-imaginary Lipshitz with integer length. QED Conjugation: R~ denotes quaternion conjugate: (A+Bi+Cj+Dk)~=(A-Bi-Cj-Dk). About R as a rotation map X --> R~ X R: this causes 2*|E|*E = R^2 to map to R~ R R R = |R|^2 R R = |R|^2 *2*|E|*E which lies on the integer 3D lattice times 2*|E|*|R|^2. Proof of integer pose existence theorem: Initially pose the tetrahedron so 3 of its vertices lie on the 2D integer lattice in the xy plane. (This can be done, as was prove in earlier posts using Gaussian integer GCD as a tool.) The remaining 4th vertex is easily seen to have rational xyz coordinates (as a consequence of edge, area, and volume integrality). Let L=LCM(denominators). Upscale your tetrahedron by L so it is integer posed but nonprimitive. All edge lengths now divisible by L. All vertices but one (namely E) now are on lattice*L and E is on lattice. Compute R=|E|+E. Upscale tet again by 2*|E|. All vertices but one (namely newE=E') now are on lattice*2*|E|*L while E' has been put on lattice*2*|E|. Apply rotation map X --> R~ X R to all tet vertices X. Now still integer posed, and now E' is on lattice*2*|E|*|R|^2 and all other vertices on lattice*2*|E|*L. Now we can safely de-scale by a factor of 2*|E|*GCD(|R|^2, L) and still everything on integer lattice. But |R|^2=4*|E|^2 is divisible by L since |E|=integer*L. So the de-scaling factor is 2*|E|*L. But that was precisely the net upscaling factor in the first place. So the net effect has been a rotation without any rescaling, and it has made everything integer-lattice-posed. QED. In fact to do this I did not need to have a Heron tetrahedron. It sufficed if all vertices but one initially Lipshitz, and that one exception initially rational with length=integer. Notice we never even had to use quaternion-GCD anywhere and this proof works in 3D only. Finally, Lunnon & I have reason to suspect that eventually, for very large Heron tetrahedra (even primitive ones) there will often be many integer poses, i.e. arbitrarily high nonuniqueness. This contrasts with the 2D situation for Heron triangles.

1 0

[math-fun] Gamma function (formulas collection)
by Warren Smith 01 Jan '12

01 Jan '12

many formulas about gamma function are in my paper: http://rangevoting.org/WarrenSmithPages/homepage/gammprox.pdf

3 3