January 2016 - mathfun@mailman.xmission.com

[math-fun] continued fractions for a/2^w with only small partial quotients
by Warren D Smith 26 Jan '16

26 Jan '16

Here is a special case of theorem 1 of Harald Niederreiter: Dyadic fractions with small partial quotients, Monatshefte f"ur Mathematik 101,4 (December 1986) 309-315 Let p[0]=1, p[1]=3, p[2]=7, p[3]=113 and if n>=3 let p[n+1]=2^(2^n)*p[n]-1. (This sequence is not in, but should be in, the oeis.) Then the rational number p[n]/2^(2^n) has continued fraction with all partial quotients either 1, 2, or 3. For n large this rational number approaches 0.441390990978106856291920262469474778296688624079447195658789... 1/2 = [0; 2] 3/4 = [0; 1, 3] 7/16 = [0; 2, 3, 2] 113/256 = (7*16+1)/2^8 = [0; 2, 3, 1, 3, 3, 2] 28927/65536 = (113*256-1)/2^16 = [0; 2, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 2] 1895759871/2^32 = (28927*2^16-1)/2^32 = [0; 2, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 2] 8142226647014178815/2^64 = (1895759871*2^32-1)/2^64 = [0; 2, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 2] 150197571147608796277790585648096215039/2^128 = (8142226647014178815*2^64-1)/2^128 = [0; 2, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 2] 51109585015884376828428305273936708056145924221155280299477400051792199286783/2^256 = (150197571147608796277790585648096215039*2^128-1)/2^256 = [0; 2, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 1, 3, 3, 3, 1, 3, 3, 1, 3, 2] -- Warren D. Smith

5 5

[math-fun] Marvin Minksy has died
by Hilarie Orman 26 Jan '16

26 Jan '16

http://www.nytimes.com/2016/01/26/business/marvin-minsky-pioneer-in-artific… Nice quotes from Alan Kay and Danny Hillis. Hilarie

3 2

[math-fun] Marvin Minsky ...
by Allan Wechsler 25 Jan '16

25 Jan '16

... passed away yesterday at the age of 88; cause of death was cerebral hemorrhage. There is an obituary at the New York Times, here: http://www.nytimes.com/2016/01/26/business/marvin-minsky-pioneer-in-artific…

1 0

[math-fun] period of fibonacci sequence mod n
by Warren D Smith 25 Jan '16

25 Jan '16

Obviously, the greatest period we could hope for would be (n*n-1). This is achieved when n=2 and n=3, but for no other n up to 270000. If we merely ask that period>=(n*n-1)/2, or period>=n^(3/2), that happens for n=2,3,5,6,10, but for no other n up to 270000. If we merely ask that period>=5*n, that happens for n=10,50,250,1250,6250,31250, and which all are of form 2*5^k, but for no other n up to 270000. Note in particular that n=156250=2*5^7 is NOT listed. In all six of these cases, the period equals 6*n. Periods exceeding n seem to happen about 10% of the time. No case where period>10*n happens up to 270000. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 5

Re: [math-fun] continued fractions for a/2^w with only small partial quotients
by Warren D Smith 25 Jan '16

25 Jan '16

