3

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);        
}
1
  • 3
    Just FYI, you don't need BigIntegers, long is enough. Dec 26, 2012 at 5:57

3 Answers 3

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.

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.

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);

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.