Locating the largest Collatz Sequence with memoization

Question

Inspired by this question I wrote a memoized form of the collatz sequence calculator.

The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (on my PC) get that value up to 1427500000, which is a large number.

I ran this particular calculator and it eventually crashed (because Java long isn't big enough) as follows:

New best: 4890328815 at 1131 chains in 342.77514018s.
Value from chain 8528817511 at length 205 is negative: -7694391518238975012
At 10000000000 of 10000000000 (100%) in 712.666022051s
Best: 4890328815 at 1131 chains.
Largest number in any chain: 7168235036980384402

That is expected and intended. I just wanted to see what the largest value it could get to was.

Feel free to comment on anything related to the code.

public class CR_150878 {
 public static void main(String[] args) {
 long maxTestValue = 10000000000l;
 int maxLength = 0;
 long maxNumber = 0;
 int chainSize = 0;
 int maxSequenceMapLength = 1427500000;
 int[] sequenceLengthMap = new int[maxSequenceMapLength];
 long largestNumberAnyChain = 0;
 long startTime = System.nanoTime();
 for (long i = 2; i < maxTestValue; i++) {
 chainSize = 0;
 long currentNumber = i;
 while (currentNumber != 1) {
 if (currentNumber > 1 && currentNumber < maxSequenceMapLength && sequenceLengthMap[(int)currentNumber] != 0) {
 chainSize += sequenceLengthMap[(int)currentNumber];
 currentNumber = 1;
 } else {
 if (currentNumber % 2 == 0) {
 currentNumber = currentNumber / 2;
 } else {
 currentNumber = 3 * currentNumber + 1;
 }
 chainSize++;
 if (currentNumber < 0) {
 System.out.println("Value from chain " + i + " at length " + chainSize + " is negative: " + currentNumber);
 currentNumber = 1;
 i = maxTestValue;
 }
 }
 if (currentNumber > largestNumberAnyChain) {
 largestNumberAnyChain = currentNumber;
 }
 }
 if (i > 1 && i < maxSequenceMapLength) {
 sequenceLengthMap[(int)i] = chainSize;
 }
 if (chainSize > maxLength) {
 maxLength = chainSize;
 maxNumber = i;
 System.out.println("New best: " + maxNumber + " at " + maxLength + " chains in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s.");
 }
 if (i % (maxTestValue / 100) == 0) {
 System.out.println("At " + i + " of " + maxTestValue + " (" + (i / (maxTestValue / 100)) + "%) in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s");
 }
 }
 System.out.println("Best: " + maxNumber + " at " + maxLength + " chains.");
 System.out.println("Largest number in any chain: " + largestNumberAnyChain);
 System.out.println("Took: " + ((double)(System.nanoTime() - startTime) / 1000000000) + " seconds.");
 }
}

The class name is intentional, it was a code rewrite to that particular Code Review question.

It's a slightly optimized algorithm, instead of doing \3ドルn+1\$ I did \$(3n+1)/2\$ to avoid having to do all sorts of math to the next number, but then I lost the accuracy of the "Largest number in any chain" and whatnot values, so I undid it. (Believe it or not a whole minute was trimmed off execution time.)

This also solves the Project Euler 14 challenge in 0.13s.

Answer 1

Heap size

The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (on my PC) get that value up to 1427500000, which is a large number.

When I try it with the same value, I run out of heap space. That may be fixable by changing my JVM settings.

Optimizing by combining steps

 if (currentNumber % 2 == 0) {
 currentNumber = currentNumber / 2;
 } else {
 currentNumber = 3 * currentNumber + 1;
 }
 chainSize++;

You say that you found that it was faster if you divided by 2 in the else as well, but it gives inaccurate chainSize values. Have you considered

 if (currentNumber % 2 == 0) {
 currentNumber /= 2;
 chainSize++;
 } else {
 currentNumber = (3 * currentNumber + 1) / 2;
 chainSize += 2;
 }

This should give an accurate chainSize value if I'm understanding the optimization properly.

Also, this uses the briefer /= notation where i /= 2; has the same value as i = i / 2;.

Or

 if (currentNumber % 2 != 0) {
 currentNumber = 3 * currentNumber + 1;
 chainSize++;
 }
 currentNumber /= 2;
 chainSize++;

I'll leave it up to you if these help with run time as well.

Don't do useless checks

You have

 if (currentNumber > largestNumberAnyChain) {
 largestNumberAnyChain = currentNumber;
 }

separate from the currentNumber update. However, in two of the three branches, you reduce the value of currentNumber.

Consider what happens if you move it into the previous code.

 if (currentNumber % 2 != 0) {
 currentNumber = 3 * currentNumber + 1;
 chainSize++;
 if (currentNumber > largestNumberAnyChain) {
 largestNumberAnyChain = currentNumber;
 }
 }
 currentNumber /= 2;
 chainSize++;

This is the only branch where currentNumber increases, so it's the only one that needs checked.

You could also move the check for negative numbers here for the same reason. Note further that the largest check and the negative check will never be true at the same time.

Avoid timing output

 System.out.println("New best: " + maxNumber + " at " + maxLength + " chains in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s.");
 }
 if (i % (maxTestValue / 100) == 0) {
 System.out.println("At " + i + " of " + maxTestValue + " (" + (i / (maxTestValue / 100)) + "%) in " + ((double)(System.nanoTime() - startTime) / 1000000000) + "s");
 }
 }
 System.out.println("Best: " + maxNumber + " at " + maxLength + " chains.");
 System.out.println("Largest number in any chain: " + largestNumberAnyChain);
 System.out.println("Took: " + ((double)(System.nanoTime() - startTime) / 1000000000) + " seconds.");

If you write this instead as

 }
 }
 double elapsed = (double)(System.nanoTime() - startTime) / 1000000000;
 System.out.println("Best: " + maxNumber + " at " + maxLength + " chains.");
 System.out.println("Largest number in any chain: " + largestNumberAnyChain);
 System.out.println("Took: " + elapsed + " seconds.");

You might find that it runs faster.

Same problem with

 System.out.println("Value from chain " + i + " at length " + chainSize + " is negative: " + currentNumber);

Measuring the time it takes to do the output distorts the overall timing. It may not matter here, but it can be a bad habit to develop.

• Der Kommissar: Regarding heap size: you can decrease that number. I have 32GB of RAM and this Java programme uses ~5.5GB of it for reference. Regarding 'inaccurate chainSize values', it gave an accurate chainSize, but an inaccurate largestNumberAnyChain value.