Python Implementation of Problem 74

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 74

This ended up being a filtering problem. The problem with my solution is that I am not satisfied with my filter at all. I feel like there is a more efficient way to go about it.

Problem:

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?

python.src.p0074.main() → int
 1"""
 2Project Euler Problem 74
 3
 4This ended up being a filtering problem. The problem with my solution is that I
 5am not satisfied with my filter at all. I feel like there is a more efficient
 6way to go about it.
 7
 8Problem:
 9
10The number 145 is well known for the property that the sum of the factorial of
11its digits is equal to 145:
12
131! + 4! + 5! = 1 + 24 + 120 = 145
14
15Perhaps less well known is 169, in that it produces the longest chain of
16numbers that link back to 169; it turns out that there are only three such
17loops that exist:
18
19169 → 363601 → 1454 → 169
20871 → 45361 → 871
21872 → 45362 → 872
22
23It is not difficult to prove that EVERY starting number will eventually get
24stuck in a loop. For example,
25
2669 → 363600 → 1454 → 169 → 363601 (→ 1454)
2778 → 45360 → 871 → 45361 (→ 871)
28540 → 145 (→ 145)
29
30Starting with 69 produces a chain of five non-repeating terms, but the longest
31non-repeating chain with a starting number below one million is sixty terms.
32
33How many chains, with a starting number below one million, contain exactly
34sixty non-repeating terms?
35"""
36from math import factorial
37from typing import Set
38
39from .lib.iters import digits
40
41
42def main() -> int:
43    cache = [factorial(x) for x in range(10)]
44    paths = {
45        69: 363600,
46        78: 45360,
47        145: 145,
48        169: 363601,
49        540: 145,
50        871: 45361,
51        872: 45362,
52        1454: 169,
53        45360: 871,
54        45361: 871,
55        45362: 872,
56        363601: 1454,
57        163600: 1454
58    }
59    answer = 0
60    seen: Set[int] = set()
61    for x in range(3, 1000000):
62        while x not in seen:
63            seen.add(x)
64            if x in paths:
65                x = paths[x]
66            else:
67                paths[x] = x = sum(cache[y] for y in digits(x))
68        if len(seen) == 60:
69            answer += 1
70        seen.clear()
71    return answer

Tags: factorial, digit-sum, sequence-generator, periodicity, python-iterator