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

Comments

Comments powered by Disqus