Trusted answers to developer questions

Rukhshan Haroon

**Digit factorial chains** are chains obtained by adding the factorial of each digit of any arbitrary number. This operation is performed iteratively on the resulting numbers.

For example, the digit factorial chain for 86 would be:

To obtain the second element in the chain, 8! was added to 6!. The sum of these two numbers results in 41040. As shown, the second occurrence of 169 marks the beginning of a loop in the chain. Array elements start to repeat in the chain after this point.

Most numbers get stuck in a loop and, usually, we are interested in the non-repeating part of the digit factorial chain.

Find all of the numbers smaller than 100,000 that can be used to create a digit factorial chain of exactly 60 elements.

In the `main`

function, we call a `for`

loop to iterate over all positive integers greater or equal to 0, but smaller than 100,000. Each integer is passed into the `dcf`

function, which maintains the corresponding digit factorial chain for that number.

Before appending any element to the chain, the program checks whether or not it is non-repeating and appends it to the chain if, and only if, it is non-repeating.

If the current length of the chain is 59 and the next number is non-repeating, the `dcf`

function returns `True`

. If a number is found to be repeating, the program returns `False`

. The `dcf`

function calls itself recursively as long as the aforementioned conditions are not met.

You can see this process below:

import math def dcf(chain,curr_num, init_num): fact_num = 0 for i in range(len(str(curr_num))): #loop to compute digit factorials fact_num = fact_num + math.factorial(int(str(curr_num)[i])) if(fact_num not in chain and len(chain) == 59): #check to append to chain chain.append(fact_num) return True else: if(fact_num in chain and len(chain)!= 59): #check to return return False else: chain.append(fact_num) return dcf(chain, fact_num, init_num) #recursive call def main(): count = 0 for i in range(100000): chain = [i] ret = dcf(chain, i, i) #calls dcf for each number in the range 0<=x<1000000 if ret == True: count += 1 print(i) print("These are ", count, " numbers in total!") main()

RELATED TAGS

python

CONTRIBUTOR

Rukhshan Haroon

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses