mitcc mitcc - 4 years ago 73
Java Question

Too long runtime of euler project #14 in Java

My code of Euler Project 14 is below. I have run this code for more than 3 hours with output result and it seems to be infinite. When I test a single number such as 11, 27, it will output the collatz chain number:14 and 111 quickly. But I don't know why it couldn't output 1000000 number's max chain number.

/*Problem 14
* 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.
*/
package number;
public class LongestCollatzSequence {
public static int collatzNum(int n){
int count = 0;
while(n != 1){
if(n%2 == 0)
n = n/2;
else
n = 3*n + 1;
count++;
}
return count;
}
public static void main(String[] args) {
int max = 0;
for(int i = 10; i <= 1000000; i++){
if(collatzNum(i) > collatzNum(max))
max = i;
}
System.out.println(max);
}
}


Furthermore, I turn
for(int i = 10; i <= 1000000; i++)
to
for(int i = 10; i <= 10; i++)
, such a short list of numbers, it is still running all the time without output. What's wrong with my code?

Here is another person's resolution, rianjs.net the code is :

public class Problem014
{
public static void main(String[] args)
{
long begin = System.currentTimeMillis();
LinkedList<Long> list = new LinkedList<Long>();
long length = 0;
int res = 0;
for(int j = 10; j < 1000000; j++){
long i = j;
while (i != 1){
if (i % 2 == 0){
i /= 2;
list.add(i);
}
else{
i = (3 * i) + 1;
list.add(i);
}
}
if(list.size() > length){
length = list.size();
res = j;
}
list.clear();
}
long end = System.currentTimeMillis();
System.out.println(res+" with chain size: "+ length);
System.out.println(end-begin + "ms");
}
}


His code runs well, I want to know why my code cannot get the output and what makes the difference of the two resolution?

Answer Source

The argument int n of your collatzNum function will overflow for the value 113383. As you can see, the other implementation uses a long variable for the temporary value.

In addition to that, you can optimize your code a lot by not calculation collatzNum(max) for each loop iteration, but only when max actually changes, in which case you already have the new collatzNum(max)as a return value from collatzNum(i).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download