Implementing the Collatz Conjecture in Haskell
Inspired by Numberphile: https://www.youtube.com/watch?v=5mFpVDpKX70
Consider the series generated by the following expression:
f(x) =
if x is odd: 3*x + 1
otherwise: x/2
Lothar Collatz conjectured that, when generating the series, it will eventually reach 1 independently of the starting number. It is known that even 2^60 reaches 1.
Generating Collatz series given a starting number:
:l collatz.h
*Main> collatz 9
[9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
*Main> collatz 100
[100,50,25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
*Main> collatz 999999999
[999999999,2999999998,1499999999,4499999998,2249999999,6749999998,3374999999,10124999998,5062499999,15187499998,7593749999,22781249998,11390624999,34171874998,17085937499,51257812498,25628906249,76886718748,38443359374,19221679687,57665039062,28832519531,86497558594,43248779297,129746337892,64873168946,32436584473,97309753420,48654876710,24327438355,72982315066,36491157533,109473472600,54736736300,27368368150,13684184075,41052552226,20526276113,61578828340,30789414170,15394707085,46184121256,23092060628,11546030314,5773015157,17319045472,8659522736,4329761368,2164880684,1082440342,541220171,1623660514,811830257,2435490772,1217745386,608872693,1826618080,913309040,456654520,228327260,114163630,57081815,171245446,85622723,256868170,128434085,385302256,192651128,96325564,48162782,24081391,72244174,36122087,108366262,54183131,162549394,81274697,243824092,121912046,60956023,182868070,91434035,274302106,137151053,411453160,205726580,102863290,51431645,154294936,77147468,38573734,19286867,57860602,28930301,86790904,43395452,21697726,10848863,32546590,16273295,48819886,24409943,73229830,36614915,109844746,54922373,164767120,82383560,41191780,20595890,10297945,30893836,15446918,7723459,23170378,11585189,34755568,17377784,8688892,4344446,2172223,6516670,3258335,9775006,4887503,14662510,7331255,21993766,10996883,32990650,16495325,49485976,24742988,12371494,6185747,18557242,9278621,27835864,13917932,6958966,3479483,10438450,5219225,15657676,7828838,3914419,11743258,5871629,17614888,8807444,4403722,2201861,6605584,3302792,1651396,825698,412849,1238548,619274,309637,928912,464456,232228,116114,58057,174172,87086,43543,130630,65315,195946,97973,293920,146960,73480,36740,18370,9185,27556,13778,6889,20668,10334,5167,15502,7751,23254,11627,34882,17441,52324,26162,13081,39244,19622,9811,29434,14717,44152,22076,11038,5519,16558,8279,24838,12419,37258,18629,55888,27944,13972,6986,3493,10480,5240,2620,1310,655,1966,983,2950,1475,4426,2213,6640,3320,1660,830,415,1246,623,1870,935,2806,1403,4210,2105,6316,3158,1579,4738,2369,7108,3554,1777,5332,2666,1333,4000,2000,1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]Finding the number that generates the largest Collatz series given a list of starting points (first is the starting point, last is the length of the Collatz series):
*Main> largestCollatzNum 30
27
*Main> largestCollatzLength 30
112
*Main> largestCollatz 30
[27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
*Main> largestCollatz 100000
[77031,231094,115547,346642,173321,519964,259982,129991,389974,194987,584962,292481,877444,438722,219361,658084,329042,164521,493564,246782,123391,370174,185087,555262,277631,832894,416447,1249342,624671,1874014,937007,2811022,1405511,4216534,2108267,6324802,3162401,9487204,4743602,2371801,7115404,3557702,1778851,5336554,2668277,8004832,4002416,2001208,1000604,500302,250151,750454,375227,1125682,562841,1688524,844262,422131,1266394,633197,1899592,949796,474898,237449,712348,356174,178087,534262,267131,801394,400697,1202092,601046,300523,901570,450785,1352356,676178,338089,1014268,507134,253567,760702,380351,1141054,570527,1711582,855791,2567374,1283687,3851062,1925531,5776594,2888297,8664892,4332446,2166223,6498670,3249335,9748006,4874003,14622010,7311005,21933016,10966508,5483254,2741627,8224882,4112441,12337324,6168662,3084331,9252994,4626497,13879492,6939746,3469873,10409620,5204810,2602405,7807216,3903608,1951804,975902,487951,1463854,731927,2195782,1097891,3293674,1646837,4940512,2470256,1235128,617564,308782,154391,463174,231587,694762,347381,1042144,521072,260536,130268,65134,32567,97702,48851,146554,73277,219832,109916,54958,27479,82438,41219,123658,61829,185488,92744,46372,23186,11593,34780,17390,8695,26086,13043,39130,19565,58696,29348,14674,7337,22012,11006,5503,16510,8255,24766,12383,37150,18575,55726,27863,83590,41795,125386,62693,188080,94040,47020,23510,11755,35266,17633,52900,26450,13225,39676,19838,9919,29758,14879,44638,22319,66958,33479,100438,50219,150658,75329,225988,112994,56497,169492,84746,42373,127120,63560,31780,15890,7945,23836,11918,5959,17878,8939,26818,13409,40228,20114,10057,30172,15086,7543,22630,11315,33946,16973,50920,25460,12730,6365,19096,9548,4774,2387,7162,3581,10744,5372,2686,1343,4030,2015,6046,3023,9070,4535,13606,6803,20410,10205,30616,15308,7654,3827,11482,5741,17224,8612,4306,2153,6460,3230,1615,4846,2423,7270,3635,10906,5453,16360,8180,4090,2045,6136,3068,1534,767,2302,1151,3454,1727,5182,2591,7774,3887,11662,5831,17494,8747,26242,13121,39364,19682,9841,29524,14762,7381,22144,11072,5536,2768,1384,692,346,173,520,260,130,65,196,98,49,148,74,37,112,56,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]