Project Euler/45
From charlesreid1
Problem Statement
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
| Shape | Formula | First Terms |
|---|---|---|
| Triangle | $ T_n = \frac{1}{2} n (n + 1) $ | 1, 3, 6, 10, 15, ... |
| Pentagonal | $ P_n = \frac{1}{2} n (3n - 1) $ | 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.
Approach
Key Insight: Hexagonal Numbers are Triangle Numbers
Every hexagonal number is also a triangle number. Algebraically:
$ H_n = n(2n - 1) = \frac{(2n-1)(2n)}{2} = T_{2n-1} $
This means the problem reduces to finding the next hexagonal number (after H143 = 40755) that is also pentagonal. We only need to generate hexagonal numbers and test them for pentagonality.
Testing for Pentagonal Numbers
Given an integer x, we can test whether it is pentagonal by solving the quadratic derived from the pentagonal formula:
$ P_n = \frac{n(3n - 1)}{2} \implies 3n^2 - n - 2x = 0 $
The discriminant is $ 1 + 24x $. If x is pentagonal, then:
- $ s = \sqrt{1 + 24x} $ must be an integer (a perfect square), and
- $ (s + 1) \bmod 6 = 0 $ (ensuring the root n is an integer).
Both conditions are checked in one pass for each candidate.
Iteration Strategy
- Start with $ n = 144 $ (the next hexagonal index after 143, the known match).
- Compute the hexagonal number $ H_n = n(2n - 1) $.
- Test whether $ H_n $ is pentagonal using the two conditions above.
- If it is pentagonal, this is the answer. Otherwise, increment n and repeat.
Because every hexagonal number is already triangle, no separate triangle check is needed.
Solution
Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem045.java
Flags
