Overview

 

Question

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

$$ n \rightarrow \begin{cases} \tfrac{n}{2} & \text{if } n \text{ is even} \\\\ 3n+1 & \text{if } n \text{ is odd} \\\\ \end{cases} $$

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.

click for answer

837799

Solutions

 

Java

 collatz.java https://raw.github.com/addamh/euler/master/014/collatz.java download


public class collatz {
  public static void main(String[] args) {
    int p;
    long a = 0;
    long b = 0;
    long c;
       
    for (int i =0;i<1000000;i++){
      p=1;
      c=i;
           
      while(c>1){
        if(c%2==0){
          c=c/2;
          p++;  
        } else {
          c=3*c+1;
          p++; 
        }
      }
      if(p>a){
        a=p;
        b=i;
      }
    }
    // Debug output
    // System.out.println(a+" -> "+b);
    System.out.println(b);
  }
}
$ time bash collatz.java
real	0m1.167s
user	0m1.698s
sys	0m0.097s

Ruby

 collatz.rb https://raw.github.com/addamh/euler/master/014/collatz.rb download
#!/usr/bin/env ruby

def collatz(stack, n)
  stack.push(n)
  if n > 1
    if(n % 2 == 0)
      collatz(stack, n/2)
    else
      collatz(stack, 3*n+1)
    end
  end
  return stack
end

sequence = Enumerator.new do |yielder|
  number = 0
  loop do
    number += 1
    yielder.yield number
  end
end

max = {:i => 1, :l => 0}
sequence.each do |i|
  a = collatz([], i)
  l = a.length
  if max[:l] < l
    max[:i] = i
    max[:l] = l
  end
  break if i > 1000000
end

p max[:i]
$ time ruby collatz.rb
real	1m6.439s
user	1m6.334s
sys	0m0.070s