August 2020 - mathfun@mailman.xmission.com

Re: [math-fun] Mike, on the PDP-6, when you were chasing Mersenne primes (e.g. 11213, 23209, ...) vs Brillhart etc @ TJWatson
by Landon Curt Noll 23 Aug '20

23 Aug '20

Hello, I was asked to supply some background on FFTs primality testing history. I hope you find this useful. =-= As part of the Amdahl 6 group back in the late 1980’s: http://www.isthe.com/chongo/tech/math/prime/amdahl6.html where in 1990, we dethroned Mersenne primes for a few years, we used: http://www.isthe.com/chongo/tech/math/prime/p391581_216193.html http://www.isthe.com/chongo/src/calc/lucas-calc We wrote a 'ultra-high speed multi-precision' package on an Amdahl 1200 (think IBM 370-195 with a long trace vector processor add-on) and implemented a Riesel test. The heart of the package was a multiplication and square routine that was based on the PFA Fast Fourier Transform and on Winograd's radix FFTs. The IBM Floating point used a radix 16 mantissa. But we also had access to Amdahl/IBM micro-code so we could play with the bits "below the end of the double". Our vectors were represented in base 2^23. We used Macsyma using LISP ported to the Amdahl / IBM to build floating point operations to model the Floating-point "math" ops. On top of that we loaded the PFA Fast Fourier Transform and a Winograd's radix FFTs model. It was a HUGE Macsyma operation than ran on the Amdahl 5990 for a few weeks. In the end we were able to prove that using the IBM floating point architecture and base 2^23, we had NO systematic errors. (unlike GIMPS where they just hope it is good enough). While Macsyma was also used to verify the correctness of our code, it played a very important role in our code testing. While the Amdahl 6 was not the first primality testing FFT by any means, it was the first well tuned FFT for primality testing. Our cross-over point for when the FFT was more efficient for Riesel primes, primes of the form: h * 2^n - 1 was just under 1000 decimal digits. Combined with an amazingly efficient sieve on the Amdahl 1200 vector processor, we were cranking out 1000+ digit prime proofs at the rate of 1 every 6 seconds. Our intent was to flood the "Titanic prime list". Until Amdahl 6’s work, a titanic prime was a proven prime that was 1000 or more decimal digits in length. After our flood, where at one point we had 99.95% of the Titanic list, they changed the "Titanic prime" definition: which was fine since that was our goal. :-) =-= I was involved in a Primality test using FFTs on the Cyber 205 in the mid 1980’s. Due to the co-developer, Steve McGrogan wanting to only to start testing when the program was "fully optimized", we missed discovering the prime M86243. While the "fully optimized" routine would have been 42% faster, had we started the first code that passed all of our regression tests, we would have discovered M86243 in only 47 hours. This is why I advise people who are engaged in what Dr. Lehmer called: The great indoor sport of prime number hunting to start with the code that passes your extensive test suite: launch your search modify your source verify by measurement, that your new code rans FASTER verify that your new code passes your QA / regression test suite replace your production code with the new code rinse and repeat Do that until your mods are no longer running faster: likely when the clock time you might save is less than the time it takes to code and test. =-= I wrote a Mersenne LL-test using FFT code that ran on the Cray 1 back in 1980. It was a floating point FFT written in Cray Assembler that was based on the Cray FFT math library. The mods were mostly to deal with the fact that I was doing Mersenne Prime testing that an inline mod 2^n-1 instead of the standard normalization that the FFT required. However that code discovered that there was a reciprocal approximation hardware bug that caused the Mersenne tests for M9689 and M19937 to fail. The fix involved a solder patch to a circuit board in the reciprocal approximation unit. Only the Cray 1’s that were manufactured post Serial number 13 had the fix build in. Unfortunately the 16 machines that were pre SN-13 did not have that fix. There was resistance to fixing the older Cray’s because some numerical code broke when the bug was fixed. Indeed the Cray 1 I used had a jumper that could be changed to turn off the switch. Yes, there were 16 machines prior to #13 .. some Cray machines were not numbered because they were "made to not exist". Indeed the first Cray that could run my FFT code correctly was loaded up into a truck and left in a trailer behind the Safeway supermarket in Livermore California: it was driven away by authorized people. The repair was tested in the field. My code was used to verify the fix. There was a jumper that could enable/disable the fix. The fix did involve in part, an issue of capacitance. In honor of the PDP-10 MIT hack: https://www.cs.utah.edu/~elb/folklore/magic.html the board that was first field repaired contains the inscription: EVEN MORE MAGIC It is my hope that this machine will be moved to a museum someday. Anyway my FFT Mersenne search was halted for reasons you can read between the lines in the above. :-) FYI: We used the MIT-MC Macsyma machine to verify that the Cray 1 ALU was generating wrong values. The Cray was at an ARPANET link site, and so tipping over to MIT-MC to run Lisp code to test was a logical thing to do at that time. =-= When I helped found the EFF Cooperative Computing Awards: http://www.eff.org/awards/coop I put into the rules: https://www.eff.org/awards/coop/rules guidelines that I am NOT eligible for an award. This is because I am chair of the Cooperative Computing Awards advisory panel who helps the EFF determine when a claim is legit, it would be a conflict of interest if I obtained an award. In order to avoid even the appearance of a conflict of interest: I only advise others on primality testing these days. Much as improved from the Amdahl 6 days! See My tutorial: A Grand Coding Challenge! Finding a new Largest Known Prime http://www.isthe.com/chongo/tech/math/prime/prime-tutorial.pdf incorporates the best practices of finding a "new Largest Known Prime". While maybe not quite at "waist height" as Selfridge liked to call it, there is a plum waiting to be picked, that someone with a modest amount of effort could again de-thrown the Mersenne primes and beat GIMPS to a new prime number record. The tutorial in the URL above describes a few approaches to picking a mew "prime plum". I would also be happy ti give video talk on these details to anyone interested. =-= Since I saw a few Q’s about what I did for Moffett Federal Airfield, Lick, Pluto and Voyager: Yes I had a hand in helping save the Blimp Hanger at Moffett Field although there were others who had much bigger hands in saving the hanger. https://en.wikipedia.org/wiki/Moffett_Federal_Airfield Yes, I had a hand in helping prevent Lick Observatory from closing: http://mthamilton.ucolick.org Yes, I played a direct personal role in talking a US Senator into changing their vote to save the New Horizons mission to the dwarf planet Pluto (yes Pluto is a planet, a Dwarf planet): Current New Horizons status: http://pluto.jhuapl.edu And yes, I found the funds to prevent the Voyager spacecraft from being turned off in the mid 1990’s. Current Voyager status: https://voyager.jpl.nasa.gov/mission/status/ =-= I hope this helps. chongo (Landon Curt Noll) /\oo/\

