Project Euler — Problem 74 Solution

Problem

The num­ber 145 is well known for the prop­er­ty that the sum of the fac­to­r­i­al of its dig­its is equal to 145:

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

Per­haps less well known is 169, in that it pro­duces the longest chain of num­bers 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 dif­fi­cult to prove that EVERY start­ing num­ber will even­tu­al­ly get stuck in a loop. For exam­ple,

69 ? 363600 ? 1454 ? 169 ? 363601 (? 1454)

78 ? 45360 ? 871 ? 45361 (? 871)

540 ? 145 (? 145)

Start­ing with 69 pro­duces a chain of five non-repeat­ing terms, but the longest non-repeat­ing chain with a start­ing num­ber below one mil­lion is six­ty terms.

How many chains, with a start­ing num­ber below one mil­lion, con­tain exact­ly six­ty non-repeat­ing terms?

Solution

The solu­tion I have here caches the pre­vi­ous results to avoid dupli­cat­ed work, this com­pli­cates the code slight­ly but it should still be fair­ly easy to fol­low. The key thing here is the recur­sive func­tion process­Chain­Rec which recur­sive­ly gen­er­ate the next num­ber in the chain until it hits one of two con­di­tions:

  1. you hit a num­ber already in the chain (hence the end of the non-repeat­ing chain)
  2. you hit a num­ber whose non-repeat­ing chain length has been cached

In the first case, sup­pose you have [69, 363600, 1454, 169, 363601] in the list already, and then the next num­ber is 1454, which is in the list with index 2. At this point, you can work out the non-repeat­ing chain length for 69, 363600 and 1454:

69 : list.length – index = 5 – 0 = 5

363600 : list.length – index = 5 – 1 = 4

1454 : list.length – index = 5 – 2 = 3

Hit three eggs with one stone? Awe­some Smile

For the sec­ond case, sup­pose you had already come across 1454 before and have already cal­cu­lat­ed its non-repeat­ing chain length, now you have [69, 363600] in the list and 1454 pop outs of the hat. So a quick look up in the cached data tells you that 1454 has a non-repeat­ing chain of 3 terms, so to apply that knowl­edge to 69 and 363600:

69 : list.length – index + 3 = 2 – 0 + 3 = 5

363600 : list.length – index + 3 = 2 – 1 + 3 = 4

Voila!