Locating the largest Collatz Sequence with memoization

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 1 && currentNumber largestNumberAnyChain) {
largestNumberAnyChain = currentNumber;
}
}

if (i > 1 && i 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.")

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.

StackExchange Code Review Q#150900, answer score: 2