The euler project is a website that contains interesting problem that can be solved with mathmatical computation. In this post I will go through several examples and my deatailed answers.
Largest Palindrome Product
A palindrome number reads the same both ways. For example: 1001, 2002, 3443, 4444. And the largest palinrome can be made from the product of two 2-digit number is 9009 = 91*99. The question is to find the largest palindrome made from the product of two 3-digit numbers.
The first step is to write a function that can identify the palindrome among all the numbers. I first convert each product number into string format and reverse the string order to match the number order of original string.
# identify each number whether it is a palindrome or not
def is_palindrom(num):
num_str = str(num)
return num_str == num_str[::-1
The second step is to iterate all the possible outcome of the product of two 3-digit numbers. the two numbers are iterate from 999 to 1 decrement by 1 each iteration. if the product of i, j is larger than the current max product, then update the current max product, else, continue.
def largest_palindrom():
max_product = float('-inf')
for i in range(999,0,-1):
for j in range(999,0,-1):
product = i*j
if is_palindrom(product) and len(str(i)) == 3 and len(str(j))==3:
if product > max_product:
max_product = product
return max_product
After running the program. The largest palindrome product is 906609 and two 3-digit numbers are 993 and 913.
Coins Sums
In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:
- 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).
It is possible to make £2 in the following way:
- 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
The idea is to use brute force to search all the possible combinations of the coins and select the combinations that sums up to the target value.
def combination_sum(candidates, target):
def bt(combs,comb,candidates, target):
if target < 0:
return
if target == 0:
combs.append(comb[:])
return
for coin in candidates:
if (not comb) or (comb and coin >= comb[-1]):
comb.append(coin)
bt(combs,comb,candidates,target-coin)
comb.pop()
return
combs, comb = [],[]
bt(combs,comb,candidates,target)
return combs
the second step is to set up all the necessary input variable and run the above function.
candidates = [1,2,5,10,20,50,100,200]
target = 200
combs = combination_sum(candidates, target)
print("there are total %i combinations"%len(combs))
The total combinations are 73682.
Prime Power Triples
The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
- $28 = 2^2 + 2^3 + 2^4 $
- $33 = 3^2 + 2^3 + 2^4$
- $49 = 5^2 + 2^3 + 2^4$
- $47 = 2^2 + 3^3 + 2^4$
How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?
The first step is to identify the limit of the three numbers. since the product must below 50,000,000. The prime square must below 7072, the prime cube must below 368. The fourth power prime must below 84. I create four lists to store the prime square, prime cube, prime fourth power and non prime numbers. i then store all possible sums in a set and return the length of the set
def count():
p2,p3,p4,not_prime = [],[],[],[]
for i in range(2,7072):
if i not in not_prime:
p2.append(i**2)
if i < 368:
p3.append(i**3)
if i < 84:
p4.append(i**4)
for j in range(2*i,7072,i):
not_prime.append(j)
counter, found = 0, set()
for a in p2:
for b in p3:
for c in p4:
N = a + b + c
if N < 50000000:
found.add(N)
answer = len(found)
return answer
after running the program, it shows that there are total 1097343 power triplets.