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

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!).

Theorem 1 that uses the inequality scheme in Lemma 1.
Theorem 2 that uses the inequality scheme in Lemma 2.
Theorem 3 that uses the inequality scheme in Lemma 3.
Theorem 4 that uses the inequality scheme in Lemma 4.
Theorem 5 that uses the inequality scheme in Lemma 5.
Theorem 6 that uses the inequality scheme in Lemma 6.
Theorem 7 that uses the inequality scheme in Lemma 7.
Theorem 8 that uses the inequality scheme in Lemma 8.
Theorem 9 that uses the inequality scheme in Lemma 9.
Theorem 10 that uses the inequality scheme in Lemma 10.
Theorem 11 that uses the inequality scheme in Lemma 11.
Theorem 12 that uses the inequality scheme in Lemma 12.
Theorem 13 that uses the inequality scheme in Lemma 13.
Theorem 14 that uses the inequality scheme in Lemma 14.
Theorem 15 that uses the inequality scheme in Lemma 15.
Theorem 16 that uses the inequality scheme in Lemma 16.
Theorem 17 that uses the inequality scheme in Lemma 17.
Theorem 18 that uses the inequality scheme in Lemma 18.
Theorem 19 that uses the inequality scheme in Lemma 19.
Theorem 20 that uses the inequality scheme in Lemma 20.
Theorem 21 that uses the inequality scheme in Lemma 21.
Theorem 22 that uses the inequality scheme in Lemma 22.
Theorem 23 that uses the inequality scheme in Lemma 23.
Theorem 24 that uses the inequality scheme in Lemma 24.
Theorem 25 that uses the inequality scheme in Lemma 25.
Theorem 26 that uses the inequality scheme in Lemma 26.
Theorem 27 that uses the inequality scheme in Lemma 27.
Theorem 28 that uses the inequality scheme in Lemma 28.
Theorem 29 that uses the inequality scheme in Lemma 29.
Theorem 30 that uses the inequality scheme in Lemma 30.
Theorem 31 that uses the inequality scheme in Lemma 31.
Theorem 32 that uses the inequality scheme in Lemma 32.
Theorem 33 that uses the inequality scheme in Lemma 33.
Theorem 34 that uses the inequality scheme in Lemma 34.
Theorem 35 that uses the inequality scheme in Lemma 35.
Theorem 36 that uses the inequality scheme in Lemma 36.
Theorem 37 that uses the inequality scheme in Lemma 37.
Theorem 38 that uses the inequality scheme in Lemma 38.
Theorem 39 that uses the inequality scheme in Lemma 39.
Theorem 40 that uses the inequality scheme in Lemma 40.
Theorem 41 that uses the inequality scheme in Lemma 41.
Theorem 42 that uses the inequality scheme in Lemma 42.
Theorem 43 that uses the inequality scheme in Lemma 43.
Theorem 44 that uses the inequality scheme in Lemma 44.
Theorem 45 that uses the inequality scheme in Lemma 45.
Theorem 46 that uses the inequality scheme in Lemma 46.
Theorem 47 that uses the inequality scheme in Lemma 47.
Theorem 48 that uses the inequality scheme in Lemma 48.
Theorem 49 that uses the inequality scheme in Lemma 49.
Theorem 50 that uses the inequality scheme in Lemma 50.
Theorem 51 that uses the inequality scheme in Lemma 51.
Theorem 52 that uses the inequality scheme in Lemma 52.
Theorem 53 that uses the inequality scheme in Lemma 53.
Theorem 54 that uses the inequality scheme in Lemma 54.
Theorem 55 that uses the inequality scheme in Lemma 55.
Theorem 56 that uses the inequality scheme in Lemma 56.
Theorem 57 that uses the inequality scheme in Lemma 57.
Theorem 58 that uses the inequality scheme in Lemma 58.
Theorem 59 that uses the inequality scheme in Lemma 59.
Theorem 60 that uses the inequality scheme in Lemma 60.
Theorem 61 that uses the inequality scheme in Lemma 61.
Theorem 62 that uses the inequality scheme in Lemma 62.
Theorem 63 that uses the inequality scheme in Lemma 63.
Theorem 64 that uses the inequality scheme in Lemma 64.
Theorem 65 that uses the inequality scheme in Lemma 65.
Theorem 66 that uses the inequality scheme in Lemma 66.
Theorem 67 that uses the inequality scheme in Lemma 67.
Theorem 68 that uses the inequality scheme in Lemma 68.
Theorem 69 that uses the inequality scheme in Lemma 69.
Theorem 70 that uses the inequality scheme in Lemma 70.
Theorem 71 that uses the inequality scheme in Lemma 71.
Theorem 72 that uses the inequality scheme in Lemma 72.
Theorem 73 that uses the inequality scheme in Lemma 73.
Theorem 74 that uses the inequality scheme in Lemma 74.
Theorem 75 that uses the inequality scheme in Lemma 75.
Theorem 76 that uses the inequality scheme in Lemma 76.
Theorem 77 that uses the inequality scheme in Lemma 77.
Theorem 78 that uses the inequality scheme in Lemma 78.
Theorem 79 that uses the inequality scheme in Lemma 79.
Theorem 80 that uses the inequality scheme in Lemma 80.
Theorem 81 that uses the inequality scheme in Lemma 81.
Theorem 82 that uses the inequality scheme in Lemma 82.
Theorem 83 that uses the inequality scheme in Lemma 83.
Theorem 84 that uses the inequality scheme in Lemma 84.
Theorem 85 that uses the inequality scheme in Lemma 85.
Theorem 86 that uses the inequality scheme in Lemma 86.
Theorem 87 that uses the inequality scheme in Lemma 87.
Theorem 88 that uses the inequality scheme in Lemma 88.
Theorem 89 that uses the inequality scheme in Lemma 89.
Theorem 90 that uses the inequality scheme in Lemma 90.
Theorem 91 that uses the inequality scheme in Lemma 91.
Theorem 92 that uses the inequality scheme in Lemma 92.
Theorem 93 that uses the inequality scheme in Lemma 93.
Theorem 94 that uses the inequality scheme in Lemma 94.
Theorem 95 that uses the inequality scheme in Lemma 95.
Theorem 96 that uses the inequality scheme in Lemma 96.
Theorem 97 that uses the inequality scheme in Lemma 97.
Theorem 98 that uses the inequality scheme in Lemma 98.
Theorem 99 that uses the inequality scheme in Lemma 99.
Theorem 100 that uses the inequality scheme in Lemma 100.
Theorem 101 that uses the inequality scheme in Lemma 101.
Theorem 102 that uses the inequality scheme in Lemma 102.
Theorem 103 that uses the inequality scheme in Lemma 103.
Theorem 104 that uses the inequality scheme in Lemma 104.
Theorem 105 that uses the inequality scheme in Lemma 105.
Theorem 106 that uses the inequality scheme in Lemma 106.
Theorem 107 that uses the inequality scheme in Lemma 107.
Theorem 108 that uses the inequality scheme in Lemma 108.
Theorem 109 that uses the inequality scheme in Lemma 109.
Theorem 110 that uses the inequality scheme in Lemma 110.
Theorem 111 that uses the inequality scheme in Lemma 111.
Theorem 112 that uses the inequality scheme in Lemma 112.
Theorem 113 that uses the inequality scheme in Lemma 113.
Theorem 114 that uses the inequality scheme in Lemma 114.
Theorem 115 that uses the inequality scheme in Lemma 115.
Theorem 116 that uses the inequality scheme in Lemma 116.
Theorem 117 that uses the inequality scheme in Lemma 117.
Theorem 118 that uses the inequality scheme in Lemma 118.
Theorem 119 that uses the inequality scheme in Lemma 119.
Theorem 120 that uses the inequality scheme in Lemma 120.
Theorem 121 that uses the inequality scheme in Lemma 121.
Theorem 122 that uses the inequality scheme in Lemma 122.
Theorem 123 that uses the inequality scheme in Lemma 123.
Theorem 124 that uses the inequality scheme in Lemma 124.
Theorem 125 that uses the inequality scheme in Lemma 125.
Theorem 126 that uses the inequality scheme in Lemma 126.
Theorem 127 that uses the inequality scheme in Lemma 127.
Theorem 128 that uses the inequality scheme in Lemma 128.
Theorem 129 that uses the inequality scheme in Lemma 129.
Theorem 130 that uses the inequality scheme in Lemma 130.
Theorem 131 that uses the inequality scheme in Lemma 131.
Theorem 132 that uses the inequality scheme in Lemma 132.
Theorem 133 that uses the inequality scheme in Lemma 133.
Theorem 134 that uses the inequality scheme in Lemma 134.
Theorem 135 that uses the inequality scheme in Lemma 135.
Theorem 136 that uses the inequality scheme in Lemma 136.
Theorem 137 that uses the inequality scheme in Lemma 137.
Theorem 138 that uses the inequality scheme in Lemma 138.
Theorem 139 that uses the inequality scheme in Lemma 139.
Theorem 140 that uses the inequality scheme in Lemma 140.
Theorem 141 that uses the inequality scheme in Lemma 141.
Theorem 142 that uses the inequality scheme in Lemma 142.
Theorem 143 that uses the inequality scheme in Lemma 143.
Theorem 144 that uses the inequality scheme in Lemma 144.

Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page