Project Euler Problem 45 Statement
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
| Type | Formula | Sequence |
|---|---|---|
| Triangle | \(T_n = \frac{n(n+1)}{2}\) | 1, 3, 6, 10, 15, … |
| Pentagonal | \(P_n = \frac{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
OK, hold on, this is going to get bumpy. I want to show you how I derived the first two lambda functions to determine if a number is a triangle number or a pentagon number. You can skip this if you don't care and just trust me.
1. Triangular Numbers
The formula for the $n$-th triangular number is: $$T_n = \frac{n(n+1)}{2}$$Solve for $n$ in terms of $T_n$:
Multiply through by 2 to eliminate the fraction:
$$2T_n = n^2 + n$$Rearrange into standard quadratic form:
$$n^2 + n - 2T_n = 0$$This is a quadratic equation in $n$. Solve using the quadratic formula:
$$n = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$Here, $a=1$, $b=1$, and $c=-2T_n$. Substituting:
$$n = \frac{-1 \pm \sqrt{1^2 - 4(1)(-2T_n)}}{2(1)}$$ Simplify the discriminant: $$n = \frac{-1 \pm \sqrt{1 + 8T_n}}{2}$$For $n$ to be a valid integer, the discriminant $\sqrt{1 + 8T_n}$ must be an integer.
Therefore:
Hence, the condition for $x$ to be triangular is:
$$\sqrt{8x + 1} \mod 1 = 0$$2. Pentagonal Numbers
The formula for the $n$-th pentagonal number is: $$P_n = \frac{n(3n-1)}{2}$$Solve for $n$ in terms of $P_n$:
Multiply through by 2 to eliminate the fraction:
$$2P_n = n(3n - 1)$$Expand and rearrange into standard quadratic form:
$$3n^2 - n - 2P_n = 0$$This is a quadratic equation in $n$. Solve using the quadratic formula:
$$n = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$Here, $a=3$, $b=-1$, and $c=-2P_n$. Substituting:
$$n = \frac{-(-1) \pm \sqrt{(-1)^2 - 4(3)(-2P_n)}}{2(3)}$$Simplify the discriminant:
$$n = \frac{1 \pm \sqrt{1 + 24P_n}}{6}$$For $n$ to be a valid integer, the discriminant $\sqrt{1 + 24P_n}$ must be and integer, and $1 + \sqrt{1 + 24P_n}$ must be divisible by 6. Therefore: $$\sqrt{24x + 1} \mod 1 = 0 \quad \text{and} \quad (\sqrt{24x + 1} + 1) \mod 6 = 0$$
The rest is simple
All hexagonal numbers are also triangular (which is why we don't need to check for triangular numbers in the second branch)
When a equals 3, the code generates pentagonal numbers using the formula n(3n-1)/2, and then checks if each pentagonal number is also triangular. The range limit t//6 is derived by solving the pentagonal formula for N.
For any other value of a, the code instead generates hexagonal numbers using the formula n(2n-1) and verifies if each hexagonal number is also pentagonal. In this case, the range limit t//4 is obtained by solving the hexagonal formula for N.
HackerRank version
HackerRank Project Euler 45 wants us to find eith Triangular—Pentagonal or Pentagonal—Hexagonal pairs under 2 ≤ N &lw; 2×1014.
Python Source Code
import math
is_triangular = lambda x: math.sqrt(8*x+1) % 1 == 0
is_pentagonal = lambda x: (math.sqrt(24*x+1)+1) % 6 == 0
N, a, _ = map(int, input().split())
t = math.isqrt(24*N+1)
if a==3:
for i in range(1, t//6):
num = i * (3*i-1) // 2
if is_triangular(num): print(num)
else:
for i in range(1, t//4):
num = i*(2*i-1)
if is_pentagonal(num): print(num) Last Word
We can also solve this mathematically by asserting that if $P_n = H_m$ then: $$\frac{1}{2} n(3n-1)=m(2m-1)$$
As documented in the article by Wolfram on Hexagonal Pentagonal Numbers we can reduce this equation as:
$$(6n-1)^2-3(4m-1)^2=-2$$This is a diophantine equation that expands as such:
$$36n^2-48m^2-12n+24m$$which we fed into our favorite Diophantine equation solver and produce the results:
P0 = 0 H0 = 0 Pn+1 = 97·Pn + 112·Hn - 44 Hn+1 = 84·Pn + 97·Hn - 38
Replace P0 and H0 with our starting index and this problem is solved instantly. Note that the starting values for p and h were defined in the problem.
A relevant sequence is documented as OEIS A046179 Hexagonal pentagonal numbers. A Python program is listed in the comments section to generate this sequence.