June 2018 - mathfun@mailman.xmission.com

[math-fun] Terse ratfitter
by Bill Gosper 14 Jun '18

14 Jun '18

Out[551]= {3, 5, 28/5, 165/28, 91/15, 68/11, 570/91, 253/40, 325/51, 609/95, 496/77} In[552]:= fitrat@% Out[552]= 3 + (-1 + n)/(1/2 + (-2 + n)/(26/7 + (-3 + n)/(203/2 + 28 (-4 + n)))) In[553]:= FullSimplify@% Out[553]= 3/4 (9 + 1/(1 - 2 n) - 4/n) fitrat[L_List, v_: (n - 1)] := If[MemberQ[#2 - #, 0] || #2 == {}, #, # + v/fitrat[Range[Length@#2]/(#2 - #), v - 1]] &[L[[1]], Rest@L] Has anyone a nice explanation of why this works? --rwg

1 2

[math-fun] Schensted's two-dimensional abacus
by James Propp 14 Jun '18

14 Jun '18

Oops; this thread needs a subject-line. On Sun, Jun 10, 2018 at 9:00 PM, James Propp <jamespropp(a)gmail.com> wrote: > According to Martin Gardner's piece "Napier's Abacus" (chapter 8 in > "Knotted Doughnuts and Other Mathematical Entertainments"): > > Craige Schensted was inspired by Napier's device to invent a chessboard > computer on which many astonishing calculations can be made. The basic idea > is to allow the columns to be labeled with the powers of one base and the > rows to be labeled with the powers of a different base. Each cell > represents the product of its row and column numbers. It would require a > long chapter to do justice to the elegant ways Schensted found for using > such a board to solve problems that otherwise would be difficult. > Does anyone know anything about this? > > I wonder whether the only extant account of Schensted's device is in > Gardner's files of correspondence. I assume that these files are available > to scholars. Perhaps someone should seek to publish those letters that > contain contributions to mathematics that would otherwise be lost to > posterity? > > Jim Propp >

5 9

[math-fun] Minimum number of swaps to sort a permutation of {1, 2, 3, ..., N}
by Dan Asimov 13 Jun '18

13 Jun '18

Consider all algorithms for sorting a permutation of {1, 2, 3, ..., N}, say given as a filled array arr[1], ..., arr[N], such that each step of the algorithm is of the form if (arr[I] > arr[J]) swap(arr[I], arr[J]); where I and J are actual numbers, and no other steps are allowed. For instance, If x[1], x[2], x[3] is any permutation of {1, 2, 3} then this program will always sort it: ----- if (x[1] > x[2]) swap(x[1], x[2]); if (x[2] > x[3]) swap(x[2], x[3]); if (x[1] > x[2]) swap(x[1], y[2]); ----- Among those that sort all permutations of {1, 2, 3, ..., N}, what is the minimum number of comparisons that sort the worst-case permutation(s)? Let this number be C(N). I'd like to have an asymptotic expression for C(N), or at least upper and lower bounds. —Dan

2 1

[math-fun] Draft of June 2018 blog post
by James Propp 13 Jun '18

13 Jun '18

I started writing a new draft titled "Why Does Exploding Dots Work?" and would love to get your comments, whether I receive them before or after I publish the essay on my blog (late on the 16th or early on the 17th). As usual, I prefer to get responses via email, since then I'll know who you are and can respond if I have follow-up questions. Thanks! Jim Propp <https://mathenchant.wordpress.com?p=2354&shareadraft=5b214e16a08c9> Title: Why Does Exploding Dots Work? Beginning: A few months from now, if James Tanton and his Global Math Project co-conspirators have their way, ten million schoolchildren will take a huge mathematical step backward from the twenty-first century into the Bronze Age: instead of using a gadget with a state-of-the-art interface (say, a telepathic ... Read more: https://mathenchant.wordpress.com?p=2354&shareadraft=5b214e1 6a08c9

1 0

[math-fun] Bug in my published 34 yr old formula !?
by Bill Gosper 12 Jun '18

12 Jun '18

https://books.google.com/books?id=oYGz3S_WTHUC&pg=PA261&lpg=PA261&dq=NYU+Co… pp 267-268. This is the formula which I've used regularly to convert an arbitrary composition of homographic functions (e.g., a sum) to a (non regular) continued fraction. To my bewilderment and distress, it just stopped working, even after I rederived it. The rarely used terminating case went undetected. Empirically, the final term should be x = c[m+1](y + d[m]/c[m]), not c[m+1](y + d[m]/d[m+1]). --rwg

6 10

[math-fun] (no subject)
by James Propp 11 Jun '18

11 Jun '18

According to Martin Gardner's piece "Napier's Abacus" (chapter 8 in "Knotted Doughnuts and Other Mathematical Entertainments"): Craige Schensted was inspired by Napier's device to invent a chessboard computer on which many astonishing calculations can be made. The basic idea is to allow the columns to be labeled with the powers of one base and the rows to be labeled with the powers of a different base. Each cell represents the product of its row and column numbers. It would require a long chapter to do justice to the elegant ways Schensted found for using such a board to solve problems that otherwise would be difficult. Does anyone know anything about this? I wonder whether the only extant account of Schensted's device is in Gardner's files of correspondence. I assume that these files are available to scholars. Perhaps someone should seek to publish those letters that contain contributions to mathematics that would otherwise be lost to posterity? Jim Propp

2 1

[math-fun] Punishment for breaking the laws of math (was Re: Bug in my published 34 yr old formula !?)
by Bill Gosper 10 Jun '18

10 Jun '18

The early 60s Friden mechanical calculator could be semi-destroyed by taking the square root of a 20-digit product when the carriage was too close to the wall. Hundreds of dollars when dollars were worth something. --rwg Flashback: This was at a Naval Air Development Center, divided into several large Labs. There was an Airborne Electronics Lab where they worked (rather unsuccessfully) on flat panel displays, a gyro navigation lab, and a lab with a human centrifuge where the Mercury Astronauts trained. There was also ACL, the "Airborne" Computer Lab. My lab was Antisubmarine Warfare Systems Analysis. About all we did was compute. On mechanical calculators! Because ACL had a political stranglehold forbidding the other labs from owning computers! If you needed a computation, you submitted it to ACL. And _months_ later, you got your pathetic results. Because they were a bunch of government fossils who only did plugboard analog! The stranglehold finally broke in 1962, when my lab got its first computer--a PB250 with delay-line memory, programmed in octal, with seven ways to get a quotient|remainder wrong, but a perfect square root instruction! It is outrageous that square root took decades to show up in mainstream instruction sets. Logic designers apparently failed to notice how simple the schoolboy algorithm is in binary. So it didn't get into C. And who would design an instruction not in C? On 2018-06-10 12:14, Keith F. Lynch wrote: > "David Wilson" <davidwwilson(a)comcast.net> wrote: >> Tomas Rokicki wrote: >>> I suspect the laws of mathematics may have changed over those >>> 34 years. > >> Or at least the fines and jail terms. > > I once got in serious trouble for breaking the law against dividing > by zero. > > When I was a small child, my father let me visit his office and play > with his electro-mechanical calculator. He warned me not to divide > by zero, but I did it anyway. The machine started grinding away, and > kept going and going. Pulling the plug made it stop, but it started > again as soon as it was plugged in again. He told me it had to be > sent back to the factory for repairs. > > For youngsters who have no idea what I'm talking about, I found > a video of someone doing the same, only on a machine that has an > interrupt switch: https://www.youtube.com/watch?v=7Kd3R_RlXgc > For youngsters who have no idea what I'm talking about, I found a video of someone doing the same, only on a machine that has an interrupt switch: https://www.youtube.com/watch?v=7Kd3R_RlXgc

3 2

[math-fun] Punishment for breaking the laws of math (was Re: Bug in my published 34 yr old formula !?)
by Keith F. Lynch 10 Jun '18

10 Jun '18

"David Wilson" <davidwwilson(a)comcast.net> wrote: > Tomas Rokicki wrote: >> I suspect the laws of mathematics may have changed over those >> 34 years. > Or at least the fines and jail terms. I once got in serious trouble for breaking the law against dividing by zero. When I was a small child, my father let me visit his office and play with his electro-mechanical calculator. He warned me not to divide by zero, but I did it anyway. The machine started grinding away, and kept going and going. Pulling the plug made it stop, but it started again as soon as it was plugged in again. He told me it had to be sent back to the factory for repairs. For youngsters who have no idea what I'm talking about, I found a video of someone doing the same, only on a machine that has an interrupt switch: https://www.youtube.com/watch?v=7Kd3R_RlXgc

2 1

[math-fun] Fear of palindromes
by Victor Miller 10 Jun '18

10 Jun '18

The word describing fear of palindromes, is itself a palindrome: aibohphobia. Victor

2 1

[math-fun] Turing & linear algebra
by Henry Baker 07 Jun '18

07 Jun '18

Today is the 2^6-th anniversary of Turing's death. Although most of us know him for his work in computability and decryption, he also did some very interesting work in linear algebra. I looked him up in Wikipedia, and they talk about his work with LU decomposition. From what I can Google, Turing didn't invent LU decomposition, and probably heard about it from Von Neumann. What Turing did do was generalize LU for rectangular matrices, and provide error analyses. But wait, I think there's more! I recall reading a paper or hearing a lecture about Turing & matrices in which Turing inadvertently got two matrix factors *backwards*, and the algorithm not only worked -- it worked better! This example showed the cleverness of Turing to push forward when a linear algebra "expert" would never have proceeded due to the obvious mistake. Unfortunately, after Googling for an hour or so, I can't find the reference. I think I must have read the paper or heard the lecture in 2012, the 100'th anniversary of Turing's birth.

1 0