Harald Niederreiter: Dyadic fractions with small partial quotients, Monatshefte f"ur Mathematik 101,4 (December 1986) 309-315 actually showed by induction that for every power of 2, say 2^w, there existed an odd a such that the rational number a/2^w was represented by a continued fraction with only small partial quotients, specifically {1,2,3} only. Essentially, his proof went as follows. First, he found a set of suitable base cases to handle all w<12. Second, if w>11 is even he used his solution for b/2^(w/2) to construct a via a = b*2^(w/2) +- 1. Third, if w>11 is odd, he used his solution for c/2^((w-1)/2) to construct a via a = c*2^((w+1)/2) +- 1. Niederreiter also notes the maximum partial quotient "3" is least possible. That is since there exist w (examples: w=4,5,9,10,11,13,17,18,23,24, which by the way could also be another OEIS sequence) such that every a/w with a odd contains at least one partial quotient >=3 in its continued fraction. And Niederreiter's sequence of a's could well be in the OEIS, but also isn't. Now there are two troubles with Niederreiter's proof. First, the a's it constructs are useless for most applications, because their binary forms end with long strings of 11111111111 or with 0000000001. It would be more useful for almost all applications to find a's that seem more like they are made of "random bits." E.g. call an odd a which does not end with FFF or 001 in hexadecimal, "non-Niederian." QUESTION: For each w>=0, do there exist non-Niederian odd a, such that a/2^w has only {1,2,3} partial quotients in its continued fraction? I conjecture "yes" and have confirmed the conjecture with plentiful examples for each w=0,1,2,3,...,64. HARDER QUESTION: For all w>=0 except for a finite set of exceptions, do there exist non-Niederian odd a, such that a/2^w has only {1,2} partial quotients in its continued fraction? I conjecture "yes" and have found such a for each w=45,46,...,63. (Computer still working on w=64, but it is plausible that w=44, or some smaller w, is the last exceptional case where "3" is needed.) STILL HARDER QUESTION: What is the least K>1 such that: For all b>0 except for a finite set of exceptions (or, different problem version: "without exceptions") there exist a with GCD(a,b)=1, such that a/b has only {1,2,3,...,K} partial quotients in its continued fraction? S.K.Zaremba in 1972 conjectured that K=5 worked for the "without exceptions" problem version. I conjecture that K=2 works for the "finite number of exceptional b" problem version. The reason for my K=2 conjecture is twofold. First, the computer seems to find more a that work, for larger b. Second, if we consider the rational numbers representable as continued fractions [0; q1, q2, q3, ..., qh] with all the qj = 1 or 2, there are 2^h such rational numbers, and hence <=2^h different denominators. Their mean denominator actually grows asymptotic to 2^h. But the median denominator grows with h like C^h where the constant C apparently obeys 1.7<C<1.9. If so, that means a typical number b ought to be a denominator of such a "good" rational a/b, for MANY a, namely at least b^0.05 different a. This growth is fast enough so that, if the distribution "acts random" then the number of exceptional b (for which no good a exists) ought to be finite. This is a reasonably convincing heuristic argument, but I do not know any fast algorithm to find the good a for any given b.

1 3

[math-fun] The period of (2^k * Fibonacci[k] for k=0, 1, 2, 3...) mod n
by Warren D Smith 25 Jan '16

25 Jan '16

is at most n*n-1 of course, and it actually attains this bound when n=5,7,29,79,103,149,173,197,199,269,271,293,... These n all are primes p with JacobSymbol[3,p]=-1 and JacobSymbol[-2,p]=-1. But they do not include every such prime since p=31 is not there. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Somos sequence fully closed form
by Bill Gosper 25 Jan '16

25 Jan '16

