- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Fwd: Fibonacci divisibility
by Bill Gosper 07 Jun '17

07 Jun '17

Hilbert's 10th was: How do you find the integer solutions (= "Diophantine") to multivariate polynomials. Matiyasevic et al showed that, in general, you can't. The problem is Turing complete. For example, somebody constructed a polynomial in n, p, and a couple of dozen auxiliary variables that can only vanish when p is the nth prime! Matiyasevic once sent me a book. (Soviet era, incredibly cheaply made.) Insensitive to what must have been his austere economic situation, I sent him several packets of Pop Rocks. I addressed the envelope in Cyrillic, and John McCarthy impishly had me append "имени Ке́ренский" to the name of the research facility. Kerensky was much despised in Soviet propaganda. I think the book was one about hypergeometric identities. One such, written with binomial coefficients, mentioned "Moriarty" in cyrillic. I hit the ceiling, thinking that the Russians had fallen for some prank, based on the Sherlock Holmes quote, "At the age of twenty-one, he wrote a treatise upon the binomial theorem <https://en.wikipedia.org/wiki/Binomial_theorem>, which has had a European vogue." I sent a xerox to Martin Gardner, who sent it to the Baker Street Irregulars, who sent it to the CIA. But the hoax was on me. One Harold Davis discovered the theorem, and playfully named it Moriarty's. https://en.wikipedia.org/wiki/A_Treatise_on_the_Binomial_Theorem Had my Russian been better, I'd've noticed that "Дэвиса" was not a "device", but rather how they spell "Davis". --rwg ---------- Forwarded message ---------- From: Warren D Smith <warren.wds(a)gmail.com> Date: Wed, Jun 7, 2017 at 4:04 PM Subject: Fibonacci divisibility To: billgosper(a)gmail.com, marniekanarek(a)gmail.com The fact that GCD[Fibonacci[a], Fibonacci[b]] == Fibonacci[GCD[a, b]], is proven as lemma 4 on p.221 in John H. Halton: ON THE DIVISIBILITY PROPERTIES OF FIBONACCI NUMBERS (1966) http://www.fq.math.ca/Scanned/4-3/halton.pdf Halton also in lemma 5 says F_m is divisible by F_n , if and only if either m is divisible by n, or n = 2. Divisibility properties like these were a key ingredient of the famous proof by Julia Robinson et al, that established the undecidability of diophantine equation solving. Robinson et al had everything they needed except for this missing ingredient, which was found by Yuri Matiyasevich thus competing the proof in 1970. However, it would seem Robinson et al could have avoided the need for Matiyasevic if they had bothered to read this 1966 paper by Halton? See https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

1 0

Re: [math-fun] When I'm 64
by Bill Gosper 07 Jun '17

07 Jun '17

