October 2012 - mathfun@mailman.xmission.com

[math-fun] Making Sudoku puzzles less puzzling
by Christian Boyer 17 Oct '12

17 Oct '12

"University of Notre Dame complex networks researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravasz (...) can not only explain why some Sudoku puzzles are harder than others, they have also developed a mathematical algorithm that solves Sudoku puzzles very quickly, without any guessing or backtracking." http://newsinfo.nd.edu/news/32826-notre-dame-researcher-helps-make-sudoku-pu zzles-less-puzzling/ Main paper: www.nature.com/srep/2012/121011/srep00725/full/srep00725.html Christian.

1 0

Re: [math-fun] Add or subtract the result. Iterate.
by Phil Carmody 17 Oct '12

17 Oct '12

I've looked at the flight of 13094, and it's relentless - up to 115000 digits after 83M iterations, and still growing... 83125533[115146]: 143524455825705033056031082470820829609344558479726770660582324880706594479267893056859434808342457255[...] If anyone's interested, this is what I wrote last night to investigate so deeply. It deliberately logs very little, as it can continue from where it left off trivially, only recording at most one log per milliard digits of computation, and then only recording a new log when a new maximum length is reached. On a 12-year-old machine, that's still a log every 20 seconds. Phil -- 8< -- #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <assert.h> //#define DEBUG void rprint(int len, const uint8_t *restrict src) { while(len-->0) { putchar('0'+src[len]); } } int maywesub(int len, const uint8_t * restrict src) { uint8_t prev2=src[--len]*2; // top digit while(len-->0) { uint8_t this=src[len]; if(this==0 || this==prev2) { prev2=2*this; continue; } if(this<prev2) { return 1; } return 0; } return 1; } int suminto(int len, uint8_t * restrict src) { int carry=0; uint8_t prev=src[len-1]; for(int i=0; i<len; ++i) { uint_fast8_t diff = (src[i]>=prev) ? src[i]-prev : prev-src[i]; uint_fast8_t sum=src[i]+diff+carry; //uint_fast8_t sum = (src[i]>=prev) ? src[i]+src[i]+carry-prev : prev+carry; prev=src[i]; if(sum>=10) { src[i]=sum-10; carry=1; } else { src[i]=sum; carry=0; } } if(carry) { src[len++]=carry; } #if defined(DEBUG) printf("sum to "); rprint(len, src); printf("\n"); #endif return len; } int subinto(int len, uint8_t * restrict src) { int borrow=0; uint8_t prev=src[len-1]; for(int i=0; i<len; ++i) { uint_fast8_t diff = (src[i]>=prev) ? src[i]-prev : prev-src[i]; int sub=src[i]-(diff+borrow); // borrow forces this to be done as int //int sub = (src[i]>=prev) ? prev-borrow : src[i]+src[i]-prev-borrow; // borrow forces this to be done as int prev=src[i]; if(sub<0) { src[i]=sub+10; borrow=1; } else { src[i]=sub; borrow=0; } } assert(!borrow); while(src[len-1]==0) { --len; } #if defined(DEBUG) printf("sub to "); rprint(len, src); printf("\n"); #endif return len; } void dump(int iter, int len, const uint8_t * restrict src, const char * restrict msg) { printf("%i[%i]: ", iter, len); rprint(len, src); printf("%s\n", msg); } int main(int argc, char**argv) { int iter=0; if(argc>2) { iter=strtoul(argv[1],0,0); --argc; ++argv; } int len=strlen(argv[1]); int buflen=(len|0x3f)+1; int maxlen=len; uint8_t *buf; buf=malloc(buflen); for(int i=0; i<len; ++i) { buf[i]=argv[1][len-1-i]-'0'; } int printflag=0; int work=0; while(1) { ++iter; int sub=maywesub(len, buf); if(!sub) { len=suminto(len, buf); if(len>=maxlen) { if(printflag) { dump(iter, len, buf, ""); printflag=0; work=0; } maxlen=len; } if(len>=buflen) { buflen=(len|0x3f)+1; //printf("realloc(%i)\n", buflen); buf=realloc(buf,buflen); } } else { len=subinto(len, buf); } #if defined(DEBUG) printf("%i: len=%i\n", iter, len); #else if((work+=len)>1000000000) { work=0; printflag++; } #endif if(iter>100 && len<3) { dump(iter, len, buf, "\naborting, assuming it will loop"); break; } } }

