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×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
In [1]:
from euler import timer
def p031():
return len(
[1 for p200 in range(0, 201, 200)
for p100 in range(0,201 - p200, 100)
for p50 in range(0,201 - p200 - p100, 50)
for p20 in range(0,201 - p200 - p100 - p50, 20)
for p10 in range(0,201 - p200 - p100 - p50 - p20, 10)
for p5 in range(0,201 - p200 - p100 - p50 - p20 - p10, 5)
for p2 in range(0,201 - p200 - p100 - p50 - p20 - p10 - p5, 2)])
timer(p031)
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.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
In [1]:
from math import sqrt
from euler import Seq, timer
def isPandigital(n):
return (range(2, int(sqrt(n)))
>> Seq.filter(lambda x: n%x==0)
>> Seq.map (lambda x: (str(x) + str(n/x) + str(n)) >> Seq.toSet)
>> Seq.exists (lambda x: x == {'1','2','3','4','5','6','7','8','9'}))
def p032():
return range(1000, 10000) >> Seq.filter(isPandigital) >> Seq.sum
timer(p032)
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.
In [2]:
from euler import Seq, GCD, fst, snd, timer
def p033():
def is_cancelling(a,b):
a_str, b_str = str(a), str(b)
for i in range(2):
for j in range(2):
if a_str[i] == b_str[j]:
return float(a_str[not i]) / float(b_str[not j]) == float(a) / float(b)
return False
def numbers(n):
return range(n,100) >> Seq.filter(lambda x: (x%10 != 0) & (x%10 != x/10))
fraction = (numbers(10)
>> Seq.collect(lambda x: numbers(x+1) >> Seq.map(lambda y: (x,y)))
>> Seq.filter(lambda (x,y): is_cancelling(x,y))
>> Seq.reduce(lambda x,y: (fst(x)*fst(y), snd(x)*snd(y))))
# then define the denominator by the greatest common divisor
return snd(fraction) / GCD(fst(fraction), snd(fraction))
timer(p033)
In [3]:
from math import factorial
from euler import Seq, fst, timer
def p034():
def factsum(n):
acc = 0
while n >= 1:
acc += factorial(n%10)
n /= 10
return acc
max_n = (fst(Seq.initInfinite(lambda x: (x, x * factorial(9)))
>> Seq.find(lambda (a,b): (10 ** a - 1) > b)) - 1) * factorial(9)
def nums():
for i in range(3, max_n + 1):
if i == factsum(i):
yield i
return nums() >> Seq.sum
timer(p034)
In [4]:
from euler import Seq, primes, timer
def p035():
def contains_even(n):
return str(n) >> Seq.map(int) >> Seq.exists(lambda x: x%2==0)
def shift(n):
str_n = str(n)
return int(str_n[1:] + str_n[0])
def circle(n):
yield n
m = shift(n)
while m != n:
yield m
m = shift(m)
p = (primes()
>> Seq.filter(lambda n: not(contains_even(n)))
>> Seq.takeWhile(lambda x: x<1000000)
>> Seq.toList)
def next_p(n): return p >> Seq.find(lambda m: m > n)
n = 2
while n is not None:
if not(all((i in p) for i in circle(n))):
for i in circle(n):
if i in p:
p.remove(i)
n = next_p(n)
return (p >> Seq.length) + 1
timer(p035)
The decimal number, $585 = 1001001001_2$ (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.)
In [5]:
from euler import Seq, timer
def p036():
def dec_is_palindrome(n):
return str(n)[::-1] == str(n)
def bin_is_palindrome(n):
a = (Seq.unfold(lambda x: (x%2, x/2) if (x != 0) else None, n)
>> Seq.toList)
return a == list(reversed(a))
return (
range(1,1000001)
>> Seq.filter(dec_is_palindrome)
>> Seq.filter(bin_is_palindrome)
>> Seq.sum)
timer(p036)
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.
In [6]:
from euler import Seq, primes, is_prime, timer
def p037():
def is_truncatable_prime(n):
x = str(n)
for i in range(1,len(x)):
if not(is_prime(int(x[i:])) & is_prime(int(x[:i]))):
return False
return True
return (
primes()
>> Seq.skipWhile(lambda x: x <= 7)
>> Seq.filter(is_truncatable_prime)
>> Seq.take(11)
>> Seq.sum)
timer(p037)
Take the number 192 and multiply it by each of 1, 2, and 3:
192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 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?
In [8]:
from euler import Seq, timer
# largest integer to test is 9876 (2*x concat x)
def p038():
def get_pandigital(num):
i = 0
concat_num = ''
while len(concat_num) < 9:
i += 1
concat_num += str(num * i)
if (len(concat_num) == 9) and (sorted(map(int, concat_num)) == range(1,10)):
return int(concat_num)
else:
return None
return max(get_pandigital(n) for n in range(9876,0,-1))
timer(p038)
In [9]:
from euler import Seq, timer
def p039():
def sols(p):
return sum(1 for a in range(1,p-1)
for b in range(a, p-a)
if (p - a - b) ** 2 == a ** 2 + b ** 2)
return range(3, 1001) >> Seq.maxBy(sols)
timer(p039)
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 $d_n$ represents the nth digit of the fractional part, find the value of the following expression.
$d_1 × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000}$
In [11]:
from euler import timer
def p040():
s = "".join(range(1,500001) >> Seq.map(str))
return (
Seq.init(7, lambda i: int(s[10 ** i - 1]))
>> Seq.reduce(lambda x,y: x*y))
timer(p040)