February 2012 - mathfun@mailman.xmission.com

[math-fun] OK, I programmed my proposed psu-random generator....
by Warren Smith 07 Feb '12

07 Feb '12

Will it pass the SuperCrush U01 tests? How fast will it be? http://www.iro.umontreal.ca/~simardr/testu01/tu01.html I have not run it thru randomness tests, but I crudely timed it for NumWordsInState=4 (period=2^256) on 64-bit iMac 2.0GHz, finding it produced random 64-bit words at a rate of 1 billion in 12 seconds, which is 3 cycles per random byte. Perhaps fiddling with the code and compiler would make it go faster? I manually unrolled loop and replaced the state 4-vector by 4 scalars; that sped it up to under 11 seconds. Another idea is to output more than one random word each time, which might mean you need a larger state vector but still in net could yield a speedup... --- #include <stdint.h> #include <stdio.h> //Warren D. Smith attempt at making psu-random generator. Compile with // gcc WarrenRand.c -Wall -O6 -o WarrenRand #define uint unsigned int #define uint32 uint32_t #define uint64 uint64_t #define uint128 __uint128_t #define RandStrideConst 14923729446516375051ull //must be odd //The below is written for a 64-bit machine. //If you have 32-bit machine then text-replace 64-->32 and then 128-->64 throughout the following: //period will be 2^(64 * NumWordsInState), increase for more randomness but slower runtime: #define NumWordsInState 4 inline uint64 UpdatorF(uint64 x){ uint128 y; y = x; x >>= (64-1); y *= y; x += y ^ (y>>64); return(x); } uint64 statevec[NumWordsInState]; uint64 Rand64(){ uint i; uint64 v; v = statevec[0]; for(i=NumWordsInState-1; i>0; i--){ //can be unrolled and all loop iterations run parallel v ^= statevec[i]; statevec[i] += UpdatorF(statevec[i-1]); } statevec[0] += RandStrideConst; return(v); //returns the XOR of all words in state vector } main(){ uint i; for(i=0; i<9999; i++){ Rand64(); } //warm it up for(i=0; i<99; i++){ printf("%llx\n", Rand64()); } //print some random machine words }

5 5

[math-fun] simple pleasures: subset-lex Gray code
by Warren Smith 07 Feb '12

07 Feb '12

I would like to do the following. GIven N items, each having a user-pre-specified positive integer "weight", I want to generate all subsets of the N items, whose sum-of-weights lies within a user-specified interval [Lo, Hi]. And I want to do it in some kind of low-change Gray-code-like order. The "weighted subset generation problem."

2 1

[math-fun] simple pleasures: subset-lex Gray code
by Joerg Arndt 07 Feb '12

07 Feb '12