1 0

Re: [math-fun] Does anybody know this fractal?
by Adam P. Goucher 17 Oct '12

17 Oct '12

> http://www.gibney.de/does_anybody_know_this_fractal > > Experimenting with the "divisibility" of complex numbers, I stumbled > across this thingy. It looks like a fractal. Although the formula > does not do any iterations. Plot the Gaussian rationals (a + bi)/c, where the size of each dot depends inversely on the value of c (cf Ford circles). This creates a square grid, resembling graph paper with infinitely thin divisions. Gibney's 'fractal' is the inversion of this 'graph paper fractal' in the unit circle. That's why everything appears to lie on circles passing through the origin; they are the inversions of straight lines with rational gradient, which naturally contain many rational points. Other interesting things can be done by repeated circle inversions, such as this: http://cp4space.wordpress.com/2012/09/02/imitating-escher/ That reminds me, I need to make some Escher-style Christmas cards using this technique. Sincerely, Adam P. Goucher

1 0

[math-fun] Re; Does anybody know this fractal?
by Stuart Anderson 17 Oct '12

17 Oct '12

Tin Eye reverse image search didnt produce anything. It reminds me of 2 things; firstly , Moebius transformations; see http://www.youtube.com/watch?v=JX3VmDgiFnY secondly, there is a passing resemblance to a recursive graph, found in David Hofstaders Godel, Escher, Bach (pages 148-151) showing energy bands for electrons in an idealized crystal in a magnetic field, magnetic field strength, runs vertically from 0 to 1. Energy runs horizontally. The horizontal line segments are bands of allowed electron energies. Stuart Anderson > Message: 3 > Date: Tue, 16 Oct 2012 12:18:12 -0700 > From: Ray Tayek <rtayek(a)ca.rr.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] Does anybody know this fractal? > Message-ID: <11.72.00773.EE2BD705(a)cdptpa-omtalb.mail.rr.com> > Content-Type: text/plain; charset="us-ascii"; format=flowed > > http://www.gibney.de/does_anybody_know_this_fractal > > Experimenting with the "divisibility" of complex numbers, I stumbled > across this thingy. It looks like a fractal. Although the formula > does not do any iterations. > > It reminds me of something. But I dont know what. > > Is this some known structure? Or some variation of another > mathematical object that has a name? > > --- > co-chair http://ocjug.org/ >

1 0

[math-fun] RCS's minimum-memory method for computing pi to N bits
by Warren Smith 16 Oct '12

16 Oct '12

RC Schroeppel: Possible minimum-memory method for computing pi to N bits, albeit extremely slowly: For K = 0 to N, use the BBP formula for the Kth bit. This will require O(logN) storage: several registers of size logN to hold the state of the BBP calculation. You'll also need to be aware of the Chudnovsky result, which, IIRC, is that |pi - p/q| > q^-13. That is, you can't get too many consecutive 0s or 1s before a round-up-or-down situation is resolved. However, if you want the answer in decimal, you may need space to hold most of the .301 N digits, which would bump the space to O(N). --WDS: lovely [if useless] observation. However, I think the story may be a little deeper than you realized, in the following sense. The "irrationality measure" you had in mind is |pi - p/q| > q^(-u) in all but a finite number of cases, The current record apparently is u = 7.6063 by V.Kh.Salikhov: On the Irrationality Measure of pi, Usp. Mat. Nauk 63 (2008) 163-164; English transl. in Russian Math. Surveys 63 (2008) 570-572. But here is the thing: I think "in all but a finite number of cases" is NOT an effective, i.e. not an algorithmic, result -- there is no known algorithm to find the last exception. (Or am I wrong about that?) If so, you actually have not got an algorithm here -- although "God" knows (but you do not know) the relevant constant, hence an algorithm EXISTS, but you do not know what that algorithm is. So you've actually got an NONCONSTRUCTIVE existence proof for an O(logN)-memory algorithm to compute N bits of pi !! Now if instead of PI you asked about other numbers... for certain numbers like e and quadratic irrationals, the full continued fraction expansion is known, hence the irrationality measure and the "last exception" both are fully understood. If any such number happens to have a BBP formula, then you'd be fully golden. Hmmm. It seems that "Baker's theorem" http://en.wikipedia.org/wiki/Baker's_theorem nowadays has fully effective/explicit formulas e.g. due to Baker & Wustholz. Therefore, it is possible to produce explicit irrationality measure statements for pi (albeit perhaps requiring far larger u than Salikhov's!), having no exceptions. A.Baker & G.W"ustholz: Logarithmic forms and group varieties, Journal f"ur die Reine und Angewandte Mathematik 442 (1993) 19-62 Therefore, I think RCS's algorithm really can be made into an algorithm.

