Python,C,C++ and JAVA programs for CBSE, ISC, B.Tech and I.T Computer Science and MCA students

The Programming Project: Digit factorial chains : Problem 74 : Project Euler Python Code

Friday, October 17, 2014

Digit factorial chains : Problem 74 : Project Euler Python Code

Digit factorial chains : Problem 74 : Project Euler Python Code

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers 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 difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

Python Code 

 

def digitFactorialChains():
    def fact(digit):
        l=1
        for i in range(digit):
            l=l*digit
            digit=digit-1
        return l
    number = 1
    digitfactsum = 0
    counter = 0
    while number < 10**6:
            chain = ()
            chain = chain + (number,)
        strnumber = str(number) 
        length = 1
            while True:
                digitfactsum = 0
            for i in range(len(strnumber)):
                    digitfactsum = digitfactsum + fact(int(strnumber[i]))
                if digitfactsum in chain:
                    break
                else:
                    chain = chain + (digitfactsum,)  
                    length = length + 1
                    strnumber = str(digitfactsum)
        """print chain,length  prints the sequnce with length"""         
        if length == 60:
                 counter = counter + 1  
             """You wont get bored if you print the loop iteration!"""  
             print number       
             number = number + 1
    print "chains, with a starting number below one million, contain exactly sixty non-repeating terms:",counter
digitFactorialChains() 

 


No comments:

Post a Comment