Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python

What are digit factorial chains?

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:

%0 node_1624878443460 86 node_1624878393621 41040 node_1624878467267 51 node_1624878464139 121 node_1624878462071 4 node_1624878439055 24 node_1624878429767 26 node_1624878456296 722 node_1624878446114 5044 node_1624878496851 169 node_1624878513665 363601 node_1624878512328 1454 node_1624878461367 169

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

python

CONTRIBUTOR

Rukhshan Haroon
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring