Finding the longest Collatz sequence cycle

Question

I wrote a program to calculate Collatz sequences for initial numbers between 1 and a given integer i, then find the one with the largest cycle length. My code is pretty fast, but I want to increase the speed more. Please have a look at my code and if there are any changes to made in my code to make it faster.

import java.util.Scanner;
class asgn {
public static void main(String args[]){
long i,j,n,max=0, pos=0, x,y;
long count=0;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the positive integer:");
while(sc.hasNextLong())
{x=System.currentTimeMillis();
 i= sc.nextLong();
long arr[] = new long [50000000];
 for(j=1;j<=i;j++)
{
n=j;
count = 0;
while(n!=1)
{
if(n<50000000)
{if(arr[(int)(n-1)]!=0)
{ count=count+arr[(int)(n-1)];
break;
}}
if(n%2==0)
{n=n/2;
count++;
}
else
{
n = (3*n)+1;
count++;
}
}
if(j<50000000)
arr[(int)(j-1)]=count;
if(count>max)
{max=count; pos=j;}
count=0;
}
y=System.currentTimeMillis();
System.out.println("Maximum cycle length occurs at "+pos+" and the number of steps involved "+max+"\n Total time taken is "+(y-x)+"milliseconds");
break;}}}

• ChrisWue: What is the definition of the cycle length?
• 200_success: Avoiding the use of indentation, spaces, comments, and descriptive variable names won't make your code any faster.
• 200_success: @ChrisWue From n = (3*n)+1; and n=n/2; I deduce that the problem is about Collatz sequence cycles.

Answer 1

Formatting

USE PROPER INDENTATION - Please!

If you're using Eclipse, press Ctrl + Shift + F.

If you're using Netbeans or IntelliJ, press Alt + Shift + F.

If you're not using any IDE, start doing so!

---

Braces

Once your code is properly formatted it can be seen that you're not using braces here:

if (j < 50000000)
 arr[(int) (j - 1)] = count;

It is especially important to use braces when you're code's not formatted properly, as it is easy to accidentally add an extra statement inside the if, which would cause unexpected results.

if (j < 50000000) {
 arr[(int) (j - 1)] = count;
}

---

Close Scanner

Scanners should be closed when they have been used. sc.close(); at the end of your program will take care of that.

---

Unnecessary outer while

Your outermost while "loop" is only executed once because there is a break; at the end of it. This could be an if instead and the break; at the end removed.

---

Use the length of the array

if (j < 50000000) {

and

if (n < 50000000) {

Should instead be:

if (j < arr.length) {

and

if (n < arr.length) {

respectively.

---

Slight simplification

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

Can be written as:

n = (n % 2 == 0 ? n / 2 : (3 * n) + 1);
count++;

Or at least, if you don't like the conditional operator (... ? ... : ...), use the if-else for n but do count++ before or after the if/else.

---

Variables

Your naming leaves some things to be desired. x and y for example should be named startTime and endTime, the current names makes it sound like it is related to coordinates, which it is not.

The only variable with any meaning is max and count. It is hard to tell what kind of max max is though, naming it maxCycles would make that clearer.

As for your other variables, long i, j, n, pos, I certainly cannot tell what they're used for without looking at your code for a while. These variable names tell me absolutely nothing!

To get a better overlook of the variables, it is better to declare the variables as close to their usage as possible. y (endTime) is declared at the top, but not used until the end of the method.

---

Extract Method

Your main method is doing way too many things right now.

Extract parts of your code to different methods:

For example, your entire while (n != 1) loop can be extracted to a determineCycles method.

---

Speed Improvement

Currently you're saving the result of one calculation into your array, and while that's a good start you are missing out on some values you can use.

Let's take the example of 3. The sequence is: 3, 10, 5, 16, 8, 4, 2, 1

The only result you are storing from this operation is 3 --> 7. But you have also found out that 10 has the value 7 - 1, 5 has the value 7 - 2, 16 has the value 7 - 3 and so on... Your algorithm would increase significantly in speed if you were also storing these intermediate values.

Answer 2

In addition to Simon's answer

Use the length of the array

Store the length of the array in a long and compare against this long, in this way you won't need to check each time for the length of the array.

long arr[] = new long[500000];
long arrayLength = arr.length;

so

if (j < arr.length) {

should be instead

if (j < arrayLength) {

and so on.

Speed

The fastest way (at least in java) for checking if a number is odd or even, is to look at the least significant bit of the number. If the least significant bit is 0 then and only then the number is even.

So using Simon's simplification this results in:

n = ((n & 1) == 0 ? n / 2 : (3 * n) + 1);

which had given me for the given n = 200000L repeating 100 times these results:

Your version as is: 3099 ms

Version using bit check: 1820 ms