## Saturday, March 17, 2012

I think every regular, or even semi regular xkcd reader is familiar with the Collatz Conjecture

I have always found this problem intriguing, and Project Euler problem 14 did give me an excuse to codify it, but I just ran though the way I'd go about it in my head, decided the best way to do that was to use a graph, and the left it at that(didn't want to implement a graph in python, or for that matter in any language - procrastination strikes yet again!).

After a while I kinda forgot about this problem, but then it came back in the form of a homework problem in the Udacity course CS101 and a lot of the students raised a storm in the forums, some were confused, some pissed that an open problem was put in the homework for a starter course.

Inspired by a forum post I decided to write a program that finds all the collatz numbers between 1...n. Though it didn't end up doing that, it did something which I think was far more interesting and fun.

What the code did was, with an initial value of 1 already in the list, it would calculate the collatz sequence for the number 1 larger than the previous highest in the list, and stop when it finds a number already in the list, add those to the main list & sort. Then after a predetermined amount of time, it would stop the loop & store the data in a text file.

Here is the loop that does all the work -
while time.time()<=end_time:
temp_list = []
i = collatz_sequence[-1]+1
while i!=1:
temp_list.append(i)
if i%2:
i = 3*i+1
else:
i = i/2
if i in collatz_sequence:
break
collatz_sequence = collatz_sequence + temp_list
collatz_sequence.sort()
You can take a look at the entire code here.

The first time I ran the program, I let it run for 2 hours & got astounding results. It returned a list of 358105 numbers, with the largest being a mammoth 366 digits at ~5.56*10365! The file was almost 51mb in size, with 10754 pages in open office at a font size of 10 - it wouldn't open in gedit.

The second time I let it run for 6 hours and got a list of 589089 numbers, in a file of size over 122mb and 25841pages, with the largest number being 522 digits long at ~7.15*10521.

522 freaking digits!

715041398187738476801333227959007954991526117844759568970308480679542199770931086993431968999019289197177322888953758295665661575530266534166491576605100312964831303050570009751228474628925903922689608550269133879781938336998139946759276583184785636935449049784282515981693228386188628272042102082685093913159905492974745881547546773841944846123223998436305423781110799447831220034363949701495690163997376176891313276814686119218403734250272362514666040141783177826783964115283210051404879451729170704505821742552537236884
This was no serious attempt to understand or solve(lol) the Collatz Conjecture, just having a bit of fun with code, because the internet was out. But still, it is a testament to the ability of Python to handle large numbers.

Edit - This is a slightly better Collatz program, and solves the Project Euler problem mentioned earlier - collatz_cycle.py