Project euler 45

Question

I'm not yet a skilled programmer but I thought this was an interesting problem and I thought I'd give it a go.

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

• Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, ...
• Pentagonal P_(n)=n(3n−1)/2 1, 5, 12, 22, 35, ...
• Hexagonal H_(n)=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Is the task description.

I know that Hexagonal numbers are a subset of triangle numbers which means that you only have to find a number where Hn=Pn. But I can't seem to get my code to work. I only know java language which is why I'm having trouble finding a solution on the net womewhere. Anyway hope someone can help. Here's my code

public class NextNumber {

    public NextNumber() {
    next();
    }

    public void next() {


int n = 144;
int i = 165;
int p = i * (3 * i - 1) / 2;
int h = n * (2 * n - 1);
        while(p!=h) {
            n++;
           h = n * (2 * n - 1);

            if (h == p) {
                System.out.println("the next triangular number is" + h);
            } else {
                while (h > p) {
                    i++;
                    p = i * (3 * i - 1) / 2;
                }
                if (h == p) {
                    System.out.println("the next triangular number is" + h); break;
                    }
                 else if (p > h) {
                    System.out.println("bummer");
                }
            }

            }

    }
}

I realize it's probably a very slow and ineffecient code but that doesn't concern me much at this point I only care about finding the next number even if it would take my computer years.

Answer 1

We know that T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755. We start with nt=286, np=166 and nh=144 and work out the respective triangle, pentagonal, and hexagonal numbers. Whichever resulting number is smallest, we bump up its n value. Continue doing this until all numbers are equal and you have your answer.

A Python implementation of this algorithm runs in 0.1 seconds on my computer.

The problem with your code is overflow. While the answer fits into a 32 bit int, the temporary values i * (3 * i - 1) overflows before reaching the answer. Using 64 bit long values fixes your code.