Project Euler

Problem 45: Triangular, Pentagonal, and Hexagonal

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₂₈₅ = P₁₆₅ = H₁₄₃ = 40755. Find the next triangle number that is also pentagonal and hexagonal.

The Catch

How to determine if a number is triangular, pentagonal, or hexagonal.

The Light

Notice that for odd values of n, note that if a number is hexagonal, then it is also triangular.

Proof: T(2n - 1) = (2n - 1)( (2n - 1) + 1 )/2 = n(2n - 1).

Thus, start generating a sequence of triangular numbers starting with n = 145 and only use odd values for n. Stop generating when the first instance of a pentagonal number appears.

Similar to the discussion in Problem 42, to check if a number is pentagonal, the inverse of P(n) = n(3n - 1)/2, (1 + sqrt(1 + 24x))/6 must produce an integer.

Use type long to hold numbers, since they can get fairly large.

The Code

public class Problem45
{
  public static void main(String[] args)
  {
    int n = 145;

    while(true)
    {
      long num = n * (2 * n - 1);
      if(isPen(num))
      {
        System.out.println(num);
        break;
      }
      n += 2;
    }
  }

  public static boolean isPen(long n)
  {
    double d = (1.0 + Math.sqrt(1 + 24 * n))/6.0;
    return (d == (long)d);
  }
}