Java: Finding the largest chain in a Collatz sequence

Question

I cannot find what's wrong for Project Euler problem #14. My first step was finding the algorithm, which worked until the numbers hit around 120000. The code broke and realized that I needed to use BigIntegers. I converted my algorithm to meet that change, but now it does not work.

I've added the System.out.print(chain_length) to assist me in where my code can potentially break.

public static void main(String[] args) {
    BigInteger target = new BigInteger("1000000");
    BigInteger n = new BigInteger("0");

    final BigInteger zero = new BigInteger("0");
    final BigInteger one = new BigInteger("1");
    final BigInteger two = new BigInteger("2");
    final BigInteger three = new BigInteger("3");
    final BigInteger ten = new BigInteger("10");

    int greatest_index = 0;
    int greatest_length = 0;
    int chain_length = 0;

    BigInteger i = new BigInteger("2");
    for(i.equals(2) ; i.compareTo(target) == -1 ; i = i.add(one)) {
        n = i;
        chain_length = 1;
        while(n.compareTo(one) == -1) {
            chain_length++;
            if(n.mod(ten).equals(zero) == true){//even
                n = n.divide(two);
            }else{//odd
                n = n.multiply(three);
                n = n.add(one);
            }
            if(n.equals(one) == true && chain_length > greatest_length){
                greatest_length = chain_length;
                greatest_index = i.intValue();
            }
        }
        System.out.println(chain_length);
    }
    System.out.println(greatest_index);        
}

Just FYI, you don't need BigIntegers, long is enough.

Daniel Fischer
– Daniel Fischer

2012-12-26 05:57:43 +00:00
Commented Dec 26, 2012 at 5:57 — Daniel Fischer
– Daniel Fischer, Commented Dec 26, 2012 at 5:57

Mark Byers · Accepted Answer · 2012-12-26 02:08:29Z

7

To test if a number is even you use modulo 2, not 10. Change this line:

if(n.mod(ten).equals(zero) == true){//even

To this:

if(n.mod(two).equals(zero)) { //even

I also removed the unnecessary == true.

edited Dec 26, 2012 at 2:08

answered Dec 26, 2012 at 1:59

Mark Byers

843k202 gold badges1.6k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

irrelephant · Accepted Answer · 2013-12-26 04:04:01Z

3

In addition to @MarkByers' answer,

while(n.compareTo(one) == -1)

Should be

while(n.compareTo(one) > 0)

or, in pseudocode, while n > 1.

You should also take

if(n.equals(one) == true && chain_length > greatest_length){
    greatest_length = chain_length;
    greatest_index = i.intValue();
}

out of the while loop, as n will never equal one inside the loop. (And since n will always(?)equal one after the while loop, you can get rid of the first condition entirely.)

Finally, i.equals(2) in

for(i.equals(2) ; i.compareTo(target) == -1 ; i = i.add(one))

doesn't do anything useful - it just returns false for most of the values.

edited Dec 26, 2013 at 4:04

answered Dec 26, 2012 at 5:48

irrelephant

4,1112 gold badges28 silver badges41 bronze badges

Comments

David Mašek · Accepted Answer · 2015-02-14 20:52:10Z

0

As noted by Daniel Fischer your should use long. Be careful not to do something like
long a = 987654321.
Correct version (if you want long): long a = 987654321L.
Simple version:

int maxChain = 0;
    int answer = 0;
    for (int i = 1_000_000; i > 0; i--) {
        int chain = 0;
        long n = i;
        while (n != 1) {
            if ((n & 1) != 1) { //Is even
                n = n / 2;
                chain++;
            } else { //Is odd
                n = 3 * n + 1;
                chain++;
            }
        }
        if (chain > maxChain) {
            maxChain = chain;
            answer = i;
        }
    }
    System.out.println(answer);
    System.out.println(maxChain);

answered Feb 14, 2015 at 20:52

David Mašek

9328 silver badges25 bronze badges

Collectives™ on Stack Overflow

Java: Finding the largest chain in a Collatz sequence

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related