# Project Euler Problem 45: Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle

$$T_n = \frac{n(n+1)}{2} \\ 1, 3, 6, 10, 15, \dotsc$$

Pentagonal

$$P_n = \frac{n(3n−1)}{2} \\ 1, 5, 12, 22, 35, \dotsc$$

Hexagonal

$$H_n = n(2n−1) \\ 1, 6, 15, 28, 45, \dotsc$$

It can be verified that $T_{285} = P_{165} = H_{143} = 40755$.

Find the next triangle number that is also pentagonal and hexagonal.

#### Version 1: Brute force¶

In [1]:
from six.moves import map, range
from itertools import islice

In [2]:
def argmin(iterable):
argmin_ = 0
for i, n in enumerate(iterable):
if n < iterable[argmin_]:
argmin_ = i
return argmin_

In [3]:
from random import randint

In [4]:
a = [randint(1, 100) for _ in range(15)]; a

Out[4]:
[78, 25, 88, 84, 50, 62, 83, 30, 80, 90, 38, 52, 26, 43, 82]
In [5]:
argmin(a)

Out[5]:
1
In [6]:
def polygonal(s):
c = s - 2
a = b = 1
while True:
yield a
b += c
a += b

In [7]:
list(islice(polygonal(2), 10))

Out[7]:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In [8]:
list(islice(polygonal(3), 10))

Out[8]:
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
In [9]:
list(islice(polygonal(4), 10))

Out[9]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
In [10]:
s = [3, 5, 6]

In [11]:
polygonal_iters = list(map(polygonal, s))

In [12]:
list(islice(polygonal(7), 10))

Out[12]:
[1, 7, 18, 34, 55, 81, 112, 148, 189, 235]
In [13]:
polygonal_iters = list(map(polygonal, s))

In [14]:
values = list(map(next, polygonal_iters))

In [15]:
next(polygonal_iters[argmin(values)])

Out[15]:
3
In [16]:
all_equals = lambda lst: lst[1:] == lst[:-1]

In [17]:
def polygonal_combinations(s_lst):
iters = list(map(polygonal, s_lst))
values = list(map(next, iters))
while True:
if all_equals(values):
yield values[0]
amin = argmin(values)
values[amin] = next(iters[amin])

In [18]:
list(islice(polygonal_combinations([3, 5, 6]), 4))

Out[18]:
[1, 40755, 1533776805, 57722156241751]
In [19]:
it = polygonal_combinations([3, 4, 6, 29, 60, 124])

In [20]:
next(it)

Out[20]:
1
In [21]:
next(it)

Out[21]:
1225

The number 1225 is hecticositetragonal ($s=124$), hexacontagonal ($s=60$), icosienneagonal ($s=29$), hexagonal, square, and triangular.

In [22]:
from operator import itemgetter

In [23]:
def polygonal_combinations(s_lst):
values = [1 for _ in s_lst]
increm = [1 for _ in s_lst]
while True:
if all_equals(values):
yield values[0]
amin = argmin(values)
increm[amin] += s_lst[amin] - 2
values[amin] += increm[amin]

In [24]:
it = polygonal_combinations([3, 5, 6])

In [25]:
next(it)

Out[25]:
1
In [26]:
next(it)

Out[26]:
40755
In [27]:
next(it)

Out[27]:
1533776805