The MIT Life hackers once got an absolutely surreal demo of the "PDP-3" in the basement of Searle Medidata, out on rte 128, by it's sole caretaker, builder(?), and programmer Charles Corderman. If memory serves, some salesman leaked that DEC was building a 36 bit challenge to IBM's mainframes, and Searle staked much on this belief. When it became clear that DEC was abandoning the project, Searle insisted on seeing the plans, and charged Corderman with completing them. The machine computed parity nearly everywhere. What a waste of bits. So Corderman changed it to a 37bit machine! He then built an *entirely* menu-driven OS, where the only pointing device was a light pen! To make things weirder, the Type 30 display had a purple phosphor. On the console was a Flexowriter, powered off. We expressed suspicion that he had programmed his (utterly peculiar) OS on it. "No, but it does work," he said, powering it on, and waving his light pen. The Flexowriter typed a lowercase "r", and he powered it off. (Kids: The only data from a light pen is a single bit, saying whether or not it saw the most recent point flashed on the (non rastered) screen. During one second, the machine was only fast enough to light a very few thousand of the 2^20 addressable points. The pen's field of view depended on how close it was to the screen, but it needed to be pretty close. How can you possibly do anything useful with such a thing?) This is the machine with which Corderman found his famous Switch Engines, http://www.conwaylife.com/w/index.php?title=Switch_engine , bizarre c/12 diagonal puffers, one of which shoots (Doppler shifted) gliders out the front! Or did I dream all this? --rwg On 2017-06-07 16:39, Fred Lunnon wrote: > Manchester Atlas I with 48-bit words. WFL > > On 6/8/17, Eugene Salamin via math-fun <math-fun(a)mailman.xmission.com> wrote: >> My first computer was the IBM 650. It had 2000 10-decimal digit words >> stored on a rotating magnetic drum. Senior year in high school class in >> applied math in 1959, IBM gave us access to their computer. It was punch >> cards, card sorters, and line printers. >> >> -- Gene >> >> >> On Wednesday, June 7, 2017, 3:52:26 PM PDT, Victor Miller >> <victorsmiller(a)gmail.com> wrote: >> >> And 60 bit (cdc). I also programmed a univac 418 -- 18 bit 1's complement >> >> >> On Wed, Jun 7, 2017 at 18:40 Tom Knight <tk(a)mit.edu> wrote: >> >>> You left out the 40 bit machines… >>> >>> > On Jun 7, 2017, at 3:50 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: >>> > >>> > FYI -- >>> > >>> > "Will you still need me, will you still feed me >>> > When I'm 64?" >>> > >>> > I've now lived through: >>> > >>> > decimal computers (IBM 1620, IBM 1401) >>> > 36-bit/15-18bit-address computers (IBM 7040, IBM 7090, GE635, PDP-10, >>> DEC-20) >>> > 12-bit computers (PDP-8) >>> > Microcoded machines (Xerox Alto, Lisp Machines) >>> > 1-bit computers (ICL DAP 32x32x1 "square word", Connection Machine) >>> > 4-bit computers (Intel 4004) >>> > 8-bit computers (6502, Z-80, 8080, 8051 (still used inside "USB flash >>> drives"!), 6800, etc.) >>> > 16-bit computers (PDP-11, Moto 68000, 8086, etc.) >>> > 32-bit computers (IBM 360, VAX, 80386, ARM, etc.) >>> > 64-bit computers (everyone!) >>> > >>> > It remains to be seen if I'll make it to 128 or 256... >>> > >>> > Son of a bits! >>> > --- >>> > >>> https://apple.slashdot.org/story/17/06/07/0538233/apple-to-phase-out-32-bit… >>> > >>> > Apple To Phase Out 32-Bit Mac Apps Starting In January 2018 >>> > >>> > Apple will be phasing out 32-bit apps with iOS 11, and soon the company >>> will make the same changes on its macOS operating system. During its >>> Platform State of the Union keynote at the Worldwide Developers >>> Conference, >>> Apple told developers that macOS High Sierra will be the "last macOS >>> release to support 32-bit apps without compromises." >> _______________________________________________

2 1

[math-fun] Minsky/Trinsky questions
by Bill Gosper 07 Jun '17

07 Jun '17

Date: 2017-06-05 17:48 From: Henry Baker <hbaker1(a)pipeline.com> To: math-fun(a)mailman.xmission.com Reply-To: math-fun <math-fun(a)mailman.xmission.com> >What is known about which orbit sizes are possible? By size, you must mean period, since x₀ and y₀ can be anything. I'm pretty sure we found many a small set of multipliers (δ, ε) whose periods grew periodically with (x₀, 0), say, covering the integers. If not, I'll bet Julian can construct such a covering fairly easily. Another approach: Removing the Floor functions yields an exactly solvable recurrence of any real "period", independent of (x₀, y₀). When these are large, restoring the Floor functions has only a small effect. I'm guessing you'd only need to try a few. Which isn't much help if you need exactly a googol and one. >What is known about which orbit sizes are impossible? The above, if correct, says no period is impossible. >How many bits of state are required for an orbit of size N ? (non-trivial max ?, non-trivial min ?) For fixed multipliers (δ, ε), the state is entirely contained in the current point (xn,yn). Usually, a very small shift in x₀ and y₀ will simply translate the whole orbit by that shift. Often, a small shift in (δ, ε) will not change the orbit at all. E.g., the large rectangles in the (mysteriously cropped) "Monster" plot on p12 of gosper.org/g12a.pdf (un-animated part of the talk). But see the discussion of accumulation points in the book. (Speaking of the animations, the one Rohan misprepared, "The worst circle I ever drew", should have drawn gosper.org/circle.png . Try to picture a Minsky making that!) >The video <https://youtu.be/lXsVWwPa7bc> talks about parallelizing; is there any kind of "speedup" -- e.g., repeated squaring of matrices or some such? No. NeilB figured out how to heuristically subdivide the space of possible (x,y) starting points with about a 12% chance of connecting up with the desired orbit, so breakeven needed about eight processors. Although TomR never managed to close the Minsky Stock Index, he did manage to close disjoint loops of record length, in the quadrillions. >Suppose that a Minsky orbit of size N is known; how hard is it to map the integers 1..N to the elements of the orbit, You just count. We don't have a way of jumping ahead a prescribed distance. > and how hard is it to map back? Or is a table lookup the fastest method in both directions? More generally, can I use Minsky orbits for addition mod N ? I don't know. Which is the answer to most questions about Minskyspace. >Are there any Minsky orbits which "decompose" into direct products of Minsky orbits? (I'm not entirely certain how such a direct product would work, but perhaps the peculiarities of particular numbers might allow the separation of a "high order" part and a "low order" part that happen not to interfere with one another.) Julian? Help! >Does Minsky/Trinsky work on any other algebraic objects other than standard integers -- e.g., polynomials over Q in a single variable ? Probably. Important: The algorithm described in the talk and the book is over the reals, not the integers. >Perhaps I didn't understand the video well enough, but are there elegant cellular automata that perform the Minsky/Trinsky computation? I'd be surprised. --Bill

