Teaching the Computer how to Discover(!) and then Prove(!!) (all by Itself(!!!)) Analogs of Collatz's Notorious 3x+1 Conjecture

By Doron Zeilberger

.pdf   .ps   .tex  
Written: March 22, 2009.

[Appeared in J. of Difference Equations and Applications, v. 17, No. 3, (March 2011) , 375-386]

Paul Erdos claimed that mathematics is not yet ready to settle the 3x+1 conjecture. I agree, but very soon it will be! With the exponential growth of computer-generated mathematics, we (or rather our silicon brethrern) would have a shot at it. Of course, not by number crunching, but by symbol crunching and automatic deduction. In the present article, I taught my computer how to use the brilliant ideas of four human beings (Amal Amleh, Ed Grove, Candy Kent, and Gerry Ladas) to prove two-dimensional analogs of this notorious conjecture. Once programmed (using my Maple package LADAS) it reproduced their ten theorems, and generated 134 new ones, complete with proofs. All by itself! I believe that the proof of the original 3x+1 conjecure would be in the same vein, but one would need a couple of extra human ideas, and better computers.
Added May 11, 2010: Watch the movie (produced by Edinah Gnang)
Maple Packages
Important: This article is accompanied by Maple packages
  • LADAS, a Maple package that does all the phases of mathematical research, conjecturing, suggesting proofs, and formally proving.
  • COLLATZ, a Maple package that (empirically) investigates one-dimensional generalizations of the 3x+1 conjecture, where instead of mod 2, you can have mod m. It is "just" for empirical investigation, and so far has no proving capabilities.

144 Computer-Generated Collatz-Type Theorems and Proofs produced with the Maple package LADAS
Assuming that you have downloaded the Maple package LADAS as well as the input file inSefer, and you type (in Linux or Unix):
maple -q < inSefer > oSefer
you would get, after 1444 seconds of CPU time, the following marvelous 144 theorems and lemmas (complete with proofs!).
Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page