Project Euler # 74 Digit factorial chains in Python

Question

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

Here's my implementation in Python.

from math import factorial
from time import time


def get_factorial_sequence_length(number, factorials, lengths):
    """Return length of factorial sequence of number."""
    if number in lengths:
        return lengths[number]
    chain = [number]
    while len(chain) == len(set(chain)):
        if chain[-1] in lengths:
            index = chain.index(chain[-1])
            return lengths[chain[-1]] + len(chain[:index])
        chain_next = sum(factorials[digit] for digit in str(chain[-1]))
        chain.append(chain_next)
    duplicate_index = chain.index(chain[-1])
    for num in chain:
        index = chain.index(num)
        if index <= duplicate_index:
            lengths[num] = len(chain[index:-1])
        if index > duplicate_index:
            lengths[num] = len(chain[duplicate_index:index]) + len(chain[index:-1])
    return lengths[number]


def get_sequence_counts(upper_bound, target_chain_size, lengths={}):
    """Return count of factorial sequences which have length target_chain_size within range upper_bound exclusive."""
    factorials = {str(n): factorial(n) for n in range(10)}
    for number in range(1, upper_bound):
        chain_length = get_factorial_sequence_length(number, factorials, lengths)
        lengths[number] = chain_length
        if chain_length == target_chain_size:
            yield number


if __name__ == '__main__':
    start_time = time()
    print(len(set(get_sequence_counts(1000000, 60))))
    print(f'Time: {time() - start_time} seconds.')

Answer 1

Dictionaries -vs- Lists

A dictionary is a very complex structure, designed to provide close to \$O(1)\$ access to its members. To do this, each element is stored in a location based on the hash of a key. The modulo remainder of the hash and the binning size of the dictionary is computed to determine the "bin" the value is stored in. Since more than 1 value can hash to the same value, modulo the dictionary binning size, the bin is then scanned to find the key which matches the input key, and that value is returned.

In contrast, to look up an entry from a list from a given position is simply retrieving the value from that position in the list. No hashing. No modulo arithmetic. No searching. Not only is the time complexity \$O(1)\$, the constant factor is also very small.

As entries are added to a dictionary, the size of the dictionary grows. Eventually, adding an entry to the dictionary will cause a "load_factor" to be exceeded, and the number of bins will increase (probably double), and all of the keys will need to be rehashed, and the elements distributed into new bins. While this rebinning is fairly fast, it still takes time. If you add 1 million entries to a dictionary, you could expect it will rebin about \$\log _2 1000000\$ times.

If you allocated an list of 1000000 entries, the allocation is done once up front, and you could look up the value of each of those entries in \$O(1)\$ time. In addition, a list of 1000000 sequential numeric entries will take half the memory as the same information store in a dictionary, since no storage is required for the keys.

Based on this, it seems that you could replace the lengths dictionary with a list of 1 million zeros. If lengths[x] == 0, then the length of the chain starting from x hasn't been computed yet. If lengths[x] > 0, then it has been.

lengths = [0]*1000000

Except the chain starting at 999999 immediately exceeds 1 million; 9! = 362880, so six 9 digits produces a 7 digit sum: 2177280, which is beyond the length of our list. Fortunately the largest next term that can be produced by a 7 digit term less than 2177280 would be produced by 1999999, which would result in 2177281, and that puts a limit on the length of the list that would be required: 2177282. Since the list requires approximately half the space as a dictionary, this works out to approximately the same memory requirement. And yet would be significantly faster.

Dramatically reducing memory

Based on "the longest non-repeating chain with a starting number below one million is sixty terms", we know we will only every need to store the values 0 through 60. These values are all within 0 to 255, so can be stored in a byte, which means we can use a bytearray, instead of a list.

lengths = bytearray(2_177_282)

chain[-1]

Using chain[-1] to get the last value in the chain is awkward, and uses up time unnecessarily. In the majority of the cases, chain_next is that last value, since you chain.append(chain_next) at the end of your loop. The exception is the first time you enter the loop, you haven't computed chain_next, and chain[-1] is actually just number. Simply set chain_next = number before entering the loop, and you don't need chain[-1]:

chain_next = number
chain = [chain_next]
while len(chain) == len(set(chain)):
    if chain_next in lengths:
        index = chain.index(chain_next)
        return lengths[chain_next] + len(chain[:index])
    chain_next = sum(factorials[digit] for digit in str(chain_next))
    chain.append(chain_next)

What is chain.index(chain[-1])? Or chain.index(chain_next) in the new code? The index of the last entry in the list, assuming it is unique, which it must be due to the loop condition, so it will be len(chain) - 1. And len(chain[:index]) is index by definition! So:

chain_next = number
chain = [chain_next]
while len(chain) == len(set(chain)):
    if chain_next in lengths:
        return lengths[chain_next] + len(chain) - 1
    chain_next = sum(factorials[digit] for digit in str(chain_next))
    chain.append(chain_next)

As @ruds point out, len(chain) == len(set(chain)) is converting the list to a set at each iteration. See their approach for maintaining both a seen and chain to avoid that inefficiency.

Answer 2

A few comments.

First, your algorithm for computing the length of a chain is quadratic, because you convert your list to a set at each iteration. Second, there's a lot going on in get_factorial_sequence_length. I'd break the function up. You essentially have three parts: 1. Generate the elements of the sequence; 2: determine when to stop generating the sequence; 3. Determine the length of the non-repeating section (and memoize the length for all the seen numbers). The first part should be its own generator.

def generate_sequence(factorials, num):
    while True:
        yield num
        num = sum(factorials[digit] for digit in str(num)

Now get_factorial_sequence_length can look like:

def get_factorial_sequence_length(number, factorials, lengths):
    chain = []
    seen = set()
    for num in generate_sequence(factorials, number):
        if num in lengths:
            memoize_lengths_found(chain, num, lengths)
            return lengths[num] + len(chain)
        if num in seen:
            memoize_lengths_new(chain, num, lengths)
            return lengths[num]
        chain.append(num)
        seen.add(num)

memoize_lengths_found and memoize_lengths_new could use some work on the names, and I leave the implementations as an exercise to the reader.