Back to index.

The problem: https://projecteuler.net/problem=45

By solving quadratic equations, again, we can find which is the index number for a Triangle/Hexagonal/Pentagonal number.

For triangle numbers, if $T_n = A$, then $n = \frac {-1 + \sqrt{1 + 8A}} 2$. For pentagonal numbers, if $P_n = A$, then $n = \frac {1 + \sqrt{1 + 24A}} 6$. For hexagonal numbers, if $H_n = A$, then $n = \frac {1 + \sqrt{1 + 8a}} 4$.

So, our idea will be the following. We'll start looking through the pentagonal numbers until we find one which is also a triangle number and a hexagonal number. We should first find 40755 (for the 165th pentagonal number) because we'll be going through the pentagonal numbers in increasing order. The next pentagonal number which is also a triangle and hexagonal number is the answer (again, this is because of monotonicity).

def P(n):
    return n*(3*n-1)//2

def integer_sqrt(n):
    if n < 0:
        return -1
    if n == 1 or n == 0:
        return n
    lo = 1
    hi = n
    while lo <= hi:
        mid = (hi+lo)//2
        square = mid*mid
        if square == n:
            return mid
        elif square > n:
            hi = mid-1
        else:
            lo = mid+1
    return -1

def find_hexagonal_index(A):
    d = 1 + 8*A
    four_n_minus_1 = integer_sqrt(d)
    if four_n_minus_1 % 4 != 3:
        return 0
    n = (four_n_minus_1 + 1)//4
    return n

def find_triangle_index(A):
    d = 1 + 8*A
    two_n_plus_1 = integer_sqrt(d)
    if two_n_plus_1 % 2 != 1:
        return 0
    n = (two_n_plus_1 - 1)//2
    return n

n_pent = 165+1
found = False
next_one = 0

while not found:
    p = P(n_pent)
    t_n = find_triangle_index(p)
    if t_n <= 0:
        n_pent += 1
        continue
    h_n = find_hexagonal_index(p)
    if h_n <= 0:
        n_pent += 1
        continue
    found = True
    next_one = p

print(next_one)

1533776805