Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.
Plan of attack:
- Starting from 286, generate a sequence of triangle numbers
- Test each one for pentagonality
- Test each one for hexagonality
- When we find one that is both pentagonal and hexagonal, we have our answer.
Let's start with the easy stuff:
let firstT = 285L + 1L let firstP = 165L + 1L let firstH = 143L + 1L
Based on the problem definition, we know that the first time T, P, and H line up is
n = 285, 165, and 143, respectively. So when we start generating sequences,
we're going to start at one past those.
let t n = n * (n + 1L) / 2L let p n = n * (3L * n - 1L) /2L let h n = n * (2L * n - 1L)
The above trio of functions generate the nth triangle, pentagonal, and hexagonal number.
Now, we need a quick way to test for pentagonal and hexagonal numbers. So we'll make maps containing 100000 of each class of numbers. 100000 is a number I just made up on the spot because it "seemed reasonable". We can adjust later if need be.
let makeMap f first = let nums = Seq.unfold (fun state -> Some(f state, state + 1L)) first |> Seq.mapi (fun i x -> (x,i+1)) |> Seq.take 100000 |> List.ofSeq let max = fst (nums |> List.last) let map = Map.ofList nums (max,map) let pentagonalMax,pentagonalMap = makeMap p firstP let hexagonalMax,hexagonalMap = makeMap h firstH let maxToCheck = min pentagonalMax hexagonalMax let isPentagonal n = Map.containsKey n pentagonalMap let isHexagonal n = Map.containsKey n hexagonalMap
makeMap function takes a starting value and a sequence unfolding function. It
generates the sequence and converts it into a map. It returns both the maximum value
in the map and the map itself.
makeMap we generate pentagonal and hexagonal maps and their maximums.
maxToCheck gets bound to the minimum of
We'll stop generating triangle numbers when they get above this value.
Finally, we have a pair of functions,
isHexagonal that can
check for pentagonality and hexagonality, respectively.
Now we need a bunch of triangle numbers to start testing:
let generateTriangle state = let number = t state if (number > maxToCheck) then None else Some(number, state + 1L) let triangleNumbers = Seq.unfold generateTriangle firstT
Seq.unfold to generate triangle numbers using the generator function
generateTriangle. It stops generating when the number generated exceeds
Now we can solve the problem:
triangleNumbers |> Seq.filter (fun n -> isPentagonal n && isHexagonal n) |> Seq.head
We simply take our sequence of triangle numbers, filter out any that aren't both pentagonal and hexagonal, and return the head of that sequence. That is the answer.Other Posts in This Series