What are digit factorial chains?
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.
Problem
Find all of the numbers smaller than 100,000 that can be used to create a digit factorial chain of exactly 60 elements.
Solution
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
CONTRIBUTOR
View all Courses
