mitcc - 4 years ago 73

Java Question

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++)`

`for(int i = 10; i <= 10; i++)`

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**