Project Euler #14 — longest Collatz sequence

I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's no Java solution for #14, I'm posting this one.

Project Euler #14 problem statement

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.

This program takes a dynamic programming approach. For each number from two to a million, it checks if the number has had its Collatz sequence length calculated yet. If not, it calls a function that recursively calculates the sequence length. The function stops recursing when it reaches a number for which the sequence length has already been calculated. The sequence length for 1 is pre-populated to avoid extra logic to handle an empty dynamic store.

This program calculates the lengths of the first million Collatz sequences in about two seconds. Finding the answer (with a sequence length of 525, counting itself and the terminating 1):

837799 has the longest Collatz sequence of numbers below a million.

The program runs out of heap space at 5791096 with my JVM settings. It takes 30-40 seconds to calculate the answer for 5791095 (5,649,499 with a sequence length of 613). The maximum number in any sequence at that point is 2,412,493,616,608.

I realize the code is somewhat procedural, but I have very few methods needed here that would make sense on a CollatzSequence class. And of those that I do have, moving them might conflict with the dynamic programming. The big gain would be the ability to rename getSequenceString as toString.

Note: this was compiled with Java 6.

Problem14.java

/**
* Class to solve Project Euler Problem 14:
* What number under 1,000,000 has the longest Collatz sequence?
*
* @author Brythan
*
*/
public class Problem14 {
/**
* Dynamic store of Collatz lengths.
* For a given key, the value is the length of the Collatz sequence.
*/
private final Map<Long,Long> collatz_length_of = new HashMap<Long,Long>();

/**
* The number with the longest Collatz sequence currently stored in collatz_length_of.
*/
private long longest = 1;
/**
* The length of the Collatz sequence for longest.
*/
private long longest_length = 1;

public Problem14() {
super();

// we need to prime collatz_length_of with 1,
// so that we don't have to add a separate check
// for if == 1 everywhere we check for presence
// in collatz_length_of
collatz_length_of.put(1L, 1L);
}

/**
* @param n
* @return   The next number in the Collatz sequence of n.
*/
public static long getCollatzSuccessor(long n) {
return (n % 2 == 0) ? n/2 : 3*n+1;
}

/**
* Update the class variables so as to keep a dynamic record.
*
* @param n
* @param length  The Collatz sequence length of n
*/
public void update(long n, long length) {
collatz_length_of.put(n, length);
if ( length > longest_length ) {
longest_length = length;
longest = n;
}
}

/**
* Recursively calculates the Collatz sequence length for n,
* updating the dynamic store as it goes.
*
* @param n
* @return   The length of the Collatz sequence of n.
*/
public long getCollatzSequenceLength(long n) {
Long length = collatz_length_of.get(n);

if ( length == null ) {
length = 1L + getCollatzSequenceLength(getCollatzSuccessor(n));
update(n, length);
}

return length;
}

/**
* For every positive integer up to maximum_value,
* calculate the Collatz sequence length.
*
* @param maximum_value  The upper bound.
*/
public void fillCollatzSequences(long maximum_value) {
for ( long i = 2; i < maximum_value; i++ ) {
// this check is functionally unnecessary,
// but saves a method call
if ( ! collatz_length_of.containsKey(i) ) {
getCollatzSequenceLength(i);
}
}
}

/**
* @param n
* @return   The string representation of the Collatz sequence starting with n.
*/
public static String getSequenceString(long n) {
StringBuilder builder = new StringBuilder();

builder.append(n);
while ( n > 1 ) {
builder.append(" => ");
n = getCollatzSuccessor(n);
builder.append(n);
}

return builder.toString();
}

/**
* @return  The number with the longest Collatz sequence calculated so far.
*/
public long getLongest() {
return longest;
}
}


For testing purposes, I defined the following main method. I'm aware that for best results, I should have run it multiple times at each level and taken the average of the run times. I'm less concerned about precision of results than just seeing how they grow.

main method

    /**
* @param args
*/
public static void main(String[] args) {
long maximum_value = 5791095;

for ( int n = 10; n <= maximum_value; n *= 10 ) {
Problem14 problem14 = new Problem14();
long startTime = System.nanoTime();
problem14.fillCollatzSequences(n);
long endTime = System.nanoTime();

System.out.println("The number below " + n
+ " with the longest Collatz sequence is "
+ problem14.getLongest() + " with a sequence that is "
+ problem14.getCollatzSequenceLength(problem14.getLongest())
+ " numbers long.");
System.out.println("    " + Problem14.getSequenceString(problem14.getLongest()));

// display run time in seconds
final double timeScale = 1.0e9;
System.out.print("Time:  ");
System.out.format("%10.9f", (endTime - startTime)/timeScale);
System.out.println();
}
}


