# The hailstone sequence

Published on 2011-07-25Lothar Collatz, a twentieth-century mathematician, once proposed that all numbers have a property known as oneness. Collatz that for any given number `n`

, if one divides `n`

by two when it is even and multiplies it by three and adds one to the product when it is odd and then repeats the process *ad infinitum*, `n`

will eventually equal one. The various values of `n`

as it makes its way through this process are known as the number's "hailstone sequence," as `n`

on its way to one jumps up and down in value like a hailstone in a cloud, and a number's oneness is the length of its hailstone sequence. For example, 6 has a hailstone sequence of 6,3,10,5,16,8,4,2,1 and a oneness of eight. The fourteenth problem in the Project Euler sequence asks the reader to find the number under 1,000,000 with the greatest oneness. It reads:

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

`n`

→`n`

/2 (`n`

is even)

`n`

→ 3`n`

+ 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

It can be seen that this sequence (starting at 13 and finishing at 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?

This one gave me a bit of trouble, as I at first forgot to account for integer overflow. After wondering why 113,383 hadn't made it all the way down to one after 30 seconds, I stopped execution, changed `chainStep`

from an `int`

to a `long`

, and had my answer in seconds.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem014 { class Program { static void Main(string[] args) { int numWithLongestChain = 0; int numOfSteps = 0; int lengthOfLongestChain = 0; long chainStep; for (int i = 2; i < 1000000; i++) { chainStep = i; numOfSteps = 0; while (chainStep != 1) { if (chainStep % 2 == 0) chainStep = chainStep / 2; else chainStep = (chainStep * 3) + 1; numOfSteps++; } if (numOfSteps > lengthOfLongestChain) { lengthOfLongestChain = numOfSteps; numWithLongestChain = i; } } Console.WriteLine("The number with the longest chain is {0}", numWithLongestChain); } } }