Here is another solution. It is not as efficient as Peter's answer, but it is easier to understand:
public class P14 {
public static void main(String[] args) {
getMaxLength(1000000);
}
private static void getMaxLength(int threshold) {
long maxLength = 1;
int nr = -1;
for (int i = 3; i < threshold; i++) {
long sequenceSize = getSequenceSize(i);
if (sequenceSize > maxLength) {
maxLength = sequenceSize;
nr = i;
}
}
System.out.println(nr);
}
private static long getSequenceSize(int n) {
long x = n;
long count = 1;
while (x > 1) {
if ((x & 1) == 0) { // x%2==0
x = x >> 1; // x=x/2
count++; // count=count+1
} else {
x = x + x + x + 1; // x=3*x+1
x = x >> 1; // x=x/2
count+=2;
}
}
return count;
}
}
Time: 1.5 seconds (Peter's solution takes 0.142 seconds on my machine)
It can be considerably improved using the following observation: if we have x
, 2*x
will have one more step in the sequence (because 2*x
is even). This is why we can ignore numbers that are less than one half. So, using the following getMaxLength
method:
private static void getMaxLength(int threshold) {
long maxLength = 1;
int nr = -1;
int start = (threshold>>1) - 1; // start = threshold/2 - 1
for (int i = start ; i < threshold; i++) {
long sequenceSize = getSequenceSize(i);
if (sequenceSize > maxLength) {
maxLength = sequenceSize;
nr = i;
}
}
System.out.println(nr);
}
the computation will take about 0.8 seconds.