[CentralOH] Collatz conjecture

[Joe Knapp]

In the vein of programming exercises involving sequences (Fibonacci,
Hamming), here's another problem, a mathematical conjecture, that is very
simple to state but at present is classified as unsolved.

Start with any natural number x = 1,2,3,...

For each step:

-- if the number is odd, multiply x by 3 and add 1.
-- if the number is even, divide x by 2
-- stop if x reachs 1, else continue

That's it for constructing the sequence. E.g., starting with x=7:

7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

The conjecture is that starting from any number will eventually lead to 1.
To date, the conjecture has neither been proved, nor been disproven by
counterexample (a sequence that grows to inifinity, or comes around in a
cycle)..

Legend has it that when this problem first went around university math
departments in the 1960s, work came to a standstill at Yale and the
University of Chicago for a month. Everyone thought that surely they could
resolve this "simple" problem. A joke went around that it was a Soviet plot
to slow mathematical research in the US.

Per wikipedia:

--------------------------
Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready
for such problems." He also offered $500 for its solution. Jeffrey Lagarias
in 2010 claimed that based only on known information about this problem,
"this is an extraordinarily difficult problem, completely out of reach of
present day mathematics."
--------------------------

Pretty easy to program and explore though. To date, the conjecture has been
verified on massively parallel computers  up to about 10^20. One might say,
well it just has to be true if it's good up to that level, but who knows?

https://en.wikipedia.org/wiki/Collatz_conjecture
https://www.youtube.com/watch?v=K0yMyUn--0s&t=2s

Joe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20171027/d2146ffe/attachment.html>