Problem Description

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?

Analysis

Knowing of a clever solution and debating the use of making one weighed in favor of utilizing some of the code from problem 34. We wrote a recursive solution that was slow but intuitive (As the the saying goes, ‘In order to understand recursion, one must first understand recursion’).

By placing the factorials in an array saved having to recalculate them as we only needed the first 10. Also, starting from 70 was a parameter inferred from the problem description.

We did want a solution that was somewhat extensible and able to answer other questions if the need ever arose. Making changes to bounds or to the size of the series would be easy to change.

Solution

Runs < 55 seconds in Perl.

my %sum;
my @fact = (1, 1, 2, 6, 24, 120, 720, 5_040, 40_320, 362_880);
for (my $i=70; $i<999999; $i++) {
  %h=();
  $x60++ if chains($i)==60; 
}
print "Answer to PE74 = $x60";
 
sub chains {
  $n = shift;
  return scalar keys %h if $h{$n};
  $h{$n}++;
  unless ( $sum{$n} ) { $sum{$n} += $fact[$_] for split //,$n }
return chains($sum{$n});
}

Comments