Project Euler 577 - Counting Hexagons

Official link: https://projecteuler.net/problem=577

Thought Process

Essentially the key to this problem is realising why H(6) = 12. If you can figure this out the problem becomes simple

It is quite easy to see that H(6) = 11 with 10 hexagons of side length 1 and 1 hexagon of side length 2, but there is 1 more which has side length sqrt(3) (See the orange dotted line)

One you realise this you can quickly realise that every time n is divisible by 3, you will introduce new possible hexagons (See the slanted blue dotted lines for example)

Therefore when we have H(3n) we introduce n new hexagons, the number of hexagons that can fit inside the triangle following the Triangular Numbers

For example H(20) = T(18) + 2*T(15) + 3*T(12) + 4*T(9) + 5*T(6) + 6*T(3)

Another method is to generate the first few numbers and find the corresponding OEIS sequence

Interactive Code

Input an integer (yourinput)

Code will output sum{n = 2 to yourinput} H(n)

Page updated

Google Sites

Report abuse