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.
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
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()
View all Courses