March 2014 - mathfun@mailman.xmission.com

[math-fun] reversing the order of bits in a word
by Bill Gosper 16 Apr '14

16 Apr '14

WDS> Let w be a 64-bit word ("unsigned long long," in C language). The following C instruction sequence w ^= w>>32; w ^= w<<32; w ^= w>>32; w ^= w>>16; w ^= w<<16; w ^= w>>16; w ^= w>>8; w ^= w<<8; w ^= w>>8; w ^= w>>4; w ^= w<<4; w ^= w>>4; w ^= w>>2; w ^= w<<2; w ^= w>>2; w ^= w>>1; w ^= w<<1; w ^= w>>1; will overwrite w with its bit-order-reversal. In general for a (2^k)-bit long word this will use 3*k shifts and 3*k XOR operations and with zero(?) or one(?) extra registers consumed for temp storage and no funny masking constants needed. -- Warren D. Smithhttp://RangeVoting.org Knuth Vol 4A, 7.1.3 has 70 pages on Bitwise Tricks and Techniques. Page 144 is Bit reversal, and may anticipate you here--I haven't read closely enough to determine. (Probably not, if Tom Karzes's "all 1s" objection resists debugging!) Certainly most of Knuth's hacks require "funny masking constants" (whose objectionability I fail to perceive). Probably the most important lesson in 7.1.3 is Knuth's strong advocacy of his MOR and MXOR (8×8 bitmatrix) instructions for inclusion in 64-bit order codes. Bit reversal takes two MORs. --rwg After Bit reversal comes Bit swapping, in which my hasty perusal fails to find the TRCE TRCE TRCE trick (HAKMEM Item 162), of which Knuth was once quite fond. It is perhaps too platform dependent? I'd think he would cite TRCE etc as ideas for future order codes, but perhaps instruction skipping is a thing of the past.

4 3

[math-fun] BarnesG and Hyperfactorial of n/4 and n/6
by Bill Gosper 14 Apr '14

14 Apr '14

Papers of mine and your own Victor Adamchik give Integrate[Log[Gamma[t]],{t,0,r}] for various rational r. We also give this integral in terms of BarnesG. But FunctionExpand[BarnesG[r]] only "works" for r=n/2, which it gives in terms of the goddam useless Glaisher symbol. Zeta'[-1] spontaneously turns into 1/12 - Log[Glaisher]. Why?? Why not then arbitrarily smash every Zeta[3] to be Apery? Or Apéry, to make it harder to type. Here are G[1/3] and -1/3 with z1 for Zeta[-1], to avoid the Glaisher braindamage. Out[67]= {BarnesG[1/3] -> 3^(25/72)* E^((1/72)*(96*z1 + (Sqrt[3]*(-PolyGamma[1, 1/3] + PolyGamma[1, 2/3]))/Pi))* Gamma[1/3]^(1/Gamma[4/3])*Gamma[4/3]^(4/3), BarnesG[-(1/3)] -> 3^(1/72)* E^((1/72)*(96*z1 + (Sqrt[3]*(PolyGamma[1, 1/3] - PolyGamma[1, 2/3]))/Pi))* Gamma[-(1/3)]^(1/Gamma[2/3])* Gamma[2/3]^(2/3)} In[68]:= Zeta'[-1] Out[68]= 1/12 - Log[Glaisher] FunctionExpand also appears to disunderstand the tuplication formula Product[Hyperfactorial[-(i/n) + z], {i, 0, -1 + n}] == (E^(z1/n - n*z1)*Hyperfactorial[n*z]^(1/n))/ n^((1 + 6*n*z + 6*n^2*z^2)/(12*n)) whose need it artificially creates for itself when given the Alternating Sign Matrix formula In[171]:= FunctionExpand[Product[(3 k + 1)!/(n + k)!, {k, 0, n - 1}], n > 0 && n \[Element] Integers] Out[171]= (3^(2 - 5 n + 3/2 n (1 + n)) 8^(-1 + n) (BarnesG[5/3] BarnesG[7/3])^(-2 + n) (BarnesG[8/3] BarnesG[10/3])^(1 - n) BarnesG[2/3 + n] BarnesG[1 + n] BarnesG[4/3 + n] BarnesG[2 + n]^( 2 - n) BarnesG[3 + n]^(-1 + n) Gamma[2 + n]^( 1 - n))/(BarnesG[1 + 2 n] Gamma[1 + n]) In[175]:= FunctionExpand[Table[%171, {n, 5}]] Out[175]= {1, 2, ( 9 BarnesG[5/3] BarnesG[7/3] BarnesG[11/3] BarnesG[13/3])/( 5 BarnesG[8/3]^2 BarnesG[10/3]^2), ( 2187 BarnesG[5/3]^2 BarnesG[7/3]^2 BarnesG[14/3] BarnesG[16/3])/( 7000 BarnesG[8/3]^3 BarnesG[10/3]^3), ( 1594323 BarnesG[5/3]^3 BarnesG[7/3]^3 BarnesG[17/3] BarnesG[19/3])/( 274400000 BarnesG[8/3]^4 BarnesG[10/3]^4)} This is an integer sequence! (A005130, 1,2,7,42,...). --Bill Gosper In[71]:= $LicenseID Out[71]= "L3290-7570"

