Like many of my previous posts, this post too has something to do with a Project Euler problem. Here’s a sketch of the **Colatz Conjecture.**

The following iterative sequence is defined for the set of positive integers:

**n → n/2 (n is even)**

**n → 3n + 1 (n is**

*odd*)Using the rule above and starting with 13, we generate the following sequence:

**13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1**

So basically, it’s just this. Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has aptly been called **oneness**! But perhaps oneness has its pitfalls too…

If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence might enter a repeating cycle that excludes 1, or increase without bound. **No such sequence has been found.**

**Question**

It can be seen that the sequence:

**13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1**

contains 10 terms. Although it has not been proved yet (*Collatz* Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

**NOTE:** Once the chain starts the terms are allowed to go above one million.

**HUGE HINT:**

Histogram of stopping times for the numbers 1 to 100 million. Stopping time is on the x axis, frequency on the y axis.

**Approach 1** (A naïve, but straigh forward method)

# Longest Collatz Sequence under a million | |

# Function listing collatz sequence for a number | |

def collatz(n): | |

"function listing collatz sequence for a positive integer" | |

coll = [] | |

coll.append(n) | |

while n != 1: | |

if n % 2 == 0: | |

n = n/2 | |

coll.append(n) | |

else: | |

n = 3*n + 1 | |

coll.append(n) | |

return coll | |

longest = 0 | |

j = 0 | |

for i in xrange(1, 1000000): | |

lencoll = len(collatz(i)) | |

if lencoll > longest: | |

longest = lencoll | |

j = i | |

print j |

**Approach 2** (Smart, quick method that uses dynamic programming with the help of dictionaries)

collatz = {1:1} | |

def Collatz(n): | |

global collatz | |

if not collatz.has_key(n): | |

if n%2 == 0: | |

collatz[n] = Collatz(n/2) + 1 | |

else: | |

collatz[n] = Collatz(3*n + 1) + 1 | |

return collatz[n] | |

for j in range(1000000,0,-1): | |

Collatz(j) | |

print collatz.keys()[collatz.values().index(max(collatz.values()))] |

I couldn’t help appreciate the elegance of the second algorithm. It’ll be well worth perusing if you don’t get it at one go. [Hint: It keeps track of the number of terms of a particular sequence as *values* assigned to *keys *of a Python dictionary]

**Ans:** *837799 *