2 1

[math-fun] Does anybody know this fractal?
by Ray Tayek 16 Oct '12

16 Oct '12

http://www.gibney.de/does_anybody_know_this_fractal Experimenting with the "divisibility" of complex numbers, I stumbled across this thingy. It looks like a fractal. Although the formula does not do any iterations. It reminds me of something. But I dont know what. Doing a <http://images.google.com/search?tbs=sbi:AMhZZiu5OzJGfE0ymAi-d3yeJNc9ZOatp3v… Y ahtWvYbNu4rfUXo5Z9os7bFrF3Ra>Google image search brings up a couple of galaxies :) This image shows the region from (-1/-1) to (1/1). You can click it to see a 4000x4000 pixel rendering of it. Is this some known structure? Or some variation of another mathematical object that has a name? --- co-chair http://ocjug.org/

1 0

Re: [math-fun] 3. Re: Another approximation of pi
by Henry Baker 16 Oct '12

16 Oct '12

At 08:29 PM 10/14/2012, Eugene Salamin wrote: >A program that calculates pi to N places requires memory that grows as some function f(N), and f(N) must grow unboundedly large with N. This is true for any irrational, since a finite state machine eventually repeats, and thus can only calculate rationals. So perhaps the complexity of an irrational number can be characterized by the slowest growing memory needed for its calculation. There is a tower of complexity based on Turing machine tape lengths, and a tower of complexity based on number of steps. The two towers are inter-related but are not (obviously) identical. Computing pi is particularly simple, because it doesn't require emulating all Turing Machines with less tape or fewer steps before deciding what the answer should be.

1 1

[math-fun] 3. Re: Another approximation of pi
by Stuart Errol Anderson 15 Oct '12

15 Oct '12

Continued fraction of ln(pi^7) leads to an approximation of pi as e^87/76 = 3.1416, and C.F. ln(pi^19) gives e^41129/35929 = 3.14159264. Also iteration of a complex number near Seahorse Valley (Mandelbrot Set) can be used to approximate pi

5 5

Re: [math-fun] Another approximation of pi
by Bill Gosper 15 Oct '12

15 Oct '12

DWilson>I would tend to group approximations into two general categories: Definition-based approximations, which follow mathematical properties, for example π ~= 3 π ~= ln(640320^3+744)/sqrt(163) The first follows from the approximate equality of the perimeter of a circle and its circumscribed hexagon, the second follows from a truncated series expansion in class theory. There are reasons for these approximations. Value-based approximations have no apparent direct relationship to mathematical definitions. For example, π ~= 22/7 π ~= 355/113 π ~= sqrt(9.87) π ~= cbrt(10) π^4 + π^4 ~= e^6 e^π - π ~= 20 all seem to be value-based. These relationships are commonly found by observation or numerical analysis of the numerical values, not derived from mathematical properties. This is clearly a subjective distinction. Tomorrow we may find reasons for approximations that baffle us today. ---------------- E.g., where would you put Out[426]= 22/7 + Sin[22/7] In[427]:= N[% - π, 2] Out[427]= 3.4*10^-10 ?-) rwg

2 2

[math-fun] Hadamard conjecture true?
by Warren Smith 15 Oct '12

15 Oct '12

I don't know if I'd agree with NJA Sloane the evidence for it is "overwhelming" but it is pretty good. I find http://oeis.org/A007299 unconvincing since it has so few entries. And I have strong doubts this sequence is monotonic. You know Laplace said the probability the sun rises tomorrow based on fact it was true N previous days, is (N+1)/(N+2). The probability the Hadamard conjecture is true is in my view about 99%. It previously was conjectured that Williamson-form Hadamard matrices always existed. True for n=1,2,3,...,34. But false for n=35 (no 140x140 Hadamard of Williamson form exists, 140=4*35). So this should serve as a cautionary tale. I suggest you solve my recently posted question about highly cancelling polynomials. If you do I will be able with probability 99% to make very strong progress on the Hadamard conjecture. (In fact in unpublished work I already did make strong progress on the Hadamard conjecture...)

4 6