Longest Collatz Sequence

Question

While doing my Java homework which is to implement the Collatz Conjecture, I thought of a different objective which is to find the longest Collatz sequence. My program counts the steps as follows:

public class Collatz {

static int count = 0;

    static void bilgi (int n){

        int result = n;
        System.out.println("Result: "+result+ " Step: "+count);

        if (result <= 1) {
            result = 1;
        } else if (result%2 == 0){
            result = result/2;
            count = count + 1;
            bilgi(result);

        } else {
            result = (result*3)+1;
            count = count + 1;
            bilgi(result);
        }
    }

    public static void main(String[] args) {
        bilgi(27);
    }

}

I want to find the highest step count.

Return the count from `bilgi`, and remember the highest. But use `long` for the numbers, they can become quite large. — Daniel Fischer, Nov 01 '12 at 20:49
I don't want to check them 1 by 1, for example which sequence will be the highest if I run this bilgi from 1 to 100. The longest step. — Alpan Karaca, Nov 01 '12 at 21:00
But the longest sequence would potentially have infinite length. In fact, it is possible to prove that for any number n, there exists a Collatz sequence of length n. So expect to wait a long time looking for the LONGEST sequence. — , Nov 02 '12 at 18:25
The point about Collatz, unlike Fibonacci, is that numbers in the range 1..n can map (via the k→ 3k+1 step) to outside the range (higher). So running from 1..100 will require computing Collatz for select points outside that range too. [Example for 27](https://en.wikipedia.org/wiki/Collatz_conjecture#Examples). Unlike Fibonacci, the runtime for a range isn't deterministic (or even bounded, for large n, although it's been verified for 64-bit naturals). — smci, Apr 10 '18 at 05:21

score 3 · Accepted Answer · answered Nov 02 '12 at 07:46

3

static int bilgi(int n) {
    int result = n;
    if (result <= 1) return 1;
    if (result % 2 == 0) return 1+bilgi(result/2);
    return 1+bilgi(3*result+1);
}

Then you collect the results of bilgi(i) calls and select maximal.

answered Nov 02 '12 at 07:46

Vesper

18,599
6
39
61

score 2 · Answer 2 · answered Aug 31 '13 at 02:01

2

The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps. For starting numbers less than 1 billion it is 670,617,279, with 986 steps, and for numbers less than 10 billion it is 9,780,657,630, with 1132 steps

source: http://en.wikipedia.org/wiki/Collatz_conjecture

answered Aug 31 '13 at 02:01

SureshS

589
8
23

1

OP's objective is to write a java class that will determine this result, not to take Wikipedia's word for it. – Ryan B. Dec 28 '16 at 05:00

score 0 · Answer 3 · answered Jul 29 '14 at 20:08

If you're looking for max between 1 and 100 you could replace:

public static void main(String[] args) {
    bilgi(27);
}

with :

public static void main(String[] args) {

    static int maxcountsofar = 0;
    static int start = 0;
    static int thisone = 0;
    for (int iloop = 1; iloop <= 100; iloop++)
    {
       thisone = bilgi(iloop);
       if (thisone > maxcountsofar)//if this one is bigger than the highest count so far then
      {
        start = iloop;//save this information as best so far
        maxcountsofar = thisone;
      }
    }
    System.out.println("Result: " + start.Tostring() + " Step: " + maxcountsofar.Tostring() );
    //I know this is a really old post but it looked like fun.

}

/* also, take the println() out of the bilgi() function, it would generate a line for each step encountered which would be worthless and extremely time consuming.

Use Vesper's bigli() because it's much faster than yours. */

score 0 · Answer 4 · answered Jun 27 '16 at 02:35

0

I know this is an old question, but I was just solving it and I would suggest for anyone doing this, just using an arraylist and getting the .size(), I did it that way, because I wanted to see the values as well.

answered Jun 27 '16 at 02:35

Spider

431
7
21

Longest Collatz Sequence

4 Answers4