October 2016 - mathfun@mailman.xmission.com

Re: [math-fun] Question about base 3/2
by James Propp 07 Oct '16

07 Oct '16

Don, Sorry it's taken me so long, but I finally had time to look at your proof today. It looks sound. So now we know that 1/3 does not have any eventually periodic expansion in the permissive version of base 3/2 that uses the digits 0, 1, and 2. Thanks! Jim On Tue, Sep 27, 2016 at 10:49 PM, Don Reble <djr(a)nk.ca> wrote: > > Can you rewrite and repost, if it's not too much trouble? >> > > Done. > > -- > Don Reble djr(a)nk.ca > >

1 0

[math-fun] Think you got a good math + physics education?
by Dan Asimov 07 Oct '16

07 Oct '16

Then try this: Part II of last June's Mathematical Tripos (U.K.): [pure + applied] [math + physics]: https://www.maths.cam.ac.uk/system/files/list_ii.pdf <https://www.maths.cam.ac.uk/system/files/list_ii.pdf> —Dan P.S. I got so tired reading it I had to lie down until the feeling passed. P.P.S. At least I can solve problem 2H on page 99. Can you?

2 2

[math-fun] 2017 trivium
by David Wilson 06 Oct '16

06 Oct '16

When 2017 rolls around, we will be looking for some interesting property of that number. Here's my early submission: It appears that 2^2017 is the largest power of 2 that does not include the substring 53.

3 3

[math-fun] Borsuk-Ulam
by James Propp 04 Oct '16

04 Oct '16

On a more mathematically substantive topic, can the proof of Borsuk-Ulam on S^2 that Vsauce presents be made rigorous without a lot of extra machinery? Neither of the proofs at https://en.m.wikipedia.org/wiki/Borsuk–Ulam_theorem is as simple as one might hope. Jim Propp On Tuesday, October 4, 2016, James Propp <jamespropp(a)gmail.com> wrote: > Michael at Vsauce, in his superb video on fixed points ( > https://m.youtube.com/watch?v=csInNn6pfT4) asserts that the reason you > eventually end up with 4 if you iterate the operation "spell the word and > count the letters" is that 4 is the only fixed point of this map. This > neglects the possibility of cycles. Can anyone find a language in which the > spell-and-count map contains one or more cycles of length greater than 1? > > There is some ill-definedness of the spell-and-count map in English, and > probably other languages too; e.g., 101 is both "one hundred one" and "one > hundred and one". There's also the matter of the British billion vs. the > American billion. All such variants are legitimate for purposes of my > question. > > Jim Propp >

1 1

Re: [math-fun] Spell-and-count
by Leo Broukhis 04 Oct '16

04 Oct '16

On Tue, 4 Oct 2016 12:32:39 -0400, Allan Wechsler <acwacw(a)gmail.com> wrote: > I suspect that all languages with advanced numeral systems have a threshold > number, above which ever numeral has fewer letters than its value. I think > this threshold in English is 4. In Russian, it is 11: одиннадцать Leo

1 0

[math-fun] Spell-and-count
by James Propp 04 Oct '16

04 Oct '16