>From the department of ASCII entertainment: a binary Gray code you have not seen before. Dots for zeros to make the structure more visible. n: Gray code transition 0: [ . . . . . . ] ---- 1: [ 1 . . . . . ] 1..... 2: [ 1 1 . . . . ] .1.... 3: [ 1 1 1 . . . ] ..1... 4: [ 1 1 1 1 . . ] ...1.. 5: [ 1 1 1 1 1 . ] ....1. 6: [ 1 1 1 1 1 1 ] .....1 7: [ 1 1 1 1 . 1 ] ....1. 8: [ 1 1 1 . . 1 ] ...1.. 9: [ 1 1 1 . 1 1 ] ....1. 10: [ 1 1 1 . 1 . ] .....1 11: [ 1 1 . . 1 . ] ..1... 12: [ 1 1 . . 1 1 ] .....1 13: [ 1 1 . . . 1 ] ....1. 14: [ 1 1 . 1 . 1 ] ...1.. 15: [ 1 1 . 1 1 1 ] ....1. 16: [ 1 1 . 1 1 . ] .....1 17: [ 1 1 . 1 . . ] ....1. 18: [ 1 . . 1 . . ] .1.... 19: [ 1 . . 1 1 . ] ....1. 20: [ 1 . . 1 1 1 ] .....1 21: [ 1 . . 1 . 1 ] ....1. 22: [ 1 . . . . 1 ] ...1.. 23: [ 1 . . . 1 1 ] ....1. 24: [ 1 . . . 1 . ] .....1 25: [ 1 . 1 . 1 . ] ..1... 26: [ 1 . 1 . 1 1 ] .....1 27: [ 1 . 1 . . 1 ] ....1. 28: [ 1 . 1 1 . 1 ] ...1.. 29: [ 1 . 1 1 1 1 ] ....1. 30: [ 1 . 1 1 1 . ] .....1 31: [ 1 . 1 1 . . ] ....1. 32: [ 1 . 1 . . . ] ...1.. 33: [ . . 1 . . . ] 1..... 34: [ . . 1 1 . . ] ...1.. 35: [ . . 1 1 1 . ] ....1. 36: [ . . 1 1 1 1 ] .....1 37: [ . . 1 1 . 1 ] ....1. 38: [ . . 1 . . 1 ] ...1.. 39: [ . . 1 . 1 1 ] ....1. 40: [ . . 1 . 1 . ] .....1 41: [ . . . . 1 . ] ..1... 42: [ . . . . 1 1 ] .....1 43: [ . . . . . 1 ] ....1. 44: [ . . . 1 . 1 ] ...1.. 45: [ . . . 1 1 1 ] ....1. 46: [ . . . 1 1 . ] .....1 47: [ . . . 1 . . ] ....1. 48: [ . 1 . 1 . . ] .1.... 49: [ . 1 . 1 1 . ] ....1. 50: [ . 1 . 1 1 1 ] .....1 51: [ . 1 . 1 . 1 ] ....1. 52: [ . 1 . . . 1 ] ...1.. 53: [ . 1 . . 1 1 ] ....1. 54: [ . 1 . . 1 . ] .....1 55: [ . 1 1 . 1 . ] ..1... 56: [ . 1 1 . 1 1 ] .....1 57: [ . 1 1 . . 1 ] ....1. 58: [ . 1 1 1 . 1 ] ...1.. 59: [ . 1 1 1 1 1 ] ....1. 60: [ . 1 1 1 1 . ] .....1 61: [ . 1 1 1 . . ] ....1. 62: [ . 1 1 . . . ] ...1.. 63: [ . 1 . . . . ] ..1... Note successive transitions are either adjacent (one-close) or three-close. Guessing the recursion may be a fun task (there is a twist wrt. to the "well known" recursions). Hint: this Gray code is to (subset-lex)... n: delta-set subset 0: ..... { } 1: 1.... { 0 } 2: 11... { 0, 1 } 3: 111.. { 0, 1, 2 } 4: 1111. { 0, 1, 2, 3 } 5: 11111 { 0, 1, 2, 3, 4 } 6: 111.1 { 0, 1, 2, 4 } 7: 11.1. { 0, 1, 3 } 8: 11.11 { 0, 1, 3, 4 } 9: 11..1 { 0, 1, 4 } 10: 1.1.. { 0, 2 } 11: 1.11. { 0, 2, 3 } 12: 1.111 { 0, 2, 3, 4 } 13: 1.1.1 { 0, 2, 4 } 14: 1..1. { 0, 3 } 15: 1..11 { 0, 3, 4 } 16: 1...1 { 0, 4 } 17: .1... { 1 } 18: .11.. { 1, 2 } 19: .111. { 1, 2, 3 } 20: .1111 { 1, 2, 3, 4 } 21: .11.1 { 1, 2, 4 } 22: .1.1. { 1, 3 } 23: .1.11 { 1, 3, 4 } 24: .1..1 { 1, 4 } 25: ..1.. { 2 } 26: ..11. { 2, 3 } 27: ..111 { 2, 3, 4 } 28: ..1.1 { 2, 4 } 29: ...1. { 3 } 30: ...11 { 3, 4 } 31: ....1 { 4 } .. what the usual (binary reflected) Gray code ist to binary numbers in counting order. Can be generalized to mixed radix numbers (and for even radices >=4 the transitions are either adjacent or two-close) and a loopless algorithm that does _not_ use any sort of focus pointers can be obtained (which is actually very fast). One-close binary Gray codes exist for n<=6 but not for n=7 (and apparently not for any n>=8). Finding a construction for two-close binary Gray code would be _very_ neat. ...and subset-lex gives fast (loopless) methods for generating non-adjacent forms, here is the Fibonacci case: 0: ........ = { } 1: 1....... = { 0 } 2: 1.1..... = { 0, 2 } 3: 1.1.1... = { 0, 2, 4 } 4: 1.1.1.1. = { 0, 2, 4, 6 } 5: 1.1.1..1 = { 0, 2, 4, 7 } 6: 1.1..1.. = { 0, 2, 5 } 7: 1.1..1.1 = { 0, 2, 5, 7 } 8: 1.1...1. = { 0, 2, 6 } 9: 1.1....1 = { 0, 2, 7 } 10: 1..1.... = { 0, 3 } 11: 1..1.1.. = { 0, 3, 5 } 12: 1..1.1.1 = { 0, 3, 5, 7 } 13: 1..1..1. = { 0, 3, 6 } 14: 1..1...1 = { 0, 3, 7 } 15: 1...1... = { 0, 4 } 16: 1...1.1. = { 0, 4, 6 } 17: 1...1..1 = { 0, 4, 7 } 18: 1....1.. = { 0, 5 } 19: 1....1.1 = { 0, 5, 7 } 20: 1.....1. = { 0, 6 } 21: 1......1 = { 0, 7 } 22: .1...... = { 1 } 23: .1.1.... = { 1, 3 } 24: .1.1.1.. = { 1, 3, 5 } 25: .1.1.1.1 = { 1, 3, 5, 7 } 26: .1.1..1. = { 1, 3, 6 } 27: .1.1...1 = { 1, 3, 7 } 28: .1..1... = { 1, 4 } 29: .1..1.1. = { 1, 4, 6 } 30: .1..1..1 = { 1, 4, 7 } 31: .1...1.. = { 1, 5 } 32: .1...1.1 = { 1, 5, 7 } 33: .1....1. = { 1, 6 } 34: .1.....1 = { 1, 7 } 35: ..1..... = { 2 } 36: ..1.1... = { 2, 4 } 37: ..1.1.1. = { 2, 4, 6 } 38: ..1.1..1 = { 2, 4, 7 } 39: ..1..1.. = { 2, 5 } 40: ..1..1.1 = { 2, 5, 7 } 41: ..1...1. = { 2, 6 } 42: ..1....1 = { 2, 7 } 43: ...1.... = { 3 } 44: ...1.1.. = { 3, 5 } 45: ...1.1.1 = { 3, 5, 7 } 46: ...1..1. = { 3, 6 } 47: ...1...1 = { 3, 7 } 48: ....1... = { 4 } 49: ....1.1. = { 4, 6 } 50: ....1..1 = { 4, 7 } 51: .....1.. = { 5 } 52: .....1.1 = { 5, 7 } 53: ......1. = { 6 } 54: .......1 = { 7 } Generating the list in reverse order can be done via... ulong prev_lexrev_fib(ulong x) // Return previous Fibonacci word in subset-lex order. // Start with zero to generate all words of length n. { ulong x0 = x & -x; // lowest bit if ( x & (x0<<2) ) // easy case: next higher bit is set { x ^= x0; // clear lowest bit return x; } else { x += x0; // move lowest bit to the left x |= (x0!=1); // and set rightmost bit unless blocked by next bit return x; } } ...which, ladies and gentlemen, ist werry beautiful! [He bows and leaves the stage. Deafening silence in the audience.]