3 4

Re: [math-fun] math-fun Digest, Vol 171, Issue 35 re Bathroom square dance tilings
by Stuart Anderson 07 Jun '17

07 Jun '17

> But all that's completely irrelevant to my purpose, which is simply to > enquire if these tilings have an established name --- preferably one rather > more euphonious than my current nomenclature: The bathroom floor tiling! > > Fred Lunnon Wikipedia has a good article on these tilings; Wikipedia.org/wiki/Pythagorean_tiling There are 4 names given: Pythagorean tiling Two squares tessellation Hopscotch pattern Pinwheel pattern (not to be confused with pinwheel tiling) The only other thing about these tilings I am aware of that is not mentioned in the article is that these tilings can tile a torus. See Geoffrey Morley's article www.squaring.net/sq/st/st.html Stuart Anderson

4 4

Re: [math-fun] More Minsky-Trinsky questions
by Henry Baker 06 Jun '17

06 Jun '17

This question might be related to my question re other algebras -- e.g., complex numbers (Gaussian integers). Speaking of which, the computer graphics folks have done wonderful things by using *quaternions* instead of *complex numbers* in their *fractal pix*. Perhaps a *quaternion* Minsky/Trinsky would provide some really fun & pretty pix, as well? At 12:02 PM 6/6/2017, James Propp wrote: >What if anything is known about Minsky-ish maps whose orbits approximate >hyperbolas rather than circles and ellipses?

1 0

[math-fun] More Minsky-Trinsky questions
by James Propp 06 Jun '17

06 Jun '17

Is it ever possible to predict that two far-apart points will belong to the same orbit? Is it ever possible to predict that an orbit will exhibit 180-degree rotational symmetry? (This is related to the first question, since the orbit of (i,j) has 180-degree rotational symmetry iff (-i,-j) is in the same orbit as (i,j).) What if anything is known about Minsky-ish maps whose orbits approximate hyperbolas rather than circles and ellipses? Jim Propp

1 0

Re: [math-fun] Minsky/Trinsky questions
by Henry Baker 06 Jun '17

06 Jun '17

Now you've lost me. The the video starts by talking about the Minsky algorithm over the integers. Where did the reals come in? Also, if you're calculating with floating point numbers, how can you be so sure that the algorithm is exactly invertible? At 01:15 AM 6/6/2017, Bill Gosper wrote: >Important: > >The algorithm described in the talk and the book is over the reals, not the integers.

1 0

[math-fun] Defending infinity
by James Propp 05 Jun '17

05 Jun '17

