-
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
233168
#def Euler1(N): # """ failed at larger N due to large rounding error in python3 """ # m3 = [i*3 for i in range(int((N-0.1)//3)+1)] # m5 = [i*5 for i in range(int((N-0.1)//5)+1)] # rs = set(m3+m5) # return sum(rs) " algorithmic approach - all pass" def Euler1(N): " algorithmic approach - all pass" m3 = int((N-0.1)//3) m5 = int((N-0.1)//5) m15 = int((N-0.1)//15) m3_sum = 3*(1+m3)*m3//2 m5_sum = 5*(1+m5)*m5//2 m15_sum = 15*(1+m15)*m15//2 rs = m3_sum+m5_sum-m15_sum return rs
-
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed N (<four million), find the sum of the even-valued terms.
''' Question 2 Fibonacci sequence ''' ''' F(1)=0, F(2)=1 , F(n) = F(n-1)+F(n-2) ''' def Euler2(x): a, b = 0, 1 even = 0 l = [a] # fib list while b <= x: a, b = b, a+b if a%2 ==0: even+=a return even
-
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
def LargestPrime(n): ''' start with largest prime number even number remove 2 until odd ''' maxPrime = 1 while n % 2 == 0: n = n//2 maxPrime = 2 for i in range(3,int(n**0.5)+1,1): while n % i ==0: n = n//i maxPrime = i if n > 2: maxPrime = n return maxPrime
-
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 which is less than N.
def panlidromic(x): maxP = 1 for i in range(int(x**0.5),100,-1): for j in range(min(x//i,999),100,-1): #3 digits p = i*j if p > maxP: s = str(p) if s == s[::-1]: maxP = max(maxP, p) return None if maxP <=1 else maxP # ---------------------------------- # quick method: # palindromic = 1e5*a + 1e4*b + 1e3*c + 1e2*b + 10a # = 100001a + 10010b + 1100 c # = 11(9091a+910b+100c) # ---------------------------------- def panlidromic2(): # check if i or j is divisible by 11 maxP = 1 for i in range(990,110,-11): for j in range(999,100,-1): #3 digits p = i*j if p > maxP: s = str(p) if s == s[::-1]: maxP = max(maxP, p) return None if maxP <=1 else maxP
-
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? 232792560
#find prime factors #for multiples of 3, starts with 9, increase every 2x3 def fast_primes(n): """ Returns a list of primes < n """ sieve = [True] * (n+1) for i in range(3,int(n**0.5)+1,2): if sieve[i]: #for multiples of 3, starts with 9, increase every 2x3 sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i]) return [2]+[i for i in range(3,n+1,2) if sieve[i]] def smallest_divider(x): '''find all primes <= x ''' prime = {x:1 for x in fast_primes(x)} prime[2] = int(math.log(x,2)) prime_list = [x for x in prime.keys() if x != 2] for u in range(3,x+1,2): for p in prime_list: print ('--',u,p) if u>p: print (u,p) c = 0 while u % p == 0: u = u//p c += 1 prime[p] = max(c,prime[p]) print (prime) product = 1 for k, v in prime.items(): product = k**v*product return product # gcd method def gcd(x,y): while y!=0: x,y=y,x%y return x def smallest_divider(x): '''p = A X B / gcd(A,B)''' p = 2**int(math.log(x,2)) for a in range(3,x+1,1): p = a*p//gcd(a,p) return p
-
The sum of the squares of the first ten natural numbers is,
$1^2+2^2+...+10^2=385$ The square of the sum of the first ten natural numbers is,
$(1+2+...+10)^2=55^2=3025$ Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025−385=2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
#1 + 2 + ……….. + n = n(n+1) / 2 #1^2 + 2^2 + ……… + n^2 = n(n+1)(2n+1) / 6 def Euler6(N): return (N*(N+1)//2)**2-N*(N+1)*(2*N+1)//6
-
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
A: 10001 th prime is 104743
def fast_primes(n): """ Returns a list of primes < n """ sieve = [True] * (n+1) for i in range(3,int(n**0.5)+1,2): if sieve[i]: #for multiples of 3, starts with 9, increase every 2x3 sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i]) return [2]+[i for i in range(3,n+1,2) if sieve[i]] def Euler7(x): scale_factor = 3 prime_list = [] count = 0 while len(prime_list)<x: prime_list = fast_primes(x*scale_factor) scale_factor = scale_factor *10 count +=1 return prime_list[x]
-
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 .......
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
def Euler8(x,k): s = [int(i) for i in str(x)] maxp = -1 for i in range(len(s)-k+1): p = 1 if 0 in s[i:i+k]: p = 0 else: for j in s[i:i+k]: p = p*j print (s[i:i+k], ' product = ',p) maxp = max(p,maxp)
-
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
'''a < N/3 b > a a+b > c > N/3 b > N/6 ''' def pythagorean(N): for a in range(N//3,0,-1): for b in range(a+1,(N-a)//2+1,1): c = N-a-b if (c > b)&( b+a>c): if a**2+b**2==c**2: print ('triangle',a,b,c) return a*b*c return -1
-
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
------- '''ref https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes''' --------
def sieve_of_Eratosthenes(N):
sieve = [True] * (n+1)
sieve[4::2] = [False] * (n//2-1)
for i in range(3,int(n**0.5)+1,2):
if sieve[i]:
#for multiples of 3, starts with 9, increase every 2x3
sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i])
summ = 2
l ={2:2}
for x in range(3,n):
if sieve[x]:
summ += x
l[x] = summ
return l- The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
def Euler11(A):
N = len(A)
maxP = 0
for j in range(N):
for i in range(N):
if i+4<=N:
H = [A[j][i],A[j][i+1],A[j][i+2],A[j][i+3]]
if 0 in H:
continue
maxP = max(maxP, A[j][i]*A[j][i+1]*A[j][i+2]*A[j][i+3])
# print (H, ' s= ',maxS, 'p = ',maxP//10000)
if j+4<=N:
V = [A[j][i],A[j+1][i],A[j+2][i],A[j+3][i]]
if 0 in V:
continue
maxP = max(maxP, A[j][i]*A[j+1][i]*A[j+2][i]*A[j+3][i])
if (i+4<=N)&(j+4<=N):
D = [A[j][i],A[j+1][i+1],A[j+2][i+2],A[j+3][i+3]]
if 0 in D:
continue
maxP = max(maxP, A[j][i]*A[j+1][i+1]*A[j+2][i+2]*A[j+3][i+3])
if (j>=3)&(i+4<=N):
D= [A[j][i],A[j-1][i+1],A[j-2][i+2],A[j-3][i+3]]
if 0 in D:
continue
maxP = max(maxP,A[j][i]*A[j-1][i+1]*A[j-2][i+2]*A[j-3][i+3])
return maxP- The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
76576500
def find_factors(x):
factors = 1
for i in range(2,int(math.sqrt(x))+1,1):
if x % i ==0:
factors += 2 if i != x//i else 1
return factors
def Euler12(n):
l = {}
for x in range(2,50000,1):
l[x] = find_factors(x)
l[1] = 0
factors = 0
i = 2
while factors <n:
if i%2 ==0:
factors = (l[i//2]+1)*(l[i+1]+1)-1
else:
factors = (l[i]+1)*(l[(i+1)//2]+1)-1
i += 1
return i*(i-1)//2- Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
s = sum([int(input()) for l in range(int(input()))])
print (str(s)[0:10])- The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even) n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
def collatz(n):
return n//2 if n%2==0 else 3*n+1
"""define list of steps to reach 1 for all numbers are 0
for each number n,
record all the intermediates and store it in a list
if x > N, do not skip recording until x falls under N
calculate steps for each intermediates
compare maxchain and maxid, update if new high
"""
def Euler14(N):
l = [0]*(N+1)
l[2] = 1
maxid_list = [0,1]
maxid, maxchain = 1,0
for n in range(2,N+1,1):
c, x = 0, n
steps = [[c,x]]
while l[x] == 0:
x = collatz(x)
c += 1
while x>N:
x = collatz(x)
c += 1
steps.append([c,x])
if len(steps)>1:
for s, v in steps[:-1]:
l[v] = l[steps[-1][-1]]+steps[-1][0]-s
if maxchain <= l[n]: #x is the last number of steps with max counts
maxchain, maxid = l[n], n
# print ('n: %d | maxchain:%d|maxid: %d'%(n,maxchain,maxid))
# print (steps,'\n')
maxid_list.append(maxid)
return maxid_list- Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
137846528820
def print_grid(grid):
for _ in grid:
print (_)
print ('-'*20)
def euler15(N,M):
# f(i,j) = f(i-1,j)+f(i,j-1)
grid = [[1]*(N+1)]+[[1]+[0]*N for i in range(M)]
for j in range(1,M+1):
for i in range(1,N+1):
grid[j][i] = grid[j-1][i]+grid[j][i-1]
return grid[M][N]
# ----------- quick method ----------- #
""" it takes 40 steps to reach to the destination, and out of them 20 are arrow right. So the question becomes choosing 20 out of 40. 20C40 """
def fac(x):
rs = 1
for i in range(x,1,-1):
rs = i*rs
return rs
def Euler15_quick(N,M):
MOD = 10**9+7
return fac(M+N)//fac(M)//fac(N)%MOD-
$2^{15} = 32768$ and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number
print (sum([int(a) for a in str(2**1000)])- If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.
class Euler17:
dict_a ={0:'',1:'One',2:'Two',3:'Three',4:'Four',5:'Five',6:'Six',7:'Seven',8:'Eight',9:'Nine',10:'Ten',11:'Eleven',12:'Twelve',13:'Thirteen',14:'Fourteen',15:'Fifteen', 16:'Sixteen', 17:'Seventeen',
18:'Eighteen',19:'Eighteen'}
dict_b={2:'Twenty',3:'Thirty',4:'Forty',5:'Fifty',6:'Sixty',7:'Seventy',8:'Eighty',9:'Ninety'}
def read_hundred(self,x):
word = []
c,b,a = (x%1000)//100,(x%100)//10,x%10
if c>0:
word += [self.dict_a[c],'Hundred']
if b>=2:
word += [self.dict_b[(x%100)//10], self.dict_a[x%10]]
else:
word += [self.dict_a[x%100]]
return word
def to_words(self,x):
words = []
if x >= 1000000000:
words += self.read_hundred(x//1000000000) +['Billion']
x = x%1000000000
if x >= 1000000:
words += self.read_hundred((x%1000000000)//1000000)+ ['Million']
x = x%1000000
if x >= 1000:
words += self.read_hundred((x%1000000)//1000)+ ['Thousand']
x = x%1000
if x<1000:
words += self.read_hundred(x)
words = ' '.join([w for w in words if w !=''])
print (words)
E17 = Euler17()
E17.to_words(1100020098)- By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3 7 4 2 4 6 8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
#bottom-up approach
def Euler18(A):
n = len(A)
for i in range(n-2,-1,-1):
for j in range(len(A[i])):
A[i][j] = max(A[i][j]+A[i+1][j],A[i][j]+A[i+1][j+1])
print (A[0][0])- You are given the following information, but you may prefer to do some research for yourself.
- 1 Jan 1900 was a Monday.
- Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine.
- A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? 171
def Euler19(y1, m1, d1, y2, m2, d2):
#1 Jan 1900 is Monday
days_in_month = [31,28,31,30,31,30,31,31,30,31,30,31]
days_in_leap_month = [31,29,31,30,31,30,31,31,30,31,30,31]
y0 = 1900
duration = 2800 #weekday patterns repeat every 2800 years
#import numpy as np
# months=np.zeros(duration*12)
# mark =np.zeros(duration*12)
# months[0::2]=31 #Jan
# months[1::12]=28 #Feb
# months[3::12]=30 #Apr
# months[5::12]=30 #Jun
# months[6::12]=31 #Jul
# months[7::12]=31 #Aug
# months[8::12]=30 #Sep
# months[9::12]=31 #Oct
# months[10::12]=30
# months[11::12]=31
# array of days in months
months=[0]*duration*12
mark =[0]*duration*12
months[0::2] =[31]*len(months[0::2]) #Jan
months[1::12]=[28]*len(months[1::12]) #Feb
months[3::12]=[30]*len(months[3::12]) #Apr
months[5::12]=[30]*len(months[5::12]) #Jun
months[6::12]=[31]*len(months[6::12]) #Jul
months[7::12]=[31]*len(months[7::12]) #Aug
months[8::12]=[30]*len(months[8::12]) #Sep
months[9::12]=[31]*len(months[9::12]) #Oct
months[10::12]=[30]*len(months[10::12])
months[11::12]=[31]*len(months[11::12])
# 1992 is leap year. in x years,
for i in range(0,duration):
# if leap year
if (y0+i)%4 == 0 and ((y0+i)%100!=0 or (y0+i)%400==0):
months[12*i+1] = 29
sum_days = 0
for i in range(len(months)):
sum_days+=months[i]
if sum_days%7==6:
mark[i+1] = 1 #sum of Jan-March is Apr 1st
mark = mark*5 # backup twice is enough, but just in case
#the weekday calendar repeat every 2800 years. creates 4816 sundays
multiple = lambda y: (y-1900)//2800
multiple1 = multiple(y1)
multiple2 = multiple(y2)
y1 = y1 - multiple1*2800
y2 = y2 - multiple2*2800
while y2<y1:
multiple2 += -1
y2 += 2800
sundays = (multiple2-multiple1)*4816
## calculaltion within the array length
i,j = (y1-y0)*12+m1-1,(y2-y0)*12+m2
if d1>1: #01/03 = start on 02/01
i+=1
# print (y1,m1,d1,' index ',i, ' ', y2,m2,d2,' index ',j,' sum:', sum(mark[i:j]))
if len(mark[i:j])>0:
print (sundays+sum(mark[i:j]))
else:
print (sundays+0)
return- n! means n × (n − 1) × ... × 3 × 2 × 1
For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!
def Euler20(x):
# sum of digits of x!
p = 1
for i in range(1,x+1):
p = p*i
print (sum([int(x) for x in str(p)]))- Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a)=b and d(b)=a, where a!=b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1,2,4,5,10,11,20,22,44,55 and 110; therefore d(220)=284. The proper divisors of 284 are 1,2,4,71 and 142; so d(284)=220.
Evaluate the sum of all the amicable numbers under 10000. 31626
def find_all_factors(x):
factors=[]
for i in range(2,int(math.sqrt(x))+1,1):
if x % i ==0:
factors += [i,x//i]
return set(factors)
def Euler21(N):
maximum = N
records = [0]*N
amicable = []
for i in range(3,maximum):
factors = find_all_factors(i)
sum_factors = 1+sum(factors)
if sum_factors>i: #only record sum > its own
records[i] = sum_factors
# print (i, ' - - - record - - ')
elif sum_factors<i: #check records
if records[sum_factors] ==i:
amicable+=[i,sum_factors]
# print ('sum < i ',records[sum_factors])
print (amicable, sum(amicable))
return amicable- Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3+15+12+9+14=53, is the 938th name in the list. So, COLIN would obtain a score of 938×53=49714.
What is the total of all the name scores in the file? 871198282
names = ["HOSEA","SHAD","SANTO","RUDOLF","ROLF","REY","RENALDO","MARCELLUS","LUCIUS","KRISTOFER","BOYCE","BENTON","HAYDEN","HARLAND","ARNOLDO","RUEBEN","LEANDRO","KRAIG","JERRELL", ...]
def mapping_func22(name):
return sum([ord(x.lower())-96 for x in name])
def Euler22(names):
names = sorted(names)
score = 0
for i in range(len(names)):
score += mapping_func22(names[i])*(1+names.index(names[i]))
print (score)- A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1+2+4+7+14=28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1+2+3+4+6=16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. 4179871
def sum_of_divisors(x):
s = 0
for i in range(2,int(math.sqrt(x))+1,1):
if x % i ==0:
s += i if i==x//i else x//i+i
return s+1
def Euler23(N=28123):
# all numbers > 28123 can be written as the sum of two abundant numbers
abundant = [i for i in range(3,N) if sum_of_divisors(i)>i ]
is_abundant_sum = [False]*(N)
for i in abundant:
for j in abundant:
z = i+j
if z <N and is_abundant_sum[z] is False:
is_abundant_sum[z]=True
return sum([i for i, x in enumerate(is_abundant_sum) if x is False])
- A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
- The Fibonacci sequence is defined by the recurrence relation:
Fn + Fn-1 + Fn-2 where F1 = 1 and F2 = 1
Hence the first 12 terms will be: 1,1,2,3,5,8,13,21,34,55,89,144
The 12th term, F12 , is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
- a