1 1

[math-fun] just plugging in can be dangerous
by Bill Gosper 07 Feb '12

07 Feb '12

z/((z + 1 - Sqrt[2])^2 - 3 + 2*Sqrt[2]) In[689]:= % /. z -> 0 Out[689]= 0 (No 0/0 warning.) In[690]:= Limit[%%, z -> 0] Out[690]= -1/2 - 1/Sqrt[2] This can get much subtler. I'm surprised how rarely it bites us. --rwg

1 0

Re: [math-fun] about pdf readers
by Henry Baker 07 Feb '12

07 Feb '12

If you want to see some of the cr*p that these bloated packages load (at least on Windows), do a Google search for "Windows" "autoruns", download it and run it. This little program will allow you to see & disable a huge number of background processes that are loaded by default. Apple is one of the worst, but Adobe is right behind them, in starting up all kinds of background processes that chew up memory and processor. You should easily be able to cut the number of these background processes in half, and also reduce your boot time significantly. You really don't need a separate process for every single software package whose entire job it is to look for an update for that package. The most obvious thing to do is to look for an update when the program runs; if you never run the program, you obviously don't need the update. (You'd think by now that Windows would have a single process that looked for updates for all packages, but that would be too easy.) I just got an HP machine & spent an entire day cleaning out all of the HP-related junk that didn't do any better job than the standard Microsoft software that it was trying to displace. At 03:46 PM 2/5/2012, Robert Munafo wrote: >The reason we lose more performance than Moore's law gives back is because >there are so many programmers (undeserving of the title "software >engineers") who would rather use some huge, unoptimal software package or >library than spending days, weeks or even years learning how to do it >efficiently. (Market forces play a role too :-) > >On Sun, Feb 5, 2012 at 09:09, Joerg Arndt <arndt(a)jjj.de> wrote: > >> * Henry Baker <hbaker1(a)pipeline.com> [Feb 05. 2012 14:48]: >> > There are now some free pdf reader apps that are about 1/10th the size >> of Adobe Reader. >> >> [In Adobe Reader] You can disable Javascript by renaming some directory >> in the installation btw. (could not find out what the >> name is in <=60 secs). > >Wikipedia says: [To] disable JavaScript in Adobe Reader [...] [use] the >General preferences dialog (Edit, Preferences, JavaScript, and un-check >"Enable Acrobat JavaScript"). > >And there is xpdf: executable < 300kB (but loads a couple >> of dynamic libs). Memory footprint about 13MB on my system: > >Ghostscript is useful too. xpdf and ghostscript are both available to Mac >users via Macports > >[...] > >acroread used to be better in "repairing" broken pdfs, >> nowadays it has clearly lost it's lead in this respect. >> >> Still, some documents, notable scanned books from arxiv, >> take bloody ages (>10secs) to render a single page. Somehow >> we are losing more performance over time than Moore's law >> gives us. >> >> -- > Robert Munafo -- mrob.com > Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - >mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com

6 5

Re: [math-fun] about pdf readers
by Axel Vogt 06 Feb '12

06 Feb '12

On 06.02.2012 03:33, math-fun-request(a)mailman.xmission.com wrote: > Date: Sun, 5 Feb 2012 18:46:26 -0500 > From: Robert Munafo<mrob27(a)gmail.com> > To: math-fun<math-fun(a)mailman.xmission.com> > Subject: [math-fun] about pdf readers ... On Win I case of doubts I use Sumatra, which handles other formats as well (djvu or postscript and more). http://blog.kowalczyk.info/software/sumatrapdf/free-pdf-reader.html For killing Windows sniffing http://xp-antispy.org/ or similar give good and easy solutions (besides those already stated).

1 0

[math-fun] A pentatope (not Heronian --- relax!)
by Fred lunnon 06 Feb '12

06 Feb '12

Consider the 4-space simplex PQRST having edge-lengths QP = 1, RP = sqrt(2), RQ = sqrt(2), SP = sqrt(3), SR = sqrt(3), SQ = sqrt(3), TP = 2, TQ = sqrt(2), TR = 1, TS = 1. Let lattice vertices be labelled even / odd according to the sum of their Cartesian coordinate components. The triangle PQR has sides 1,sqrt(2),sqrt(2): if it is embedded in the lattice with P is even then Q is odd, so R is odd, so P is odd. By contradiction, it must be impossible to embed PQRST in the lattice |Z^4. However, PQRST does have the rational embedding in |Q^4 P = [0,0,0,0], Q = [0,0,0,1], R = [1,0,1,0], S = [1,1,0,0], T = [5,1,1,0]/3. Why am I telling you this? The proofs that a Heronian simplex is lattice embeddable in 2 and 3 dimensions require only that the simplex be rationally embedded, and have edge lengths squaring to integers. This example shows that any proof of Heronian embeddability in |Z^4 would have to somehow involve extra properties besides these two. [That's always assuming, of course, that somebody can manage to find any to embed: Sascha Kurz has recently calculated that no Heronian pentatope can exist with diameter < 600,000.] Incidentally, I have prepared a proof of the construction of lattice embeddings in 2- and 3-space via complex-number and quaternion GCD. I'll try to upload this somewhere public shortly --- in the meantime, anyone interested is welcome to request a copy (don't all rush at once!). Fred Lunnon

1 2

[math-fun] New simple full-period psu-random generator
by Warren Smith 06 Feb '12

06 Feb '12

New simple full-period psu-random generator ====Warren D. Smith Feb 2012========= In the below let "a+b" mean (a+b) mod 2^w where w is the machine's word size. Let F(x) be any function at all that maps one machine word x to another. The "parity of F" is the sum over all 2^w words x, of F(x) computed mod 2. So for example, the parity of F(x) = C + D*x + E(x*x) where C, D are any integer constants and E() is any function from integers to machine words, is equal to E(0) + E(2^(w-1)) mod 2. (This also works if any of the + are replaced by XOR.) Proof: use symmetry E(x*x)=E((-x)*(-x)) to pair x with -x for x not equal to 0 or 2^(w-1), which are the two numbers whose negation is the same as they are. Similarly mentally pair x and x+1 to handle the linear term. QED. If F() has even parity you can convert it to a new function F'() having odd parity as follows: F'(x) = F(x) + (C if x is zero, else D) where C and D are any integer constants with opposite parities. Also any of the "+" here could be replaced by XOR, that also works. THEOREM: Let x[0], x[1], ..., x[N-1] be a set of N machine words. Let C be any odd constant and F be any odd-parity function. Then the following code: x[0] += C; for(i=1 to N){ x[i] += F(x[i-1]); } will update the x-vector in a manner which has the maximum possible period=2^(n*w). So the random generator that I suggest is simply to do that update then output x[N-1]. However, that can be criticized thus: "the above update procedure is sequential not parallel." You can defeat that criticism as follows: Instead run the updating "in reverse": for(i=N down to 1){ x[i] += F(x[i-1]); } x[0] += C; which you can easily see makes no real difference (period still maximal... different guys are still doing their same thing, just shifted in time) but now all loop iterations and the final line all can be done in parallel. As a concrete example, this F(x) works: 1. Compute y=x*x as a double-length word. 2. F(x) = (lo(y) XOR hi(y)) + (x >> (w-1)) where "a>>h" is the C-language "right shift by h hops" operator. (The + optionally could be replaced by XOR.) ADVANTAGES: Very simple and foolproof. Does not care what wordsize your machine has in the sense you do not need, if the machine wordsize changes, to redesign a new set of mysterious careful constants or change the code. Does not care what n is, for any n at all will still have max period=2^(w*n) so you can increase n to get greater randomness but lower speed. Trivially easy to parallelize. For the particular F(x) suggested above, every bit of x potentially affects every bit of F(x), and the operation-types are well mixed preventing any particular part of the processor from experiencing "traffic jams."

1 0

[math-fun] Square root of an integer has first E digits repeated in some base B
by Robert Munafo 06 Feb '12

06 Feb '12

I did a more comprehensive search [3] for solutions to the Diophantine[1] equation R*S^2 = B^E-2 causing a square root of an integer to have repeating digits, with the digits resembling the coefficients of Series[K*sqrt(1/(1-2x))]. We want to have at least 2 repeated digits, because there are just too many examples if you allow just a single repeated digit (but see [2]). Some of the digit patterns are pretty darn pretty. sqrt(1820) in base 2 repeats 13 digits : 101010.1010100 1010101010100 1111111111111 1010101010100 ... sqrt(167772) in base 2 does a similar thing: 110011001.100110011000 11001100110011001100 100110011001100110010 111111111111111111111 ... This comes from 2^21-2 = 5^2*83886, and the fact that 5^2*2^2 = 100 gives us the base-10 similarity between 167772 and 2^24=16777216. Also in base 2: sqrt(28), sqrt(116508), and sqrt(85598) are similar. There are lots of 2^N-2 that are divisible by a square. sqrt(3) in base 3 repeats 3 digits: 1.20 120 212 222... This comes from 5^2+2=3^3 and is the only one I found where you're taking the square root of the base itself. Bases 4, 8 and 9 inherit all the cool patterns seen in bases 2 or 3. I gave a base 5 example earlier, another cool one is sqrt(1735): 131.31 13131 22222 13131 21211 44444 ... These go up to high bases too, and some are stunning. sqrt(16448427) in base 23 is: 7F7.F7 7F7F7 BBBBB 7F7F7 ACACA 5H5H5 where most pairs of digits add to M (the highest digit in base 23). sqrt(2434958270224475) in base 23 is a similar marvel with seemingly endless 7F7F7F7's I also want to mention that there is nothing arbitrary about the repeated digits themselves. In the case of sqrt(2), we have 2*7^2+2=100, so the repeated "14" is 2*7. This is also close to 100/7. In the case of sqrt(62), we have 62*127^2=999998, so the repeated digits "7874" are 62*127, close to 1000000/127. - Robert [1] Michael Reid mentions the Diophantine (2 a^2 - 1)(2 b^2 - 1)^2 = (2 c^2 - 1). I haven't tried to figure out whether or not the solutions to my Diophantine are in one-to-one correspondance with his. [2] A single repeated digit happens a lot: for any base B=K*N^2+2, sqrt(K*B) starts with a repeated digit. They all come from the same series expansion. In base 10, sqrt(20) shows the pattern: it is 4+0.4+0.06+0.010+... which is 4 times the series expansion of sqrt(1/(1-2x)) with x=0.1. [3] A longer list (bases up to 36 not including perfect powers like base 8 or base 9; R*S^2 up to 10^17, and R or R*B up to 999999): sqrt(28) in base 2 repeats 7 digits, because 14*3^2 = 2^7-2 = 126 sqrt(1820) in base 2 repeats 13 digits, because 910*3^2 = 2^13-2 = 8190 sqrt(116508) in base 2 repeats 19 digits, because 58254*3^2 = 2^19-2 = 524286 sqrt(167772) in base 2 repeats 21 digits, because 83886*5^2 = 2^21-2 = 2097150 sqrt(85598) in base 2 repeats 22 digits, because 85598*7^2 = 2^22-2 = 4194302 sqrt(3) in base 3 repeats 3 digits, because 1*5^2 = 3^3-2 = 25 sqrt(1735) in base 5 repeats 5 digits, because 347*3^2 = 5^5-2 = 3123 sqrt(276) in base 6 repeats 5 digits, because 46*13^2 = 6^5-2 = 7774 sqrt(977423) in base 7 repeats 10 digits, because 977423*17^2 = 7^10-2 = 282475247 sqrt(2) in base 10 repeats 2 digits, because 2*7^2 = 10^2-2 = 98 sqrt(62) in base 10 repeats 6 digits, because 62*127^2 = 10^6-2 = 999998 sqrt(836612) in base 14 repeats 5 digits, because 59758*3^2 = 14^5-2 = 537822 sqrt(392318) in base 22 repeats 6 digits, because 392318*17^2 = 22^6-2 = 113379902 sqrt(5711) in base 23 repeats 4 digits, because 5711*7^2 = 23^4-2 = 279839 sqrt(9326) in base 26 repeats 4 digits, because 9326*7^2 = 26^4-2 = 456974 sqrt(24584) in base 28 repeats 3 digits, because 878*5^2 = 28^3-2 = 21950 Allowing the residue to be a lot larger reveals some like this: sqrt(182044444444444440) in base 20 repeats 13 digits, because 9102222222222222*3^2 = 20^13-2 = 81919999999999998 This might seem like a freak or even an error, but it checks out. In fact, the statement "62*127^2 = 10^6-2 = 999998", written in base 5, becomes "222*1002^2 = 20^11-2 = 223444443". On Sun, Feb 5, 2012 at 21:13, Robert Munafo <mrob27(a)gmail.com> wrote: > Well, of course there's 2*7^2 = 98, which gives us the pretty digit > pattern: > > sqrt(2) = 1.4 14 ... > > More on this later, plus a mnemonic for the coefficients > of Series[sqrt(1/(1-2x))] > > In base 5, because 111^2*3963+2 = 5^11, the square root of 3963*5 = > 19815_10 = 1113230_5 = 1030.34033 00103034033 00132103324... where the > digit-groups are 11 digits long. > > In base 6, because 46*13^2+2 = 6^5, the square root of 46*6 = 276_10 > = 1140_6 = 24.34 02434 04053... where the digit-groups are 5 digits long. > > In base 7, because 977423*17^2+2 = 7^10, the square root of 977423_10 > = 11210426_7 = 2611.43464 0261143464 0421565362... where the digit-groups > are 10 digits long. > > In each of these examples, the third and 4th pretty digit-groups are 3/2 > and 5/2 times the first two digit groups. For example in the familiar > square root of 2, the first 8 digits (in groups of 2) are 14, 14, 21, 35 > and 14*1.5 = 21, 14*5/2=35. > > (You can check the other pretty digit examples above, but remember I > showed each in its native base and in odd bases 1/2 is an infinite > "repeating decimal". So 261143464 times 3/2 in base 7 is 421565362.3333... > where the "0.3333..." is 1/2 in base 7. These 3's overrun the following > digit-group which hides the 5/2 term.) > > So there are 4 examples (-: > > The digits of the square root of 2, taken in pairs and divided by 14, are > one way of remembering the coefficients of the series expansion > of sqrt(1/(1-2x)), if you ever find yourself in the need and are stuck with > just a pocket calculator. (-: The "62" ought to be 61.25, but it's overrun > by the leading "1" of the following term which is 14*63/8=110.25) > [...] > -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com

1 0

Re: [math-fun] More fun with sequences embedded in decimals
by David Wilson 06 Feb '12

06 Feb '12

Yes, in fact you cracked it. What I thought was notable about this solution was: - It arises naturally from a common length conversion. - We know that 0.3937 = 0.3937 1/2.54 = 0.3937007874... Given that the numbers themselves are so close, it would stand to reason that their geometric mean would be near their arithmetic mean, so that sqrt(0.3937 * (1/2.54)) .= (0.3937+(1/2.54))/2 = 0.3937003937... Both accurate to the decimals shown. This gives us a square root with a pretty repeated start block, which you observed and reproduced in another example. - But then there is the nice common factor between the block values 3937 = 31*127 254 = 2*127 This arises from the unusual square factor in the prime factorization: 999998 = 2*31*127^2 This has the peculiar side benefit that the quotient of the repeating blocks is a terminating decimal: 3937/254 = 15.5 Going back to our geometric mean identity, we get sqrt(0.3937 * (1/2.54)) = sqrt(0.155) = 0.3937003937... Which gives us a pretty square root of a terminating decimal. Multiplying by 20 on both sides then gives sqrt(62) = 7.874 007874 ... I will guess that small integer square roots with pretty blocks like this are rare in any base. - And an aside about the Mersenne primes You can't miss that 31 and 127 are Mersenne primes, which at first might seem incidental. However, consider that 2^20 = 1048576 .= 10^6 is close to a power of 10. Obviously this is well known, since we call 2^10 bytes a kilobyte, 2^20 bytes a megabyte, etc. We can break this up to 2 * 2^5 * (2^7)^2 = 1048576 .= 10^6 And if we tweak a couple of these factors slightly, we shouldn't affect the product too much, so lets tweak 2^5 and 2^7 down a notch: 2 * (2^5-1) * (2^7-1)^2 .= 999998 .= 10^6 So perhaps it is now less surprising that Mersenne primes might multiply to a value near 10^6, since Mersenne primes are slightly smaller than powers of 2 and 2^20 is slightly larger than 10^6. But of course, this is a hindsight analysis, since I knew the factorization to begin with. On 2/5/2012 3:09 AM, Robert Munafo wrote: > I don't see how the Mersenne factors matter. > > The first two of David's properties, 1/2.54 = 00.3937 007874... and > 1/39.37=00.0254 000508... are explained by their product being 99.9998 > = (10^N-2) / 10^K, as I suggested before. > > The other of David's properties, regarding the geometric mean, also > comes from (10^N-2) / 10^K, as you can see here: > > 1/sqrt(99.9998) > = .100000100000150000250000437500787501443752681255027353246111 > 1/sqrt(99.998) > = .100001000015000250004375078751443776813002743871274179225808 > 1/sqrt(99.98) > = .100010001500250043757876444018175282935398352327750882087668 > 1/sqrt(99.8) > = .100100150250438288946436286857920839193514369563735147583946 > > These all have the same pattern, related to the series expansion of > sqrt(1/(1-2x)), which you can get by "Series[sqrt(1/(1-2*x)),{x,0,8}]" > in Mathematica or Wolfram Alpha. The coefficients are: 1, 1, 3/2, 5/2, > 35/8, 63/8, 231/16, 429/16, 6435/128, ... The numerators are > https://oeis.org/A001790, which are also the numerators of the > sqrt(1/(1-x)) series expansion because only the denominators change. >

3 4