Project Euler Solution 61: Cyclical figurate numbers

Martin Ueding

2023-08-05

Code & Zahlen

Project Euler Problem 61: Cyclical figurate numbers brings us back to triangular and pentagonal numbers.

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Kind Definition Examples

Triangle $P_{3,n}=n(n+1)/2$ 1, 3, 6, 10, 15, ...

Square $P_{4,n}=n^2$ 1, 4, 9, 16, 25, ...

Pentagonal $P_{5,n}=n(3n−1)/2$ 1, 5, 12, 22, 35, ...

Hexagonal $P_{6,n}=n(2n−1)$ 1, 6, 15, 28, 45, ...

Heptagonal $P_{7,n}=n(5n−3)/2$ 1, 7, 18, 34, 55, ...

Octagonal $P_{8,n}=n(3n−2)$ 1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).

Each polygonal type: triangle ($P_{3,127}=8128$), square ($P_{4,91}=8281$), and pentagonal ($P_{5,44}=2882$), is represented by a different number in the set.

This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Kind	Definition	Examples
Triangle	$P_{3,n}=n(n+1)/2$	1, 3, 6, 10, 15, ...
Square	$P_{4,n}=n^2$	1, 4, 9, 16, 25, ...
Pentagonal	$P_{5,n}=n(3n−1)/2$	1, 5, 12, 22, 35, ...
Hexagonal	$P_{6,n}=n(2n−1)$	1, 6, 15, 28, 45, ...
Heptagonal	$P_{7,n}=n(5n−3)/2$	1, 7, 18, 34, 55, ...
Octagonal	$P_{8,n}=n(3n−2)$	1, 8, 21, 40, 65, ...

The count of four digit numbers in the six different classes are the following: [97, 69, 57, 49, 44, 40]. We can already see that that there are 32,323,441,920 combinations for all these numbers, which is not an impossible large number. And we have 5! = 120 ways to arrange the order. A few combinations will not be valid because the same number is used multiple times. So in total there would be 3,878,813,030,400 combinations to check. That number feels pretty large. With a 4.2 GHz CPU I can only do 4,200,000,000 computations per second. Given the 1 minute limit, this would limit me to 252,000,000,000 computations. One can see that this number is too large.

If one takes a look at the numbers and divides them into a two-digit prefix and two-digit suffix, one finds that each prefix usually only has one, perhaps two suffixes. This means that the number of continuations for a given previous number are actually very limited. We can use that to try all combinations in a much more clever way.

First we start by implementing the various number types.

def iter_triangular() -> Iterator[int]:
    for n in itertools.count(1):
        yield n * (n + 1) // 2


def iter_square() -> Iterator[int]:
    for n in itertools.count(1):
        yield n**2


def iter_pentagonal() -> Iterator[int]:
    for n in itertools.count(1):
        yield n * (3 * n - 1) // 2


def iter_hexagonal() -> Iterator[int]:
    for n in itertools.count(1):
        yield n * (2 * n - 1)


def iter_heptagonal() -> Iterator[int]:
    for n in itertools.count(1):
        yield n * (5 * n - 3) // 2


def iter_octogonal() -> Iterator[int]:
    for n in itertools.count(1):
        yield n * (3 * n - 2)

Next we write a function that extracts all the four digit numbers.

def generate_numbers(iterator: Iterator[int]) -> list[int]:
    result = []
    for number in iterator:
        if number >= 1000:
            result.append(number)
        if number >= 10000:
            break
    return result

And then we write a function that splits numbers into prefixes and suffixes and stores them in a dict[str, list[str]] for easy look-up of the suffixes for a given prefix.

def split_numbers(numbers: list[int]) -> dict[str, list[str]]:
    result = collections.defaultdict(list)
    for number in numbers:
        s = str(number)
        prefix = s[:2]
        suffix = s[2:]
        result[prefix].append(suffix)
    return result

We can then define a recursive function that takes a given prefix of numbers (as strings) and a list of remaining splits to continue.

def recursion(
    set_so_far: list[str], splits: list[dict[str, list[str]]]
) -> Optional[list[str]]:
    prefix = set_so_far[-1][2:]
    if splits:
        for candidate in splits[0].get(prefix, []):
            set_so_far.append(prefix + candidate)
            result = recursion(set_so_far, splits[1:])
            if result:
                return result
            set_so_far.pop()
    else:
        if prefix == set_so_far[0][:2]:
            return set_so_far

The solution is then formed by generating all the numbers and splitting them. Then we take all permutations of the splits such that we get all possible orderings. Taking prefixes from the triangular numbers, we continue it with the other ones.

def solution() -> int:
    all_numbers = [
        generate_numbers(iterator)
        for iterator in [
            iter_triangular(),
            iter_square(),
            iter_pentagonal(),
            iter_hexagonal(),
            iter_heptagonal(),
            iter_octogonal(),
        ]
    ]

    splits = [split_numbers(numbers) for numbers in all_numbers]
    for ss in itertools.permutations(splits[1:]):
        for prefix, suffixes in splits[0].items():
            for suffix in suffixes:
                if result := recursion([prefix + suffix], ss):
                    return sum(map(int, result))

This gives the correct solution in just 2.0 ms. We can make it a bit faster and finish in 1.6 ms if we start with the octagonal numbers. Perhaps this is just a coincidence as we find the solution earlier in the permutations that are tried. It likely doesn't mean too much.