Somos sequences are expressible as quadratic powers times theta functions, but these entail mysterious parameters empirically determined to make the first few terms come out right. An exception from arxiv.org/pdf/math/0703470 : RSolveInYourDreams[{a[n] == (a[-2 + n]^2 + a[-3 + n] a[-1 + n])/a[-4 + n], a[1] == 1, a[2] == 1, a[3] == -1, a[4] == Root[17 + 21 #1 - 5 #1^2 + 3 #1^3 + #1^4 &, 1]}, a[n], n] would give a[n]->ChebyshevU[-1 + n, 1/(2 Root[-1 - #1 + #1^4 &, 2]^(3/2))]* Root[-1 - #1 + #1^4 &, 2]^(1/2 (-1 + n^2)) featuring two nondescript quartic surds. Test: In[492]:= First /@ NestList[Append[Rest[#], (#[[4]] #[[2]] + #[[3]]^2)/#[[1]] // RootReduce] &, {1, 1, -1, Root[17 + 21 #1 - 5 #1^2 + 3 #1^3 + #1^4 &, 1]}, 7] Out[492]= {1, 1, -1, Root[17 + 21 #1 - 5 #1^2 + 3 #1^3 + #1^4 &, 1], Root[-11 + 36 #1 - 8 #1^2 - #1^3 + #1^4 &, 1], Root[89 - 731 #1 - 210 #1^2 - 18 #1^3 + #1^4 &, 2], Root[-379 - 12391 #1 + 2354 #1^2 - 134 #1^3 + #1^4 &, 2], Root[119 + 20913 #1 - 155 #1^2 + 51 #1^3 + #1^4 &, 1]} In[494]:= Table[RootReduce[ ChebyshevU[-1 + n, 1/(2 Root[-1 - #1 + #1^4 &, 2]^(3/2))]* Root[-1 - #1 + #1^4 &, 2]^(1/2 (-1 + n^2))], {n, 8}] Out[494]= {1, 1, -1, Root[17 + 21 #1 - 5 #1^2 + 3 #1^3 + #1^4 &, 1], Root[-11 + 36 #1 - 8 #1^2 - #1^3 + #1^4 &, 1], Root[89 - 731 #1 - 210 #1^2 - 18 #1^3 + #1^4 &, 2], Root[-379 - 12391 #1 + 2354 #1^2 - 134 #1^3 + #1^4 &, 2], Root[119 + 20913 #1 - 155 #1^2 + 51 #1^3 + #1^4 &, 1]} If ISC (etc?) tabulated the mysterious parameters in the theta formulas, maybe one day they'd suddenly become nonmysterious. --rwg

1 0

Re: [math-fun] 2^74,207,281-1 is prime
by W. Edwin Clark 21 Jan '16

21 Jan '16

I can factor 2^74,207,281-1. Will that do. :-) I am reminded of Bill Gates' comment: "The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers." On Thu, Jan 21, 2016 at 3:57 PM, rkg <rkg(a)ucalgary.ca> wrote: > The recent discovery of a new Mersenne prime reminds > me of the imminent risk that I shall lose $20.00. > Around my 80th birthday, when writing The Book of Numbers > with John Conway, he guessed that no new Fermat number > would be completely factored in the next 20 years. I bet > him that one would. > > So, in the next eight months, would someone please > complete the factorization of a previously unfactored > Fermat number? In an amazingly generously gesture, I > offer to split the $20.00 with anyone who comes up > with such a factorization! R. > > On Thu, 21 Jan 2016, Robert Baillie wrote: > > Thanks for the news! >> >> According to >> http://www.mersenne.org/ >> GIMPS software also a flaw in Intel's latest Skylake CPUs. >> >> Bob >> --- >> Ray Tayek wrote: >> >>> >>> http://science.slashdot.org/story/16/01/20/0137259/new-mersenne-prime-disco… >>> >>> >>> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> >> > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

1 0

[math-fun] 2^74,207,281-1 is prime
by Ray Tayek 21 Jan '16

21 Jan '16

http://science.slashdot.org/story/16/01/20/0137259/new-mersenne-prime-disco… -- Honesty is a very expensive gift. So, don't expect it from cheap people - Warren Buffett http://tayek.com/

3 2

[math-fun] big new planet?
by Warren D Smith 21 Jan '16

21 Jan '16

http://www.sciencemag.org/news/2016/01/feature-astronomers-say-neptune-size… "Astronomers say a Neptune-sized planet lurks beyond Pluto" allegedly its period is 15000 years, its mass is 5-to-15 earth masses, and its orbit is highly elliptical, unlike Neptune and every planet inside Neptune's orbit, all of which have highly circular orbits. Konstantin Batygin and Mike Brown of the California Institute of Technology (Caltech) in Pasadena are the ones making the claim. However, they have not actually directly seen the planet with any telescope, it is purely a mathematical deduction (similar to LeVerrier and Adams inferring Uranus had to exist) based on the way it appears to be pulling on other planets that we have seen. Actually seeing it could be pretty difficult. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 2