1 0

[math-fun] Exploiting uniqueness
by James Propp 22 Aug '20

22 Aug '20

Does anyone know of a name attached to this problem-solving tactic? Jim Propp ---------- Forwarded message --------- From: David Will <daw5de(a)virginia.edu> Date: Tue, Jun 30, 2020 at 8:17 PM Subject: Question about the self-referential aptitude test To: <jamespropp(a)gmail.com> Dr. Propp: Good evening. I know I'm a bit late to the party, but I just wanted to say I'm a big fan of your self-referential aptitude test, which I just discovered today. In the instructions, you mentioned this idea that the foreknowledge of the puzzle having a unique solution can, in and of itself, be used as a clue when solving the puzzle. I enjoy Japanese-style puzzles, and I've previously encountered this same phenomenon in games such as slitherlink and masyu. I'm also a graduate student in mathematics at the University of Virginia, so I've been curious about this idea from a mathematical perspective. I was hoping you'd be able to answer a quick question. Do you know of a name for this phenomenon? I'm lacking in knowledge about game theory (is that even the right subject?), so I was unsuccessful in my searches online. I'd like to see if this phenomenon has been studied with any sort of rigor. In particular, I want to know if it would be possible to construct a puzzle that requires this logic in order to be solved (in some loose sense, ignoring brute-force guessing). Thank you for your time. I'd greatly appreciate it if you'd be willing to entertain my curiosity. Best, Andrew Will

5 5

[math-fun] Keller's conjecture now settled in all dimensions
by Dan Asimov 22 Aug '20

22 Aug '20

Keller's conjecture <https://en.wikipedia.org/wiki/Keller's_conjecture> proposed that if Euclidean space R^n were tiled by n-dimensional cubes any which way, then there must be some pair of n-cubes that share a common (n-1)-dimensional face. This is intuitively true in dimensions 2 and 3, but was proved true in dimensions up through 6 by Oskar Perron in 1940. To the surprise of many people, Lagarias & Shor (1994) found a counterexample in dimension 10. This immediately leads to counterexamples in all higher dimensions as well. Soon after a counterexample was found in dimension 8, showing it was also false in dimension 9 and leaving the only dimension where it was open being dimension 7. A team of four people — Joshua Brakensiek, Marijn Heule, John Mackey, and David Narváez — used a computer program to search for counterexamples in dimension 7, and in October 2019 they found one: <https://arxiv.org/abs/1910.03740>. There a nice article about it in Quanta magazine: <https://www.quantamagazine.org/computer-search-settles-90-year-old-math-pro…>. —Dan

2 1

Re: [math-fun] Correction re: Keller's conjecture now settled in all dimensions
by Dan Asimov 21 Aug '20

21 Aug '20