In recent email conversation with a polite but insistent .999... dissenter, I've been made aware of strands of thought that rejects the mathematical concept of infinity as being unrealistic, incoherent, and repugnant (three different charges requiring three different sorts of defense). There are books and articles and on-line videos that approach the topic of infinity from different angles, but are there any that address these attacks head-on? It's possible that what's really being rejected (at least by some dissenters) is not the concept of infinity in isolation but the whole enterprise of making deductions in imaginary worlds (like the world of Euclidean geometry) to draw conclusions that are applicable in our world. A convincing defense of "unrealistic" concepts like a Euclidean point or the set of all counting numbers should in my opinion include an admission that we don't know why the mathematical enterprise has been so successful (the "unreasonable effectiveness" phenomenon). What's been done along these lines? One thing that's relevant, sort of, is an essay by Isaac Asimov in which young Isaac gets into an argument with a philosophy professor, challenging him to produce half a piece of chalk and then pointing out that it's probably not exactly HALF. But I think the philosopher was onto something when he got the whole in-class argument started by insisting that mathematicians are idealists because they believe in imaginary numbers. Old Isaac's point in his essaywas that complex numbers, properly understood, are no more fanciful than ordinary fractions; but you can turn this around and say that ordinary fractions, properly understood, are no less fanciful than complex numbers. Jim Propp

2 1

Re: [math-fun] Defending infinity
by Henry Baker 05 Jun '17

05 Jun '17

Perhaps I'm a bit warped, but having had a fair amount of mathematical logic, what with axioms, theories, models and such, I no longer believe in numbers, infinities, etc., in ways that seem to tie many people up in knots. There are usually many different models for the same theory, so it becomes kind of pointless to worry about which one is "best", because different models produce different insights. If one person thinks of +oo as the limit "point" of the positive integers, that's great; if someone else wants to deny pointhood to +oo, but rather talk about some sort of a limit, that's also great. WRT .999... v. 1.000..., there are often congruence classes of representations that can't be distinguished with a certain class of operations -- this happens all the time in computer science when we have to choose a digital representation for an object, and keeping the object in a "canonical" form is (or seems to be) too much work -- e.g., a rational fraction representation that doesn't always "reduce to lowest common terms". At 07:45 AM 6/5/2017, James Propp wrote: >In recent email conversation with a polite but insistent .999... dissenter, >I've been made aware of strands of thought that rejects the mathematical >concept of infinity as being unrealistic, incoherent, and repugnant (three >different charges requiring three different sorts of defense). > >There are books and articles and on-line videos that approach the topic of >infinity from different angles, but are there any that address these >attacks head-on? > >It's possible that what's really being rejected (at least by some >dissenters) is not the concept of infinity in isolation but the whole >enterprise of making deductions in imaginary worlds (like the world of >Euclidean geometry) to draw conclusions that are applicable in our world. A >convincing defense of "unrealistic" concepts like a Euclidean point or the >set of all counting numbers should in my opinion include an admission that >we don't know why the mathematical enterprise has been so successful (the >"unreasonable effectiveness" phenomenon). > >What's been done along these lines? > >One thing that's relevant, sort of, is an essay by Isaac Asimov in which >young Isaac gets into an argument with a philosophy professor, challenging >him to produce half a piece of chalk and then pointing out that it's >probably not exactly HALF. But I think the philosopher was onto something >when he got the whole in-class argument started by insisting that >mathematicians are idealists because they believe in imaginary numbers. Old >Isaac's point in his essaywas that complex numbers, properly understood, >are no more fanciful than ordinary fractions; but you can turn this around >and say that ordinary fractions, properly understood, are no less fanciful >than complex numbers. > >Jim Propp

2 1

[math-fun] Minsky/Trinsky questions
by Henry Baker 05 Jun '17

05 Jun '17

What is known about which orbit sizes are possible? What is known about which orbit sizes are impossible? How many bits of state are required for an orbit of size N ? (non-trivial max ?, non-trivial min ?) The video talks about parallelizing; is there any kind of "speedup" -- e.g., repeated squaring of matrices or some such? Suppose that a Minsky orbit of size N is known; how hard is it to map the integers 1..N to the elements of the orbit, and how hard is it to map back? Or is a table lookup the fastest method in both directions? More generally, can I use Minsky orbits for addition mod N ? Are there any Minsky orbits which "decompose" into direct products of Minsky orbits? (I'm not entirely certain how such a direct product would work, but perhaps the peculiarities of particular numbers might allow the separation of a "high order" part and a "low order" part that happen not to interfere with one another.) Does Minsky/Trinsky work on any other algebraic objects other than standard integers -- e.g., polynomials over Q in a single variable ? Perhaps I didn't understand the video well enough, but are there elegant cellular automata that perform the Minsky/Trinsky computation?

1 0