Euler Problem no.30 with Python

This problem statement was quite interesting because that not only judged my coding skills but also my mathematical skills. So i tried to solve it in two different ways –

Problem Statement
Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:
1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution –

I first thought of getting the set of numbers (which meet the problem’s criteria) that are to be added, and then add them together to verify that the set is correct and complete.

Secondly, make a list of constraints which put restriction on the solution set. This problem excludes the value 1 from consideration. In fact, by intuitive extension, it is excluding all single digit values (numbers < 10) as they cannot form a sum of digits. This is a clue that our search range starts from at least 10.Now we have to think on the end range that’s the maximum limit till which our code should search. After just a moment of thought it becomes clear that the number of digits for the sum must have the same number of digits as a value.
Look at the table below to get the maximum limit.

Digits Maximum n Limit = 95 x n Comments
9 999,999,999 531,441 they need to have the same no. of digits
8 99,999,999 472,392 nope, still too many digits of n .
7 9,999,999 413,343 not quite there
6 999,999 354,294 a valid search limit

So we got the maximum limit as 354,294 . Now let’s write the code.

Python Code –

TotalSum = 0    
Value = []                             #values to be added

#Range we got and then comparing the values according to criteria
for i in range(10, 354294): 
    Sum = 0                       #This sum is for getting one single value 
    for x in str(i):
        Sum += int(x) ** 5        #checking for main condition with power 5 
    if Sum == i:                  #If the sum matches with the value 
        Value.append(i)           #The value we are in search for 

# We add those values stored in the list to get total Sum
for i in Value:
    TotalSum += i

print ("Values :" , Value)
print ("TotalSum :" , TotalSum)

Output ->

Values : [4150, 4151, 54748, 92727, 93084, 194979]
TotalSum : 443839

I also tried with other way by defining a function.

Python Code ->

def power_of_digits(n, exp = 5):
    Sum = 0
    while n > 0:
       Sum += (n % 10)**exp
       n //= 10
    return Sum

total = 0
for i in range(10, 10**6):
    if power_of_digits(i) == i:
        total += i
print(total)

Output ->

443839

Happy Coding! 🙂

Advertisements

Euler Problem no. 4 with Python

I Solved the 4th problem from the Euler’s problem set using python and found that it can be done in multiple ways. The problem is related to palindrome concept.

Problem Statement – 
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

I first approached the problem statement by thinking that how many maximum digits will a number have so 2 three digits will have max 6 digits number when multiplied and that can be easily achieved by first multiplying the biggest numbers so I took a reverse loop. And then checked the condition of being a palindrome number and displayed the greatest one after comparison .

Python Code ->

palindrome = 0 
# 2 variables to find the biggest palindrome
for a in range(999, 100, -1):       #First factor

#second factor starts from a so that one multiplication does not repeat.  
    for b in range(a, 100, -1): 
        number = a * b  
        if number > palindrome: 

#To check if number is a palindrome. 
            x = str(a * b)   
            if x == x[::-1]:  
                palindrome = a * b  
print(palindrome) 

Output ->

906609 

Trying More Euler’s Problem and the same code with C++. 🙂