p45.cpp

/**
 * 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.
 *
 * SOLUTION:
 *
 * It is easy to verify that T(2n-1) = H(n). So we only need to find an
 * intersect of P(n) and H(n').
 *
 * Now let H(n') = y. Solving the equation P(n) = y yields
 *
 *   n = (1 + sqrt(1 + 24 * y)) / 6
 *
 * where n needs to be an integer.
 *
 * ANSWER: 1533776805
 */

#include <iostream>
#include "euler/imath.hpp"
#include "euler.h"

BEGIN_PROBLEM(45, solve_problem_45)
    PROBLEM_TITLE("Triangular, pentagonal, and hexagonal")
    PROBLEM_ANSWER("1533776805")
    PROBLEM_DIFFICULTY(1)
    PROBLEM_FUN_LEVEL(1)
    PROBLEM_TIME_COMPLEXITY("?")
    PROBLEM_SPACE_COMPLEXITY("?")
END_PROBLEM()

static void solve_problem_45()
{
  for (int64_t n = 1; n <= 0xffffffffLL; n++)
  {
    int64_t y = n*(n+n-1);
    int64_t d = euler::isqrt(1+24*y);
    if (d*d == 1+24*y)
    {
      int64_t m = (1+d)/6;
      if (m*6 == 1+d)
      {
        if (y <= 40755)
        {
          // std::cout << "Found " << y << std::endl;
        }
        else
        {
          std::cout << y << std::endl;
          break;
        }
      }
    }
  }
}