The Wikipedia article just hasn't been updated yet. —Dan Mike Beeler wrote: ----- The Wikipedia article says, "However, the translation from cube tilings to graph theory can change the dimension of the problem, so this result doesn't settle the geometric version of the conjecture in seven dimensions.” -----

1 0

[math-fun] Correction re: Keller's conjecture now settled in all dimensions
by Dan Asimov 21 Aug '20

21 Aug '20

Oops! I said the exact opposite of what happened. Sorry about that. In 7 dimensions it was proved ***true***, not false, contrary to what I wrote. —Dan ----- Keller's conjecture <https://en.wikipedia.org/wiki/Keller's_conjecture> proposed that if Euclidean space R^n were tiled by n-dimensional cubes any which way, then there must be some pair of n-cubes that share a common (n-1)-dimensional face. This is intuitively true in dimensions 2 and 3, but was proved true in dimensions up through 6 by Oskar Perron in 1940. To the surprise of many people, Lagarias & Shor (1994) found a counterexample in dimension 10. This immediately leads to counterexamples in all higher dimensions as well. Soon after a counterexample was found in dimension 8, showing it was also false in dimension 9 and leaving the only dimension where it was open being dimension 7. A team of four people — Joshua Brakensiek, Marijn Heule, John Mackey, and David Narváez — used a computer program to search for counterexamples in dimension 7, and in October 2019 they found one: <https://arxiv.org/abs/1910.03740>. ^^^^^^^^^^^^^^ ***FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE*** There a nice article about it in Quanta magazine: <https://www.quantamagazine.org/computer-search-settles-90-year-old-math-pro…>. -----

4 4

[math-fun] Another Lex. Earliest Sequence: Scott Shannon's "Enots Wolley sequence A336957
by Neil Sloane 21 Aug '20

21 Aug '20

Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names. Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version. Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ? I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem. Neil

9 13

Re: [math-fun] FactorInteger
by Bill Gosper 20 Aug '20

20 Aug '20

Slight improvement: Mathematica's front end by default displays a centerdot for implicit multiplication. Strangely, this doesn't work in old the FI function below, which displays blanks. Blanks also (by default) separate digits in blocks of 3. So the display is sometimes ambiguous. But Wolfram CE Harry Calkins showed me this workaround: FI⨉[n : _Rational | _Integer] := Defer @@ {FactorInteger@n} /. {{a_Integer, 1} -> a, {a_Integer, b_} -> a^b} /. {a_} -> a /. List -> Times E.g. In[144]:= FI⨉@BernoulliB@50]@// tim During evaluation of In[144]:= 0.006522,1 (seconds) Out[144]= (5^2 417202699 47464429777438199)/(2 3 11) (The first Bernoulli number with a square factor!) Dirty trick. I used a tiny ⨉ symbol instead of x, so you need Front End completion to input FI⨉. You may want to edit the definition. Instead of little centerdots between the factors, there's a Preferences variable Appearances|Numbers|Multiplication|Automatically display multiplication symbol between multiplied numbers Use symbol: which you can bash to be a mini ⨉. Sorry, I don't know how to bash it under program control, as in an init file. Unfactor is way nicer than with FactorInteger: UnFI⨉@Defer[x_] := x In[153]:= UnFI⨉@%144 Out[153]= 495057205241079648212477525/66 —rwg On Wed, Jan 4, 2017 at 12:44 AM Bill Gosper <billgosper(a)gmail.com> wrote: > There are > > In[14]:= 52! > Out[14]= > 80658175170943878571660636856403766975289505440883277824000000000000 > > ways to shuffle a deck. > That's just a "little" over a googol ... > > In[366]:= Log[10.^100, %] > Out[366]= 0.679066483922048 > > to the 2/3 power. The square of the cube root. And vice versa. So if > anybody asks how many > ways to shuffle a deck, "Oh, about the cube root of a googol squared." > But this is actually low > by a fairly substantial factor of > In[372]:= (10.^100)^(.679 - 2/3) > > Out[372]= 17.1132830416181 > > The actual number of shufflings is enormously composite: > > In[15]:= FactorInteger@%14 > Out[15]= > {{2,49},{3,23},{5,12},{7,8},{11,4},{13,4},{17,3},{19,2},{23,2},{29,1},{31,1},{37,1},{41,1},{43,1},{47,1}} > > But this is ugly and hard to read. The doc suggests > > In[16]:= CenterDot@@(Superscript@@@%) > Out[16]= > 2^49\[CenterDot]3^23\[CenterDot]5^12\[CenterDot]7^8\[CenterDot]11^4\[CenterDot]13^4\[CenterDot]17^3\[CenterDot]19^2\[CenterDot]23^2\[CenterDot]29^1\[CenterDot]31^1\[CenterDot]37^1\[CenterDot]41^1\[CenterDot]43^1\[CenterDot]47^1 > > This actually looks neat. Except for the ^1s. Try it. But it's unclear > (actually, a nice little Mathematica exercise) how to get your original > number back. > So I wrote something called FI > > In[364]:= FI[52!] > Out[364]= 2^49 3^23 5^12 7^8 11^4 13^4 17^3 19^2 23^2 29 31 37 41 43 47 > > In[365]:= ReleaseHold@% > Out[365]= > 80658175170943878571660636856403766975289505440883277824000000000000 > > Here is the definition: > FI[n : _Rational | _Integer] := > Times @@ ((HoldForm @@ {#1[[1]]})^#1[[2]] &) /@ FactorInteger[n] > > And here's a spoiler for how to invert FactorInteger: > > In[367]:= Times @@ (Power @@@ FactorInteger[73 137]) > Out[367]= 10001 > > which also works on that CenterDot expression: > > In[368]:= Times @@ (Power @@@ %16) > > Out[368]= > 80658175170943878571660636856403766975289505440883277824000000000000 > > Finally, you might enjoy finding a fairly nice formula for how many 0s are > on the end of n!, and, > more generally, what are exponents of the various prime factors. > --Bill >