1 1

[math-fun] Nines in Pi
by James Propp 11 Apr '14

11 Apr '14

Is it possible that for some n, the n+1st through 2nth digits of pi are all 9's? Dick Hess just gave a wonderful G4G talk which raised this issue. Jim

5 4

[math-fun] Knight-distance metric in chess
by Warren D Smith 07 Apr '14

07 Apr '14

Consider a bi-infinite chessboard (Z^2). What is the distance between (x1,y1) and (x2,y2) measured in number of knight-moves? [Incidentally, for a finite hXw chessboard, if min(h,w)>3 the bi-infinite and finite board exhibit the same distances in all cases except if the two squares are the corner of the board and diagonally adjacent to it, in which case the finite board has distance=4 while the bi-infinite board distance is 2.] After some fiddling, I came up with the following CONJECTURE: Define dx = |x1-x2|, dy = |y1-y2|, L1distance = dx + dy, KingDistance = max(dx, dy) F = ( max(2*L1distance, 3*KingDistance) + 4 ) / 6 Then KnightDistance = F rounded to the nearest eligible integer of the correct parity (correct parity: even if source and destination same-colored squares, otherwise odd) (eligible: must be non-negative, and if the two squares differ then must be positive) except for this list: (dx,dy) KnightDistance Formula (1,0) or (0,1) 3 1 (2,2) 4 2 (7,7) 4 6 in which my formula is off by 2. Are there any other exceptions? -- Warren D. Smith http://RangeVoting.org

10 20

[math-fun] matrix group with bounded eigenvalues
by Fred Lunnon 03 Apr '14

03 Apr '14

