Project Euler 31~40
Problem 31
In England the currency is made up of pound, £, and pence, p, and 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
How many different ways can £2 be made using any number of coins?
|
Answer:
|
73682 |
# -*- coding: UTF-8 -*-
def func(money):
sum = 0
for a in range(money, -1, -200):
for b in range(a, -1, -100):
for c in range(b, -1, -50):
for d in range(c, -1, -20):
for e in range(d, -1, -10):
for f in range(e, -1, -5):
for g in range(f, -1, -2):
sum += 1
return sum
if __name__ == "__main__":
print func(200)
Problem 32
We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
|
Answer:
|
45228 |
# -*- coding: UTF-8 -*-
'''要产生A*B=C，并且str(A)+Str(B)+Str(C)只包含[1-9]\
只有两种情况len(A)=1,len(B)=4,len(C)=4或len(A)=2,len(B)=3,len(C)=4
'''
def is_pandigital(a, b):
strc = str(a) + str(b) + str(a * b)
if len(strc) != 9:
return False
ilist = set(strc)
ilist.add('0')
if len(ilist) == 10:
return True
return False
print sum(set(a * b for a in range(1, 100) for b in range(100, 10000)\
if is_pandigital(a, b)))
Problem 33
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
|
Answer:
|
100 |
# -*- coding: UTF-8 -*-
def get_gcd(a, b):
return b and get_gcd(b, a % b) or a
def is_the_fraction(a, b):
if a / 10 == a % 10 or b /10 == b % 10:
return False
if a % 10 != b / 10:
return False
if a * (b % 10) == (a / 10) * b:
return True
return False
def sum_fraction():
result = 1.0
for a in range(10, 100):
for b in range(a, 100):
if is_the_fraction(a, b):
c = get_gcd(a, b)
result *= float(b) / float(a)
return result
print sum_fraction()
Problem 34
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of their digits.
Note: as 1! = 1 and 2! = 2 are not sums they are not included.
|
Answer:
|
40730 |
# -*- coding: UTF-8 -*-
def fac(n):
return reduce(lambda x, y:x * y,[i for i in range(1, n + 1)])
fact1 =[1,1]
fact2 = [fac(i) for i in range(2, 10)]
fact1.extend(fact2)
def get_up_limit():
n=1
while(10 ** n - n * fac(9) <0):
n +=1
return n * fac(9)
def sum_of_fac(n):
s = 0
while n > 0:
d = n % 10
s += fact1[d]
n /= 10
return s
n = get_up_limit()
print sum( i for i in xrange(10, n) if i == sum_of_fac(i))
Problem 35
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
|
Answer:
|
55 |
# -*- coding: UTF-8 -*-
import math
def sieve_method(num):
prime_data = [x for x in xrange(num + 1)]
for i in xrange(2,int(math.sqrt(num) + 1)):
if prime_data[i]:
start = i**2
step = i
prime_data[start::step]=((num-start)/step + 1) * [0]
prime_data[1] = 0
return prime_data
prime_data = sieve_method(1000000)
def is_circular(n):
i = str(n)
length = len(i)
if len(i) == 1:
return True
else:
while length > 1:
i = i[-1] +i[:-1]
if prime_data[int(i)] == 0:
return False
length -= 1
return True
ilist = []
for i in prime_data:
if i:
if is_circular(i):
ilist.append(i)
print len(ilist)
Problem 36
The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
|
Answer:
|
872187 |
def is_palindromic(n, base):
digits = []
reverse = []
while n > 0:
d = n % base
digits.append(d)
reverse.insert(0, d)
n /= base
return digits == reverse
print sum(n for n in xrange(1, 1000000) if is_palindromic(n, 10) and \
is_palindromic(n, 2))
Problem 37
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
|
Answer:
|
748317 |
import math
def sieve_method(n):
prime_data = [x for x in xrange(n + 1)]
for i in xrange(2, int(math.sqrt(n) + 1)):
start = i ** 2
step = i
prime_data[start::step] = ((n - start) / step + 1) * [0]
prime_data[1] = 0
return prime_data
def is_truncateble(n):
i, j = str(n), str(n)
while len(i) > 1: # left to right
i = i[:-1]
if prime_data[int(i)] == 0:
return False
while len(j) > 1: # rught to left
j = j[1:]
if prime_data[int(j)] == 0:
return False
return True
ilist=[]
prime_data = sieve_method(1000000)
for n in prime_data:
if n and is_truncateble(n):
ilist.append(n)
print sum(ilist[4:15]) # 2, 3, 5, 7 not contain
Problem 38
Take the number 192 and multiply it by each of 1, 2, and 3:
192
192
192
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n 
1?
|
Answer:
|
932718654 |
def is_1to9_product(n):
i=2
j = str(n)
while len(j) < 9:
j += str(n * i)
i += 1
if len(j) ==9:
s = set(j)
s.add('0')
if len(s) == 10:
return int(j)
return 0
def get_max():
maxt = 0
for i in range(10000):
c = is_1to9_product(i)
if c:
maxt = max(maxt, c)
return maxt
print get_max()
Problem 39
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p 
1000, is the number of solutions maximised?
|
Answer:
|
840 |
import math
def func(p):
dict={}
for a in range(1, p / 3):
for b in range(a,(p - a) / 2):
c=int(math.sqrt(a*a+b*b))
if a*a+b*b==c*c:
try:
dict[a+b+c]+=1
except KeyError:
dict[a+b+c]=1
return dict
dict = func(1001)
mx, mxp = -1, -1
for (k, v) in dict.items():
if v>mx:
mx, mxp= v, k
print mxp, mx
Problem 40
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021...
It can be seen that the 12th digit of the fractional part is 1.
If dn represents the nth digit of the fractional part, find the value of the following expression.
d1 d10 d100 d1000 d10000 d100000 d1000000
|
Answer:
|
210 |
s = [str(i) for i in range(1000000)]
strc = ''.join(s)
sum, j = 1, 1
while j <= 1000000:
sum *= int(strc[j])
j *= 10
print sum
2023年1月24日 22:12
Solvng Project Euler problems like 31~40 is a great way to sharpen your mathematical and problem-solving skills. In this particular problem, we are asked to figure out how many different realty properties Fitchburg ways there are to make £2 by using any number of coins in the English currency. By using the coins available in England – 1p, 2p, 5p, 10p, 20p, 50p, £1 and £2 – we can come up with a variety of combinations to make up the £2 total. For example, we can use 1x£1 and 1x50p, or 2x£1, or 1x£2 and 1x50p, or 1x£1 and 2x20p, and so on.