1 1

[math-fun] (> 40)? yr old Life pattern for Roth's constant.
by Bill Gosper 19 Aug '20

19 Aug '20

(Which I incorrectly labeled Thue's. It has a fulminating continued fraction.) This (admittedly trivial) pattern has been waiting years to get included as Golly's Patterns>Hashlife>roth.mc. It spells out the bit sequence with blinkers. Formulas: https://www.jjj.de/fxt/fxtbook.pdf, 38.2 Screenshot <http://gosper.org/rothshot.png>: Golly file <http://gosper.org/roth.mc>: —rwg

1 0

[math-fun] Sage on iMac: on no account read the instructions!
by Fred Lunnon 17 Aug '20

17 Aug '20

The SAGE/SageMath CAS is free software, maintained by volunteer enthusiasts. This has pros and cons, of which I have experienced a handsome dose in the last couple of days. Starting with the cons: every hotshot programmer-mathematician who feels a ferocious urge to maintain an up-to-date step-by-step installation guide for dummies, please raise your hand now ... Uh-huh, thought so. Besides, none of those guys could do that job anyway, even if they wanted to: by the time anyone starts to take such things seriously, familiarity has already blinded them to many of the difficulties faced by a newcomer. Thus the download file directory comprises large number of alternative file identifiers, with no clue how to distinguish (say) sage-8.9-OSX_10.14.6-x86_64.app.dmg [for my operating system] sage-9.1-OSX_10.11.6-x86_64.app.dmg [for latest CAS release]. On randomly downloading some not-obviously unsuitable selection, one might (eventually) succeed in finding a way past Apple's security to click hopefully on the nice blue icon, calling up a browser panel labelled "Jupyter" which looks very business-like, but cannot apparently be persuaded to actually DO anything. At which point your newbie rolls up a sleeve and falls straight into a novice trap: he opens the installation README file, and attempts to execute the procedure described therein in deceptively precise and comforting detail. Then rolls up the other sleeve and tackles the Q&A support site, which has lots of Q's and A's and a search option, but (naturally) no procedure apparent for actually submitting an enquiry. Eventually all these obstacles prove to be minor, given a modicum of dogged perseverance, which proves rewarded by a couple of major pros. The level of support is astounding: once broken into the frankly weird bug-report system, my query was responded to within minutes by a fellow user, who pursued it through the weekend. And when one does succeed in invoking it, the software appears robust, efficient, cleanly designed, fast, (relatively) compact. For the benefit of anyone else contemplating installing SageMath on an Apple iMac, there is now a step-by-step description in the author's answer at https://ask.sagemath.org/question/53036/installation-fails-at-readme-step-5… which tries to carry on from where https://doc.sagemath.org/html/en/installation/binary.html http://www.mirrorservice.org/sites/www.sagemath.org/osx/intel/index.html leave the novice dangling. Fred Lunnon

1 0

Re: [math-fun] 'in-band' signaling in voting systems
by Keith F. Lynch 17 Aug '20

17 Aug '20

Brent Meeker <meekerdb(a)verizon.net> wrote: > Andy Latto wrote: >> There are two downsides to that. One downside is shared with >> absentee voting -- the voter could have been coerced or rewarded to >> vote in a specific way. The advantage of in-person voting is that >> that's not possible, at least not unless the coercer or rewarder >> hooks the voter up to a reliable lie detector. I, not Brent, wrote the above. > Or asks for a cel phone video of the ballot being marked. Not possible here in Virginia. You mark the ballot however your coercer or rewarder wishes, take a photo of it, then take the ballot to the poll worker and tell her that you made a mistake. She will discard the spoiled ballot and hand you a new one, which you then mark however you like. I assume the same would be true in most US states. And that the coercer or rewarder would know this, hence wouldn't bother.

1 0