Every so often, things coincide. In the last couple of days, Jeff Shaumeyer relayed on Facebook an 8/9 posting on Jason Kottke’s blog with a delightful video about the Collatz Conjecture, and then a day later I got a phone call from Greg Huber at UC Santa Barbara about this very same conjecture in number theory and its possible connection to a paper Steve Isard and I wrote 46 years ago (in previous lives) on “one-symbol Smullyan systems”. And there’s an xkcd:
(#710 from 3/5/10)
From Kottke (with a link to the video):
For a recent episode of Numberphile, David Eisenbud explains the Collatz Conjecture, a math problem that is very easy to understand but has an entire book devoted to it and led famous mathematician Paul Erdős to say “this is a problem for which mathematics is perhaps not ready”.
The problem is easily stated: start with any positive integer and if it is even, divide it by 2 and if odd multiply it by 3 and add 1. Repeat the process indefinitely. Where do the numbers end up? Infinity? 1? Loneliness? Somewhere in-between?
The Wikipedia page is not so light-hearted:
The Collatz conjecture is a conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani’s problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse’s algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers (because the values are usually subject to multiple descents and ascents like hailstones in a cloud), or as wondrous numbers.
The conjecture can be summarized as follows. Take any positive integer n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called “Half Or Triple Plus One”, or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.
(and once you reach 1, then you loop 1 ➝ 4 ➝ 2 ➝ 1)
And then apparently from a different world, one-symbol Smullyan systems, which (speaking very loosely) operate with rules of an especially simple sort on strings of a single symbol (say, the symbol 1). Collatz sequences are described by the two productions (in a simplified formalism):
xx —> x (the even case)
xx1 —> xxxxxx1111 (the odd case)
On one-symbol Smullyan systems (with a link to the paper on my blog):
Stephen Isard & Arnold Zwicky, “Three open questions in the theory of one-symbol Smullyan systems” (SIGACT News, 1970).
The paper considers some open questions having to do with oss’s and the stringsets they generate, in particular the question of whether there’s an oss that generates the set of all strings of 1s of square length (an especially simple-sounding question).
Meanwhile, Greg Huber (and his student Kyle Kawagoe) at the Kavli Institute for Theoretical Physics at UC Santa Barbara, who had been hacking at Collatz, somehow came across Isard & Zwicky, saw some possible overlap between sets generated by oss’s and Collatz sequences, and phoned me to ask if the unsolved problems from 1970 had been solved. To my knowledge, no; in fact, Steve and I weren’t sure that anyone had ever read our paper, beyond the two of us and Dana Scott, who we cited at length.
Onwards and sideways with mathematics…
August 12, 2016 at 7:18 am |
From Jason Parker-Burlinghama link on Facebook to Chris Given’s Blog on 8/12/16, a program that creates a force directed graph of the Collatz conjecture containing all numbers up to 500:
https://bl.ocks.org/cmgiven/231f779f9655025f38b5b4b828f3b7b0
The program runs “backwards”, from an nteger to its Collatz predecessor, so that some integers have two links: 10 preceded by 20 or 3, 16 preceded by 32 or 5.