Michael at Vsauce, in his superb video on fixed points ( https://m.youtube.com/watch?v=csInNn6pfT4) asserts that the reason you eventually end up with 4 if you iterate the operation "spell the word and count the letters" is that 4 is the only fixed point of this map. This neglects the possibility of cycles. Can anyone find a language in which the spell-and-count map contains one or more cycles of length greater than 1? There is some ill-definedness of the spell-and-count map in English, and probably other languages too; e.g., 101 is both "one hundred one" and "one hundred and one". There's also the matter of the British billion vs. the American billion. All such variants are legitimate for purposes of my question. Jim Propp

4 6

Re: [math-fun] The largest twin-primes known today...
by Bill Gosper 03 Oct '16

03 Oct '16

So an "unlucky" Miller-Rabin case would refute GRH? --rwg On 2016-10-02 02:50, Adam P. Goucher wrote: >> On 2016-09-21 04:29, Adam P. Goucher wrote: >> > I personally like Pollard's rho factorisation. Easy to implement (no >> > fancy sieves) and offers a quadratic speedup over trial division (so a >> > worst-case time complexity of sqrt(sqrt(N)) for factorising N). >> >> It's easy to like: fast, terse, and clever. But it just finds a factor >> rather >> than the full factorization, and doesn't prove primality. How tersely can >> we do *all* this if we settle for √n time complexity? --rwg > > You can check primality first using Miller-Rabin for various initial values. > I think there's a bound (or rather two, the tighter one being dependent on > GRH) of how many values you need to check. > > >> >> Sent: Wednesday, September 21, 2016 at 1:20 PM >> >> From: "Bill Gosper" <billgosper(a)gmail.com> >> >> To: math-fun(a)mailman.xmission.com >> >> Subject: Re: [math-fun] The largest twin-primes known today... >> >> >> >> On Wed, Sep 21, 2016 at 2:14 AM, Bill Gosper <billgosper(a)gmail.com> >> wrote: >> >> >> >> > I think Allan means 3^2, not 3^12. This would have been an extremely >> easy >> >> > factorization even for Lehmer's optical contraption >> >> > <https://en.wikipedia.org/wiki/Lehmer_sieve>. Or Macsyma back when it >> >> > trial-divided by consecutive odd numbers. Which is pretty much like >> >> > GCDing with >> >> > their product, now that we can store big numbers. I just wrote a tiny >> >> > (and >> >> > very untested) recursive program in a similar vein: >> >> > >> >> > In[832]:= Clear[dumfac]; dumfac@1 = {}; >> >> > dumfac[n_Integer] := (dumfac@n = {n}; >> >> > dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ >> >> > GCD[n, Binomial[#, Floor[#/2]] &@Floor[Sqrt[n]]]) >> >> > >> >> > In[833]:= dumfac[2996863034895] // tim >> >> > >> >> > During evaluation of In[833]:= 0.188517 sec, 5 >> >> > >> >> > Out[833]= {5, 3, 3, 18583, 3583757} >> >> > >> >> > In[834]:= PrimeQ /@ % >> >> > >> >> > Out[834]= {True, True, True, True, True} >> >> > --rwg >> >> > >> >> > Phew, that doesn't even slightly work! >> >> >> >> In[342]:= dumfac@11111111111111111 // tim >> >> >> >> During evaluation of In[342]:= 12.903538,1 >> >> >> >> Out[342]= {11111111111111111} >> >> >> >> Mindlessly changing a 2 to a 3, >> >> In[338]:= Clear[dumfac]; dumfac@1 = {}; >> >> dumfac[n_Integer] := (dumfac@n = {n}; >> >> dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ >> >> GCD[n, Binomial[#, Floor[#/3]] &@Floor[Power[n, (2)^-1]]]) >> >> >> >> In[339]:= dumfac@11111111111111111 // tim >> >> >> >> During evaluation of In[339]:= 11.772568,2 >> >> >> >> Out[339]= {2071723, 5363222357} >> >> >> >> But 12 seconds! >> >> On 2016-09-21 03:04, Tom Karzes wrote: >> >> > Or you could just invoke the factor program that's part of GNU >> coreutils >> >> > and is part of a standard Ubuntu Linux install: >> >> > >> >> > % factor 2996863034895 >> >> > 2996863034895: 3 3 5 18583 3583757 >> >> > % >> >> > >> >> > See the info file for details. >> >> > >> >> > Tom >> >> > >> >> But the elephant in the room is Mathematica: >> >> In[320]:= FactorInteger[(10^59 - 1)/9] // tim >> >> >> >> During evaluation of In[320]:= 0.035899 sec, 2 >> >> >> >> Out[320]= {{2559647034361, 1}, >> >> {4340876285657460212144534289928559826755746751, 1}} >> >> --rwg >> >> >> >> > >> >> > On 2016-09-20 16:05, Allan Wechsler wrote: >> >> > > Factoris says the coefficient factors to 3^12.5.18583.3583757. >> >> > > >> >> > > On Tue, Sep 20, 2016 at 6:55 PM, Dan Asimov <asimov(a)msri.org> wrote: >> >> > > >> >> > >> P.S. I'm puzzled by this statement about these twin primes at that >> link: >> >> > >> >> >> > >> ----- >> >> > >> They will enter Chris Caldwell's “The Largest Known Primes Database” >> >> > >> (http://primes.utm.edu/primes) ranked 1st for twins, and each >> entered >> >> > >> individually ranked 4180th overall. >> >> > >> ----- >> >> > >> >> >> > >> Why do they have the same ranking overall? Does it not matter that >> >> > >> one is bigger than the other? >> >> > >> >> >> > >> —Dan >> >> > >> >> >> > >> >> >> > >> > On Sep 20, 2016, at 3:35 PM, Dan Asimov <asimov(a)msri.org> wrote: >> >> > >> > >> >> > >> > Is anything known about the factorization of that coefficient >> >> > >> > >> >> > >> > (other than its divisibility by 5 and 9)? >> >> > >> > >> >> > >> > Was it chosen as part of some algorithm that singled out >> relatively >> >> > >> > likely candidates? Or was it just stumbled on at random from a >> >> > >> > massive search? >> >> > >> > >> >> > >> > >> >> > >> > Or maybe one of our factoring experts can factor it? (You know >> who you >> >> > >> are.) >> >> > >> > >> >> > >> > —Dan >> >> > >> > >> >> > >> > >> >> > >> >> On Sep 20, 2016, at 3:18 PM, Eric Angelini < Eric.Angelini(a)kntv.be >> > >> >> > >> wrote: >> >> > >> >> >> >> > >> >> >> >> > >> >> ... are: >> >> > >> >> 2996863034895*2^1290000-1 >> >> > >> >> and >> >> > >> >> 2996863034895*2^1290000+1 >> >> > >> >> >> >> > >> >> http://www.primegrid.com/download/twin-1290000.pdf >> >> > >> >> >> > >> >> > >> ______________

4 3

[math-fun] Half forgotten AILab flashback
by Bill Gosper 02 Oct '16

02 Oct '16

Sometime ~ 1966?, Bill Henneman asked me to search for a counterexample to a conjecture about finite state (Moore) machines. It said something like a machine that accepts the star of a finite set has only cyclic subgroups in its state vector semigroup. Can someone render this coherent? It may have been for Minsky's Finite and Infinite Machines book. I remember representing the state vectors as blocks of indexed PUSH instructions, so you could multiply them by aiming one at the other and executing it, one instruction per state. Oh, that's right, data execution is now illegal. Anyway, I failed to find a counterexample, but I think Henneman constructed one. Why unmentioned in HAKMEM? --rwg

1 0

Re: [math-fun] The largest twin-primes known today...
by Bill Gosper 02 Oct '16

02 Oct '16

On 2016-09-21 04:29, Adam P. Goucher wrote: > I personally like Pollard's rho factorisation. Easy to implement (no > fancy sieves) and offers a quadratic speedup over trial division (so a > worst-case time complexity of sqrt(sqrt(N)) for factorising N). It's easy to like: fast, terse, and clever. But it just finds a factor rather than the full factorization, and doesn't prove primality. How tersely can we do *all* this if we settle for √n time complexity? --rwg > >> Sent: Wednesday, September 21, 2016 at 1:20 PM >> From: "Bill Gosper" <billgosper(a)gmail.com> >> To: math-fun(a)mailman.xmission.com >> Subject: Re: [math-fun] The largest twin-primes known today... >> >> On Wed, Sep 21, 2016 at 2:14 AM, Bill Gosper <billgosper(a)gmail.com> wrote: >> >> > I think Allan means 3^2, not 3^12. This would have been an extremely easy >> > factorization even for Lehmer's optical contraption >> > <https://en.wikipedia.org/wiki/Lehmer_sieve>. Or Macsyma back when it >> > trial-divided by consecutive odd numbers. Which is pretty much like >> > GCDing with >> > their product, now that we can store big numbers. I just wrote a tiny >> > (and >> > very untested) recursive program in a similar vein: >> > >> > In[832]:= Clear[dumfac]; dumfac@1 = {}; >> > dumfac[n_Integer] := (dumfac@n = {n}; >> > dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ >> > GCD[n, Binomial[#, Floor[#/2]] &@Floor[Sqrt[n]]]) >> > >> > In[833]:= dumfac[2996863034895] // tim >> > >> > During evaluation of In[833]:= 0.188517 sec, 5 >> > >> > Out[833]= {5, 3, 3, 18583, 3583757} >> > >> > In[834]:= PrimeQ /@ % >> > >> > Out[834]= {True, True, True, True, True} >> > --rwg >> > >> > Phew, that doesn't even slightly work! >> >> In[342]:= dumfac@11111111111111111 // tim >> >> During evaluation of In[342]:= 12.903538,1 >> >> Out[342]= {11111111111111111} >> >> Mindlessly changing a 2 to a 3, >> In[338]:= Clear[dumfac]; dumfac@1 = {}; >> dumfac[n_Integer] := (dumfac@n = {n}; >> dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ >> GCD[n, Binomial[#, Floor[#/3]] &@Floor[Power[n, (2)^-1]]]) >> >> In[339]:= dumfac@11111111111111111 // tim >> >> During evaluation of In[339]:= 11.772568,2 >> >> Out[339]= {2071723, 5363222357} >> >> But 12 seconds! >> On 2016-09-21 03:04, Tom Karzes wrote: >> > Or you could just invoke the factor program that's part of GNU coreutils >> > and is part of a standard Ubuntu Linux install: >> > >> > % factor 2996863034895 >> > 2996863034895: 3 3 5 18583 3583757 >> > % >> > >> > See the info file for details. >> > >> > Tom >> > >> But the elephant in the room is Mathematica: >> In[320]:= FactorInteger[(10^59 - 1)/9] // tim >> >> During evaluation of In[320]:= 0.035899 sec, 2 >> >> Out[320]= {{2559647034361, 1}, >> {4340876285657460212144534289928559826755746751, 1}} >> --rwg >> >> > >> > On 2016-09-20 16:05, Allan Wechsler wrote: >> > > Factoris says the coefficient factors to 3^12.5.18583.3583757. >> > > >> > > On Tue, Sep 20, 2016 at 6:55 PM, Dan Asimov <asimov(a)msri.org> wrote: >> > > >> > >> P.S. I'm puzzled by this statement about these twin primes at that link: >> > >> >> > >> ----- >> > >> They will enter Chris Caldwell's “The Largest Known Primes Database” >> > >> (http://primes.utm.edu/primes) ranked 1st for twins, and each entered >> > >> individually ranked 4180th overall. >> > >> ----- >> > >> >> > >> Why do they have the same ranking overall? Does it not matter that >> > >> one is bigger than the other? >> > >> >> > >> —Dan >> > >> >> > >> >> > >> > On Sep 20, 2016, at 3:35 PM, Dan Asimov <asimov(a)msri.org> wrote: >> > >> > >> > >> > Is anything known about the factorization of that coefficient >> > >> > >> > >> > (other than its divisibility by 5 and 9)? >> > >> > >> > >> > Was it chosen as part of some algorithm that singled out relatively >> > >> > likely candidates? Or was it just stumbled on at random from a >> > >> > massive search? >> > >> > >> > >> > >> > >> > Or maybe one of our factoring experts can factor it? (You know who you >> > >> are.) >> > >> > >> > >> > —Dan >> > >> > >> > >> > >> > >> >> On Sep 20, 2016, at 3:18 PM, Eric Angelini <Eric.Angelini(a)kntv.be > >> > >> wrote: >> > >> >> >> > >> >> >> > >> >> ... are: >> > >> >> 2996863034895*2^1290000-1 >> > >> >> and >> > >> >> 2996863034895*2^1290000+1 >> > >> >> >> > >> >> http://www.primegrid.com/download/twin-1290000.pdf >> > >> >> > >> >

2 1

[math-fun] Iteration question
by David Wilson 02 Oct '16

02 Oct '16

Let f(n) = sigma(n) - n = sum of proper divisors of n. If you iterate f on positive integer n, some trajectories end at 0 (where you cannot continue, since 0 is not in the domain of f), some trajectories loop (e.g. 6 -> 6... or 220 -> 284 -> 220...). For other numbers, like 138, the trajectory seems to diverge. Can we prove that there exist divergent trajectories?

3 2