As a potential optimization, I tried replacing the recursive call with a call to an iterative function. You can see a C++ example at this question. However, this was slightly slower in my checks.

Iterative _getCollatzSequenceLength method

    /**
* Iteratively generates the Collatz sequence for n
* until a value is found in the dynamic store.
* Uses that value to calculate the Collatz lengths
* of the rest of the sequence, updating the dynamic store
* as it goes.
*
* @param n
* @return   The length of the Collatz sequence of n.
*/
private long _getCollatzSequenceLength(long n) {
Deque<Long> uncalculated = new ArrayDeque<Long>();

while ( ! collatz_length_of.containsKey(n) ) {
n = getCollatzSuccessor(n);
}

Long length = collatz_length_of.get(n);
while ( ! uncalculated.isEmpty() ) {
n = uncalculated.removeFirst();
length++;
update(n, length);
}

return length;
}


I would be interested in a reference explaining why the iterative solution is slower than the recursive solution. It's not a big difference, just in the opposite direction of my expectations. It held up under multiple runs, so it's not just experimental variation.

If someone has a way to test with much bigger numbers, I think that might be neat. Currently it always runs in less than a minute. It's memory that is the big limitation. I'm guessing between 1.5 and 2 GiB of RAM when it crashes. Alternately, perhaps I'm hitting a different limit (e.g. integer overflow). I tried switching to BigInteger, but it was horrendously slow even for small values. Perhaps I did it wrong though.

I would also be interested if there is a shortcut that I'm missing. The main trick that I'm using here is the dynamic programming memoization. Is that all that there is to this problem?

Some points:

private final Map<Long,Long> collatz_length_of = new HashMap<Long,Long>();


Standard Java Conventions for variable names is camelCase, so it would be:

private final Map<Long,Long> collatzLengthOf = new HashMap<Long,Long>();


It is all over your code. Try fixing that.

You also have inconsistent spacing. You have:

if ( length > longest_length ) {


which I consider over-spacing, and you also have:

return (n % 2 == 0) ? n/2 : 3*n+1;


which I consider under-spacing.

How I would do it:

if (length > longest_length) {


and:

return (n % 2 == 0) ? n / 2 : 3 * n + 1;


public Problem14() {
super();
collatz_length_of.put(1L, 1L);
}


The call to the super constructor is unnecessary. Just remove it:

public Problem14() {
collatz_length_of.put(1L, 1L);
}


More Ideal Solution

I would suggest the following solution:

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Problem14 {

public static CollatzSequence solve(int max) {
final Map<Long, Long> collatzLengthOf = new HashMap<Long, Long>();
long longest = 1;
long longestLength = 1;
collatzLengthOf.put(1L, 1L);
for (long i = 2; i < max; i++) {
if (!collatzLengthOf.containsKey(i)) {
long length = getCollatzSequenceLength(collatzLengthOf, i);
collatzLengthOf.put(i, length);
if (length > longestLength) {
longestLength = length;
longest = i;
}
}
}
return new CollatzSequence(longest);
}

public static long getCollatzSuccessor(long n) {
return (n % 2 == 0) ? n / 2 : 3 * n + 1;
}

private static long getCollatzSequenceLength(
Map<Long, Long> collatzLengthOf, long n) {
Long length = collatzLengthOf.get(n);
if (length == null) {
length = 1L + getCollatzSequenceLength(collatzLengthOf,
getCollatzSuccessor(n));
}
return length;
}

}

class CollatzSequence {

private final List<Long> sequence;
private final long number;

public CollatzSequence(long num) {
if (num < 1) {
throw new IllegalArgumentException(
"num cannot be less that 0. num was " + num);
}
this.number = num;
this.sequence = generateSequence(num);
}

private List<Long> generateSequence(long num) {
for (long i = num; i > 1; i = Problem14.getCollatzSuccessor(i)) {
}
return list;
}

public long number() {
return number;
}

public List<Long> sequence() {
return sequence;
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
long num = this.number;
builder.append(num);
while (num > 1) {
num = Problem14.getCollatzSuccessor(num);
builder.append(" => ");
builder.append(num);
}
return builder.toString();
}

}


Why I like this solution better:

1. I don't think creating a Problem14 object is necessary. Instead, there is a static solve() method that returns a CollatzSequence object, which stores all the necessary solution information.
2. getSequenceString() is now the overrided toString() in CollatzSequence.
3. It seems slightly faster (2000 miliseconds -> 1500 miliseconds)