Project Euler - Problem 14

Welcome to week 14 of my Project Euler series.

Problem 14:

Find the longest sequence using a starting number under one million.

Details:

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

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?

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

Code:

// Find the longest sequence using a starting number under one million.

class Problem0014

{

static void Main(string[] args)

{

int startOfLongest = 0;

int longestChain = 0;

for (int i = 1; i < 1000000; i++)

{

int chainLength = 0;

long n = i;

while (n > 1)

{

if (n % 2 == 0)

n /= 2;

else

n = (3 * n) + 1;

chainLength++;

}

if (chainLength > longestChain)

{

longestChain = chainLength;

startOfLongest = i;

}

}

Console.WriteLine(startOfLongest);

Console.Read();

}

}

Solution:

This is an interesting problem. We have the solution given to us, we just have to use it to find right answer. The algorithm that we are following is that we will divide an even number by 2 and triple an odd number then add one.  We will continue this pattern until we get the number down to one. This seems easy enough, except that we are looking for the number with the longest chain.  Theoretically every number will end up at one so we are looking for the one that takes the longest to get there.

We got our starting point (one) and our ending point (999,999) and our route.  Now to implement it.  We obviously need a loop (in the shape of a "while" since we don't actually have a set number of iterations to complete) and a couple of "if" statements in the middle to handle each situation. The rest is simply translating the algorithm into source code.  This is a very important skill to master, because most people that are going to tell you what they want from programs are not going to tell you in source code, or even easily translated pseudo code.  If they were already that far along in the software development cycle they would most likely finish it themselves!

One final note before I finish this off for today.  n is a terrible variable name! I used it simply to conform to the question and make it easier for people who are struggling to understand the logic to link it to the question. I can not stress enough the need for proper, logical, understandable, and valuable variable names. These little things can make or break the readability, and by extension the maintainability, of your code.

Until next time...

Enjoy!