Given a finite set of complex matrices generating an infinite group, I need to establish that every element of the group has all eigenvalues within the unit circle. Such problems must have been well investigated --- perhaps (shudder) by math physicists --- but I have no idea where to start looking. [It's actually a semigroup of integer matrices with constraints on allowed products, and circle radius exponential in the number of product factors --- but those details are almost certainly unimportant.] WFL

5 8

[math-fun] HAKMEM Item 1
by Bill Gosper 01 Apr '14

01 Apr '14

ITEM 1 (Schroeppel): (1/3)! and (2/3)! are interexpressible. (1/4)! and (3/4)! are interexpressible. Thus these two pairs are of dimensionality one. (1/10)! and (2/10)! are sufficient to express (N/10)! for all N. (1/12)! and (2/12)! are sufficient to express (N/12)! for all N. (1/3)! and (1/4)! are sufficient to express (N/12)! for all N. Thus the three cases above are of dimensionality two. PROBLEM: Find some order to this dimensionality business. The reflection and multiplication formulas: pi Z Z! (-Z)! = --------- sin(pi Z) (N-1)/2 -NZ-1/2 (2 pi) N (NZ)! = Z! (Z-1/N)! (Z-2/N)! ... (Z-(N-1)/N)! -------------- I was under the misimpression that Mathematica had finally nailed this, but using LR[L_, N_] := Block[{$MaxExtraPrecision = N}, LatticeReduce[ Transpose[Prepend[IdentityMatrix[Length[L]], Round[10^N*L]]]]] (LR for Lattice Reduce or Linear Relation), which finds multiple solutions, unlike FindIntegerNullVector (PSLQ), to find relations among (k/12)! : In[17]:= Join[{2, 3, 5}, (Range[6]/12)!] Out[17]= {2, 3, 5, (1/12)!, (1/6)!, (1/4)!, (1/3)!, (5/ 12)!, Sqrt[\[Pi]]/2} In[18]:= LR[Log[%], 69][[1 ;; 3]] Out[18]= {{0, 6, -1, -2, 2, 3, -4, -6, 2, 3}, {-6, -2, 7, -4, 4, 0, -8, 0, 4, 0}, {-29420553, 655434586, 1447298892, -1344266042, -1749889224, 1253758671, 366295186, 83356101, -1110973039, -416024934}} In[19]:= Rest /@ %[[1 ;; 2]].Transpose[{Log[%%]}] Out[19]= {{6 Log[2] - Log[3] - 2 Log[5] + 3 Log[Sqrt[\[Pi]]/2] + 2 Log[(1/12)!] + 3 Log[(1/6)!] - 4 Log[(1/4)!] - 6 Log[(1/3)!] + 2 Log[(5/12)!]}, {-2 Log[2] + 7 Log[3] - 4 Log[5] + 4 Log[(1/12)!] - 8 Log[(1/4)!] + 4 Log[(5/12)!]}} In[20]:= First /@ Simplify[E^%] Out[20]= {(8 \[Pi]^(3/2) ((1/12)!)^2 ((1/6)!)^3 ((5/12)!)^2)/( 75 ((1/4)!)^4 ((1/3)!)^6), (2187 ((1/12)!)^4 ((5/12)!)^4)/( 2500 ((1/4)!)^8)} In[21]:= N[%] Out[21]= {1., 1.} In[22]:= MapAt[#^(1/4) &, %%, 2] Out[22]= {(8 \[Pi]^(3/2) ((1/12)!)^2 ((1/6)!)^3 ((5/12)!)^2)/( 75 ((1/4)!)^4 ((1/3)!)^6), (3 3^(3/4) (1/12)! (5/12)!)/( 5 Sqrt[2] ((1/4)!)^2)} In[23]:= Numerator[#] == Denominator[#] & /@ % Out[23]= {8 \[Pi]^(3/2) ((1/12)!)^2 ((1/6)!)^3 ((5/12)!)^2 == 75 ((1/4)!)^4 ((1/3)!)^6, 3 3^(3/4) (1/12)! (5/12)! == 5 Sqrt[2] ((1/4)!)^2} In[24]:= FullSimplify[FunctionExpand[%]] /. Gamma[z_] -> (z - 1)! Out[24]= {75 (1/4)!^4 (1/3)!^6 == 8 π^(3/2) (1/12)!^2 (1/6)!^3 (5/12)!^2, 5 Sqrt[2] (1/4)!^2 == 3 3^(3/4) (1/12)! (5/12)!} In[25]:= N[%] Out[25]= {True, True} Is this really that hard a problem? If we can "sort" these, we should move on to the higher factorials (e.g. BarnesG and Hyperfactorial), which have analogous reflection and tuplication formulæ. gosper.org/facfun.pdf . (Recall Date 2014-03-11 02:53 FunctionExpand also appears to disunderstand the tuplication formula Product[Hyperfactorial[-(i/n) + z], {i, 0, -1 + n}] == (E^(z1/n - n*z1)*Hyperfactorial[n*z]^(1/n))/ n^((1 + 6*n*z + 6*n^2*z^2)/(12*n)) whose need it artificially creates for itself when given the Alternating Sign Matrix formula In[171]:= FunctionExpand[Product[(3 k + 1)!/(n + k)!, {k, 0, n - 1}], n > 0 && n \[Element] Integers] Out[171]= (3^(2 - 5 n + 3/2 n (1 + n)) 8^(-1 + n) (BarnesG[5/3] BarnesG[7/3])^(-2 + n) (BarnesG[8/3] BarnesG[10/3])^(1 - n) BarnesG[2/3 + n] BarnesG[1 + n] BarnesG[4/3 + n] BarnesG[2 + n]^( 2 - n) BarnesG[3 + n]^(-1 + n) Gamma[2 + n]^( 1 - n))/(BarnesG[1 + 2 n] Gamma[1 + n]) ) --rwg Old business: I was unable to reproduce that -2=-1 hypergeometric mess for Wolfram's troubleshooters. Now I get a slightly smaller mess which seems numerically correct.

3 5

[math-fun] Origami URLs
by Fred Lunnon 31 Mar '14

31 Mar '14

Stephen Brown of NUIM sends the following origami references: >> The folding antenna was by Robert Lang: http://www.langorigami.com/ > > Much of interest here --- I was unaware of the Justin axioms, not to mention > the solution of quintic equations via non-elementary folds! > >> The NASA paper aeroplance was "Arturo's Desert Eagle": >> http://www.telegraph.co.uk/news/newstopics/howaboutthat/9162771/Giant-paper… > > Thanks, but I think I prefer to take the train ... > >> Just saw this - origami using steel sheets: >> http://rspa.royalsocietypublishing.org/content/early/2011/03/25/rspa.2011.0… Just in case you ever have a requirement for an armour-plated shopping-bag! [But do not try putting p.13 on a Powerpoint slide.] WFL

1 0

[math-fun] Solving (c7) [Was: <Glaisher flame>]
by Bill Gosper 31 Mar '14

31 Mar '14

BTW, I'm having difficulty solving (c7) for F , wot does not appear in the equation ... Has my belt fallen down? WFL Thanks for reminding. I've yet to figure out how to stop html from randomly changing ϕ to f and Φ to F. NOW what color is your belt? --rwg On 3/30/14, Bill Gosper <billgosper(a)gmail.com> wrote: in http://www.tweedledum.com/rwg/idents.htm that Dick Askey once deemed "wild". Unfortunately, using that bleeping useless Glaisher symbol instead of Zeta'[-1], which it bashes to 1/12 - Log[Glaisher]. This is like bashing Zeta[3] to Apéry. Zeta'[-1] is also simply related to Porter's constant, so why doesn't Mma call it (some function of) Porter? Since it comes up in Hyperfactorial[1/2] and BarnesG[1/2], I used to advocate the symbol π_1, where π_0 := π, but, so far at least, Mma doesn't support Hyperfactorial[n,k] := 1^1^k 2^2^k ... n^n^k. In the past, and on that page, I used Zeta'[2], but that is almost always clumsier. Best for that identity is probably Product[n!*(n/E)^-n/Sqrt[2*π*(n + 1/6)], {n, ∞}] == E^(-(1/12)+2 (Zeta'[-1]) (2 π)^(1/4) Sqrt[(1/6)!]. Can someone emit a rule to melt Glaishers? --rwg

2 1

[math-fun] reversing the order of bits in a word
by Bill Gosper 31 Mar '14

31 Mar '14

wds>Knuth gave the following absolutely incredible algorithm, here as C which I tested: //Don Knuth incredible algorithm for reversing a 64-bit word x: uint64 y; x = ((x>>1) & U64(0x5555555555555555)) | ((x & U64(0x5555555555555555)) << 1); y = (x ^ (x>>4)) & U64(0x0300C0303030C303); x ^= y ^ (y<<4); y = (x ^ (x>>8)) & U64(0x00C0300C03F0003F); x ^= y ^ (y<<8); y = (x ^ (x>>20)) & U64(0x00000FFC00003FFF); x ^= y ^ (y<<20); x = (x>>34) | (x<<30); return(x); Good luck figuring it out. And what are the 8, 16, and 32-bit versions of it (if any)? <WDS The Symbolics Lisp Machine (and many of its contemporaries) had a BITBLT (Bit block transfer) instruction capable of Boolean functions on rectangular bit arrays. Our usual test subject was a 1 bit/pixel frame of a Zippy the Pinhead strip. I wrote a little demo called Thrash-Zippy which iteratively subjected this to various BITBLTcherous flips and rotations, the most interesting of which was a bitmatrix transpose (swap-xy), which took k1 lg n for n×n, and used lg n n×n masks, each of which I'm pretty sure took k2 lg n to compute. The kth mask designated all those bits which needed to switch with their counterparts 2^k to their northwest. I recall it startling Leo Guibas, who was writing a computational geometry book at the time, so maybe he wrote it up. Funster Stephen Jones has copies of my old files. I think the functions were in a file named bltfun. --rwg

1 0

Re: [math-fun] reversing the order of bits in a word
by Henry Baker 30 Mar '14

30 Mar '14

Given Intel's close relationship with un-named agencies, how do you know that bit reverse, and a lot of other instructions, aren't already "standard" (but whose existence is classified) ? So long as an instruction doesn't require new datapaths, it would be nearly impossible to notice its existence in a chip mask. The existence of the AES instruction is an obvious (unclassified) example of this type of extension. http://en.wikipedia.org/wiki/AES_instruction_set There are companies that can reverse engineer chips by shaving them layer by layer, and eventually reconstruct their netlists. But this may be quite difficult at the bleeding edge of the latest technologies. It may well be that there are a number of Snowden disclosures that appear so bizarre that the journalists can't figure out what they mean; references to obscure instructions might well fall into this class. At 02:03 PM 3/28/2014, Eugene Salamin wrote: >>Due to it's utility in FFT, I'm surprised that bit reverse is not a standard instruction.

3 2