def is_prime(n):
if n < 5:
return n == 2 or n == 3
elif n % 2 == 0 or n % 3 == 0:
return False
for i in range(5, int(n**0.5)+1, 6):
if n % i == 0 or n % (i+2) == 0:
return False
return TrueSolutions to Project Euler’s second 50 problems
algorithm
project euler
python
numba
These are codes to solve the second 50 problems in Project Euler. These python codes will give solutions in less than 1 second. This is achieved by using the excellent numba package.
Problem 51
%%time
def problem51(max_digits=6):
position_list = [[i, j, k] for i in range(6) for j in range(i+1, 6)
for k in range(j+1, 6)]
for origin in range(10**(max_digits-3)):
for position in position_list:
start_digit = 0 if position[0] == 0 else 1
fail_count = start_digit
answer = []
for digit in range(start_digit, 10):
origin_str = "{:0{}d}".format(origin, max_digits-3)
expanded_digits = [str(digit)] * 6
expanded_digits[position[0]] = origin_str[0]
expanded_digits[position[1]] = origin_str[1]
expanded_digits[position[2]] = origin_str[2]
generated_number = int("".join(expanded_digits))
if is_prime(generated_number) == False:
fail_count += 1
if fail_count == 3:
break
else:
answer.append(generated_number)
if len(answer) == 8:
return answer[0]
print(problem51())121313
CPU times: user 40 ms, sys: 0 ns, total: 40 ms
Wall time: 40.9 msProblem 52
%%time
def problem52(limit=10**7):
for i in range(1, limit):
sorted_i = sorted(str(i))
if sorted_i == sorted(str(2*i)):
if sorted_i == sorted(str(3*i)):
if sorted_i == sorted(str(4*i)):
if sorted_i == sorted(str(5*i)):
if sorted_i == sorted(str(6*i)):
return i
print(problem52())142857
CPU times: user 208 ms, sys: 0 ns, total: 208 ms
Wall time: 205 msProblem 53
from math import factorial%%time
def problem53():
count = 0
for n in range(23, 101):
for r in range(1, n):
if factorial(n) // (factorial(r) * factorial(n-r)) > 10**6:
count += 1
return count
print(problem53())4075
CPU times: user 12 ms, sys: 0 ns, total: 12 ms
Wall time: 9.28 msProblem 54
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p054_poker.txt'
with urlopen(url) as response:
DATA = response.read().decode()
def get_rank_value(hand):
CARD_TO_VALUE = dict(zip('23456789TJQKA', range(13)))
RANK_LIST = ['Royal Flush', 'Straight Flush', 'Four of a Kind',
'Full House', 'Flush', 'Straight', 'Three of a Kind',
'Two Pairs', 'One Pair', 'High Card']
RANK = dict(zip(RANK_LIST, range(9,-1,-1)))
cards = [CARD_TO_VALUE[card[0]] for card in hand]
is_flush = len(set([card[1] for card in hand])) == 1
card_freqs = sorted([(cards.count(card), card) for card in set(cards)])
n_cards = len(card_freqs)
value = sum([card_freqs[i][1]*10**(2*i) for i in range(n_cards)])
if card_freqs[-1][0] == 4:
return (RANK['Four of a Kind'], value)
elif card_freqs[-1][0] == 3:
if n_cards == 2:
return (RANK['Full House'], value)
else:
return (RANK['Three of a Kind'], value)
elif card_freqs[-1][0] == 2:
if n_cards == 3:
return (RANK['Two Pairs'], value)
else:
return (RANK['One Pair'], value)
elif (((card_freqs[4][1] - card_freqs[0][1]) == 4) or
((card_freqs[4][1] == CARD_TO_VALUE['A'] and
card_freqs[0][1] == CARD_TO_VALUE['2'] and
card_freqs[3][1] == CARD_TO_VALUE['5']))):
if is_flush:
if card_freqs[0][1] == CARD_TO_VALUE['A']:
return (RANK['Royal Flush'], value)
else:
return (RANK['Straight Flush'], value)
else:
return (RANK['Straight'], value)
elif is_flush:
return (RANK['Flush'], value)
else:
return (RANK['High Card'], value)%%time
def problem54():
lines = DATA.strip().split('\n')
count = 0
for line in lines:
cards = line.split()
player_1 = cards[:5]
player_2 = cards[5:]
if get_rank_value(player_1) > get_rank_value(player_2):
count += 1
return count
print(problem54())376
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 17.8 msProblem 55
%%time
def problem55(limit=10000):
c = 0
for i in range(limit):
n = i
n_t = int(str(n)[::-1])
is_Lychrel = True
for j in range(49):
n = n + n_t
n_t = int(str(n)[::-1])
if n == n_t:
is_Lychrel = False
break
if is_Lychrel:
c += 1
return c
print(problem55())249
CPU times: user 40 ms, sys: 0 ns, total: 40 ms
Wall time: 40.7 msProblem 56
%%time
def problem56():
max_digital_sum = 0
for a in range(100):
for b in range(100):
d_sum = sum([int(x) for x in str(a**b)])
if d_sum > max_digital_sum:
max_digital_sum = d_sum
return max_digital_sum
print(problem56())972
CPU times: user 128 ms, sys: 0 ns, total: 128 ms
Wall time: 130 msProblem 57
from fractions import Fraction%%time
def problem57():
x = 2 + Fraction(1, 2)
count = 0
for i in range(1000):
y = x - 1
if len(str(y.numerator)) > len(str(y.denominator)):
count += 1
x = 2 + Fraction(1, x)
return count
print(problem57())153
CPU times: user 40 ms, sys: 0 ns, total: 40 ms
Wall time: 40.9 msProblem 58
from numba import jit
@jit
def is_prime(n):
if n < 5:
return n == 2 or n == 3
elif n % 2 == 0 or n % 3 == 0:
return False
for i in range(5, int(n**0.5)+1, 6):
if n % i == 0 or n % (i+2) == 0:
return False
return True%%time
@jit
def problem58():
x = 1
gap = 0
n_prime_x10 = 0
n_x = 1
while True:
gap = gap + 2
for i in range(3):
x = x + gap
if is_prime(x):
n_prime_x10 += 10
x = x + gap
n_x += 4
if n_prime_x10 < n_x:
return int(x**0.5)
print(problem58())26241
CPU times: user 216 ms, sys: 4 ms, total: 220 ms
Wall time: 220 msProblem 59
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p059_cipher.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem59():
cipher = list(map(lambda x: int(x), DATA.rstrip().split(',')))
length = len(cipher)
ord_a = ord('a')
for i in range(ord_a, ord_a+26):
for j in range(ord_a, ord_a+26):
for k in range(ord_a, ord_a+26):
key = ([i, j, k] * (length//3+1))[:length]
message = bytes([x^y for x, y in zip(cipher, key)])
if b'that' in message and b'have' in message:
return sum([ord(x) for x in message.decode()])
print(problem59())107359
CPU times: user 332 ms, sys: 0 ns, total: 332 ms
Wall time: 333 msProblem 60
import numpy as np
from numba import jit, int8, int64
@jit(int8[:](int64))
def create_sieve_of_halfprimes(n):
sieve = np.ones(n//2, dtype=np.int8)
for i in range(3, int(n**0.5)+1, 2):
if sieve[i//2]:
sieve[i*i//2::i] = 0
return sieve
@jit(int8[:,:](int8[:], int64[:]))
def create_check_matrix(sieve, primes):
check_matrix = np.zeros((len(primes), len(primes)), dtype=np.int8)
for i1 in range(len(primes)):
for i2 in range(i1+1, len(primes)):
half_prime12 = (primes[i1]
* 10**(int(np.log10(primes[i2]))+1)
+ primes[i2]) // 2
if sieve[half_prime12]:
half_prime21 = (primes[i2]
* 10**(int(np.log10(primes[i1]))+1)
+ primes[i1]) // 2
if sieve[half_prime21]:
check_matrix[i1, i2] = 1
return check_matrix
@jit(int64(int64[:], int8[:,:]))
def find_answer(primes, check_matrix):
for a1 in range(len(primes)):
for a2 in range(a1+1, len(primes)):
if check_matrix[a1, a2]:
for a3 in range(a2+1, len(primes)):
if check_matrix[a2, a3] and check_matrix[a1, a3]:
for a4 in range(a3+1, len(primes)):
if (check_matrix[a3, a4] and check_matrix[a2, a4]
and check_matrix[a1, a4]):
for a5 in range(a4+1, len(primes)):
if (check_matrix[a4, a5]
and check_matrix[a3, a5]
and check_matrix[a2, a5]
and check_matrix[a1, a5]):
return (primes[a1] + primes[a2]
+ primes[a3] + primes[a4]
+ primes[a5])
return 0%%time
def problem60(limit=10**4):
sieve = create_sieve_of_halfprimes(limit**2)
primes = 2*np.nonzero(sieve[:limit//2])[0][1:] + 1
check_matrix = create_check_matrix(sieve, primes)
return find_answer(primes, check_matrix)
print(problem60())26033
CPU times: user 296 ms, sys: 4 ms, total: 300 ms
Wall time: 298 msProblem 61
def create_polygonal_numbers(k):
l = []
p = n = 1
while p < 10000:
if p >= 1000:
l.append(p)
n = n + 1
p = n * ((k-2)*n - k + 4) // 2
return l
def check(a, b, c, d, e, f, polygonal_dict):
ab = a*100 + b
bc = b*100 + c
cd = c*100 + d
de = d*100 + e
ef = e*100 + f
fa = f*100 + a
for i1 in polygonal_dict[ab]:
for i2 in polygonal_dict[bc]:
for i3 in polygonal_dict[cd]:
for i4 in polygonal_dict[de]:
for i5 in polygonal_dict[ef]:
for i6 in polygonal_dict[fa]:
if len(set([i1,i2,i3,i4,i5,i6])) == 6:
return True
return False%%time
def problem61():
polygonal_dict = dict()
for k in range(3, 9):
for n in create_polygonal_numbers(k):
if n not in polygonal_dict:
polygonal_dict[n] = [k]
else:
polygonal_dict[n].append(k)
cyclic = dict()
for n in polygonal_dict:
a, b = (n//100, n%100)
if b < 10:
continue
if a not in cyclic:
cyclic[a] = [b]
else:
cyclic[a].append(b)
for a in cyclic:
for b in cyclic[a]:
if b not in cyclic:
continue
for c in cyclic[b]:
if c not in cyclic:
continue
for d in cyclic[c]:
if d not in cyclic:
continue
for e in cyclic[d]:
if e not in cyclic:
continue
for f in cyclic[e]:
if f not in cyclic:
continue
if a not in cyclic[f]:
continue
if check(a, b, c, d, e, f, polygonal_dict):
return sum([a,b,c,d,e,f]) * 101
print(problem61())28684
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 741 µsProblem 62
from collections import Counter%%time
def problem62():
k = 1
while True:
cubes = []
for n in range(int(int('1'*k)**(1/3))+1, int(int('9'*k)**(1/3))+1):
cubes.append(n**3)
arranged_cubes = [''.join(sorted(str(x))) for x in cubes]
counter = Counter(arranged_cubes)
for c in list(counter):
if counter[c] == 5:
return cubes[arranged_cubes.index(c)]
k += 1
print(problem62())127035954683
CPU times: user 28 ms, sys: 0 ns, total: 28 ms
Wall time: 28.3 msProblem 63
%%time
def problem63():
n = 1
c = 1
while len(str(9**n)) >= n:
for i in range(2, 10):
if i**n >= 10**(n-1):
c += 1
n += 1
return c
print(problem63())49
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 141 µsProblem 64
def count_period(n):
if n == int(n**0.5)**2:
return 0
b = 0
c = 1
l = []
while True:
if (b,c) in l:
return len(l) - l.index((b,c))
l.append((b,c))
b = int((n**0.5 + b) / c) * c - b
c = (n - b**2) // c%%time
def problem64(limit=10**4):
c = 0
for i in range(2, limit+1):
if count_period(i) % 2 == 1:
c += 1
return c
print(problem64())1322
CPU times: user 420 ms, sys: 0 ns, total: 420 ms
Wall time: 419 msProblem 65
from fractions import Fraction%%time
def problem65():
fraction_list = [2]
for i in range(1, 34):
fraction_list += [1, 2*i, 1]
rational_approx = Fraction(fraction_list[-1])
for a in fraction_list[-2::-1]:
rational_approx = a + 1 / rational_approx
return sum([int(x) for x in str(rational_approx.numerator)])
print(problem65())272
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.02 msProblem 66
from fractions import Fraction
def diophantine_solution(D):
if D == int(D**0.5)**2:
return 1
b = 0
c = 1
a = a0 = int(D**0.5)
fraction_list = []
while True:
a = int((D**0.5 + b) / c)
if a == 2*a0:
break
fraction_list.append(a)
b = a*c - b
c = (D - b**2) // c
rational_approx = Fraction(fraction_list[-1])
for a in fraction_list[-2::-1]:
rational_approx = a + 1 / rational_approx
if rational_approx.numerator**2 - D*rational_approx.denominator**2 == 1:
return rational_approx.numerator
rational_approx = rational_approx + a0
for a in fraction_list[::-1]:
rational_approx = a + 1 / rational_approx
return rational_approx.numerator%%time
def problem66(limit=1000):
x_max = 3
d_max = 2
for i in range(3, limit+1):
x = diophantine_solution(i)
if x > x_max:
x_max = x
d_max = i
return d_max
print(problem66())661
CPU times: user 96 ms, sys: 0 ns, total: 96 ms
Wall time: 93.3 msProblem 67
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p067_triangle.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem67():
triangle = [[int(y) for y in x.split()] for x in DATA.rstrip().split('\n')]
route = [59]
for i, row in enumerate(triangle[1:]):
current = [row[0] + route[0]] \
+ [x + max(route[j], route[j+1]) for j, x in enumerate(row[1:-1])] \
+ [row[-1] + route[-1]]
route = current
return max(route)
print(problem67())7273
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 2.3 msProblem 68
%%time
def problem68():
solutions = []
a = 10
for b in range(1, 10):
for c in range(1, 10):
if b == c:
continue
for d in range(1, 10):
if d in [b, c]:
continue
e = a + b - d
if e < 1 or e > 9 or e in [b, c, d]:
continue
for f in range(1, 10):
if f in [b, c, d, e]:
continue
g = c + d - f
if g < 1 or g > 9 or g in [b, c, d, e, f]:
continue
for h in range(1, 10):
if h in [b, c, d, e, f, g]:
continue
i = e + f - h
j = g + h - b
if i < 1 or j < 1 or i > 9 or j > 9:
continue
if len(set([a,b,c,d,e,f,g,h,i,j])) == 10:
solutions.append([a,b,c,d,c,e,f,e,g,h,g,i,j,i,b])
ordered_solutions = []
for solution in solutions:
i_min = solution.index(min(solution[0], solution[3],
solution[6], solution[9], solution[12]))
ordered_solution = solution[i_min:] + solution[:i_min]
ordered_solution_to_int = int(''.join(
[str(x) for x in ordered_solution]))
ordered_solutions.append(ordered_solution_to_int)
return max(ordered_solutions)
print(problem68())6531031914842725
CPU times: user 0 ns, sys: 4 ms, total: 4 ms
Wall time: 1.34 msProblem 69
import numpy as np%%time
def problem69(limit=10**6):
sieve = np.ones(limit+1)
n_per_phi_n_list = np.ones(limit+1)
for i in range(2, int(limit**0.5)+1):
if sieve[i] == 1:
sieve[i::i] = 0
n_per_phi_n_list[i::i] *= i / (i-1)
return np.argmax(n_per_phi_n_list)
print(problem69())510510
CPU times: user 28 ms, sys: 0 ns, total: 28 ms
Wall time: 27.5 msProblem 70
import numpy as np
from numba import jit
@jit
def create_sieve(n):
sieve = np.ones(n, dtype=np.int8)
sieve[0] = sieve[1] = 0
sieve[4::2] = 0
for i in range(3, int(n**0.5)+1, 2):
if sieve[i]:
sieve[i*i::i] = 0
return sieve%%time
def problem70(limit=10**7):
sieve = create_sieve(limit)
prime_list = np.nonzero(sieve)[0]
nb_primes = len(prime_list)
n_min = 87109
ratio_min = 87109 / 79180
i_max = np.nonzero((prime_list ** 2) >= 10**7)[0][0]-1
for i in range(i_max, -1, -1):
if prime_list[i] / (prime_list[i]-1) >= ratio_min:
break
for j in range(i+1, nb_primes):
i_times_j = prime_list[i] * prime_list[j]
if i_times_j >= 10**7:
break
phi_i_times_j = (prime_list[i]-1) * (prime_list[j]-1)
ratio = i_times_j / phi_i_times_j
if ratio < ratio_min:
if sorted(str(i_times_j)) == sorted(str(phi_i_times_j)):
n_min = i_times_j
ratio_min = ratio
return n_min
print(problem70())8319823
CPU times: user 280 ms, sys: 0 ns, total: 280 ms
Wall time: 279 msProblem 71
from fractions import Fraction%%time
def problem71(limit=10**6):
d_min = 5
n_min = 2
for d in range(2, limit+1):
n = 3 * d // 7
if d % 7 == 0:
n = n-1
if n * d_min > d * n_min:
n_min = n
d_min = d
return Fraction(n_min, d_min).numerator
print(problem71())428570
CPU times: user 220 ms, sys: 0 ns, total: 220 ms
Wall time: 219 msProblem 72
import numpy as np
from numba import jit%%time
@jit
def problem72(limit=10**6):
sieve = np.ones(limit+1)
phi_n_list = np.arange(limit+1)
phi_n_list[1] = 0
for i in range(2, limit+1):
if sieve[i] == 1:
sieve[i*i::i] = 0
phi_n_list[i::i] *= (i-1)
phi_n_list[i::i] //= i
return sum(phi_n_list)
print(problem72())303963552391
CPU times: user 360 ms, sys: 0 ns, total: 360 ms
Wall time: 359 msProblem 73
from numba import jit
@jit
def count_Stern_Brocot(limit, left_n, left_d, right_n, right_d):
mid_n = left_n + right_n
mid_d = left_d + right_d
if mid_d > limit:
return 0
else:
count = 1
count += count_Stern_Brocot(limit, left_n, left_d, mid_n, mid_d)
count += count_Stern_Brocot(limit, mid_n, mid_d, right_n, right_d)
return count%%time
def problem73(limit=12000):
return count_Stern_Brocot(12000, 1, 3, 1, 2)
print(problem73())7295372
CPU times: user 124 ms, sys: 0 ns, total: 124 ms
Wall time: 124 msProblem 74
from math import factorial
from itertools import permutations
def count_permuation(n):
p = set(permutations(str(n)))
if str(n)[0] == '1':
new_str = '0' + str(n)[1:]
p = p.union(set(permutations(new_str)))
if str(n)[:2] == '11':
new_str = '00' + str(n)[2:]
p = p.union(set(permutations(new_str)))
if str(n)[:3] == '111':
new_str = '000' + str(n)[3:]
p = p.union(set(permutations(new_str)))
if str(n)[:4] == '1111':
new_str = '0000' + str(n)[4:]
p = p.union(set(permutations(new_str)))
if str(n)[:5] == '11111':
p = p.add(str(n)[5:]+'00000')
c = 0
for e in p:
if e[0] != '0':
c += 1
return c%%time
def problem74():
fac = [factorial(x) for x in range(10)]
a = [0] * 2200000
answer_list = []
for i1 in range(10):
for i2 in range(i1, 10):
for i3 in range(i2, 10):
for i4 in range(i3, 10):
for i5 in range(i4, 10):
for i6 in range(i5, 10):
i = i1*10**5+i2*10**4+i3*1000+i4*100+i5*10+i6
chain = []
j = i
while (a[j] == 0) and (j not in chain):
chain.append(j)
s = 0
jr = j
while jr != 0:
s += fac[jr % 10]
jr //= 10
j = s
if j in chain:
for t in range(len(chain)):
a[chain[t]] = len(chain) - t
if chain[t] == j:
break
for t1 in range(t+1, len(chain)):
a[chain[t1]] = len(chain) - t
else:
for t, k in enumerate(chain):
a[k] = len(chain) - t + a[j]
if a[i] == 60:
answer_list.append(i)
return sum([count_permuation(answer) for answer in answer_list])
print(problem74())402
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 18.7 msProblem 75
from numba import jit
@jit
def gcd(m, n):
if m == 0:
return n
return gcd(n % m, m)%timeit
def problem75(limit=1500000):
d = [0] * (limit + 1)
for n in range(1, 1000):
for m in range(n+1, 1000, 2):
if gcd(m, n) != 1:
continue
L = 2 * m * (m + n)
k_max = limit // L
for k in range(1, k_max+1):
d[L*k] += 1
c = 0
for i in range(limit+1):
if d[i] == 1:
c += 1
return c
print(problem75())161667Problem 76
import numpy as np%%time
def problem76():
A = np.zeros((101, 101), dtype=np.int)
for i in range(1, 101):
for j in range(1, i+1):
A[i, j] = 1
for k in range(j, i//2+1):
A[i, j] += A[i-k, k]
return A[100, 1] - 1
print(problem76())190569291
CPU times: user 24 ms, sys: 0 ns, total: 24 ms
Wall time: 21.3 msProblem 77
import numpy as np
def is_prime(n):
if n < 5:
return n == 2 or n == 3
elif n % 2 == 0 or n % 3 == 0:
return False
for i in range(5, int(n**0.5)+1, 6):
if n % i == 0 or n % (i+2) == 0:
return False
return True%%time
def problem77():
A = np.zeros((101, 101), dtype=np.int)
for i in range(1, 101):
for j in range(1, i+1):
if is_prime(i):
A[i, j] = 1
for k in range(j, i//2+1):
if is_prime(k):
A[i, j] += A[i-k, k]
if A[i, j] > 5000 + is_prime(i):
return i
print(problem77())71
CPU times: user 20 ms, sys: 0 ns, total: 20 ms
Wall time: 20.5 msProblem 78
from numba import jit%%time
@jit
def problem78(limit=60000):
p = [0] * limit
p[0] = 1
p[1] = 1
for i in range(2, limit):
k = 1
s = 1
g_k = 0
while True:
g_k += 2*k - 1
if g_k > i:
break
p[i] = p[i] + s*p[i-g_k]
g_k += k
if g_k > i:
break
p[i] = p[i] + s*p[i-g_k]
k += 1
s = -s
p[i] = p[i] % 10**6
if p[i] == 0:
return i
print(problem78())55374
CPU times: user 100 ms, sys: 0 ns, total: 100 ms
Wall time: 102 msProblem 79
from urllib.request import urlopen
from itertools import permutations, combinations
url = 'https://projecteuler.net/project/resources/p079_keylog.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem79():
for p in permutations(''.join(sorted(list(set(DATA) - {'\n'})))):
passcode = ''.join(p)
passcode_keys = [''.join(x) for x in combinations(passcode, 3)]
flag = True
for key in DATA.split():
if key not in passcode_keys:
flag = False
break
if flag == True:
return passcode
print(problem79())73162890
CPU times: user 300 ms, sys: 0 ns, total: 300 ms
Wall time: 300 msProblem 80
from decimal import getcontext, Decimal%%time
def problem80():
getcontext().prec = 102
s = 0
for i in range(1, 101):
if i not in [y**2 for y in range(1, 11)]:
s += sum([int(x) for x in str(Decimal(i).sqrt())[:101]
if x != '.'])
return s
print(problem80())40886
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 4.47 msProblem 81
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p081_matrix.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem81():
matrix = [[int(y) for y in x.split(',')] for x in DATA.split()]
path_sum = [[0]*80]*80
for i in range(80):
for j in range(80):
if i == 0 and j == 0:
min_path = 0
elif i == 0:
min_path = path_sum[i][j-1]
elif j == 0:
min_path = path_sum[i-1][j]
else:
min_path = min(path_sum[i][j-1], path_sum[i-1][j])
path_sum[i][j] = matrix[i][j] + min_path
return path_sum[79][79]
print(problem81())427337
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 3.94 msProblem 82
from urllib.request import urlopen
import numpy as np
url = 'https://projecteuler.net/project/resources/p082_matrix.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem82():
matrix = np.array([[int(y) for y in x.split(',')] for x in DATA.split()],
dtype='uint16')
path_sum = np.zeros((80, 80), dtype='uint32')
min_path = np.zeros((80, 80), dtype='uint32')
for j in range(80):
for i in range(80):
if j == 0:
min_path = [0]
else:
min_path = [path_sum[i, j-1]]
for k in range(80):
if k < i:
min_path.append(matrix[k:i, j].sum()
+ path_sum[k, j-1])
if k > i:
min_path.append(matrix[i+1:k+1, j].sum()
+ path_sum[k, j-1])
path_sum[i, j] = matrix[i, j] + min(min_path)
return path_sum[:,79].min()
print(problem82())260324
CPU times: user 956 ms, sys: 0 ns, total: 956 ms
Wall time: 958 msProblem 83
from urllib.request import urlopen
import numpy as np
url = 'https://projecteuler.net/project/resources/p083_matrix.txt'
with urlopen(url) as response:
DATA = response.read().decode()
def update(i, j, path_sum, matrix, inf):
min_around = [inf]
if i > 0:
min_around.append(path_sum[i-1, j])
if i < 79:
min_around.append(path_sum[i+1, j])
if j > 0:
min_around.append(path_sum[i, j-1])
if j < 79:
min_around.append(path_sum[i, j+1])
path_sum[i, j] = min(min_around) + matrix[i, j]%%time
def problem83():
matrix = np.array([[int(y) for y in x.split(',')] for x in DATA.split()],
dtype='uint16')
inf = np.iinfo(np.uint32).max // 2
path_sum = np.zeros((80, 80), dtype='uint32')
path_sum[:] = inf
path_sum[0, 0] = matrix[0, 0]
visited = np.zeros((80, 80), dtype='bool')
visited[0, 0] = True
update(0, 1, path_sum, matrix, inf)
update(1, 0, path_sum, matrix, inf)
while not visited[79, 79]:
i, j = np.unravel_index(np.ma.argmin(
np.ma.MaskedArray(path_sum, visited)), (80, 80))
visited[i, j] = True
if i > 0 and not visited[i-1, j]:
update(i-1, j, path_sum, matrix, inf)
if i < 79 and not visited[i+1, j]:
update(i+1, j, path_sum, matrix, inf)
if j > 0 and not visited[i, j-1]:
update(i, j-1, path_sum, matrix, inf)
if j < 79 and not visited[i, j+1]:
update(i, j+1, path_sum, matrix, inf)
return path_sum[79, 79]
print(problem83())425185
CPU times: user 360 ms, sys: 0 ns, total: 360 ms
Wall time: 359 msProblem 84
from random import randint%%time
def problem84():
jail = 10
g2j = 30
cc = [2, 17, 33]
ch = [7, 22, 36]
double = 0
table = [0] * 40
i = 0
for j in range(100000):
dice1 = randint(1, 4)
dice2 = randint(1, 4)
if dice1 == dice2:
double += 1
else:
double = 0
if double == 3:
i = jail
else:
i = (i + dice1 + dice2) % 40
if i in cc:
cc_open = randint(1, 16)
if cc_open == 1:
i = 0
elif cc_open == 2:
i = jail
if i in ch:
ch_open = randint(1, 16)
if ch_open == 1:
i = 0
elif ch_open == 2:
i = jail
elif ch_open == 3:
i = 11
elif ch_open == 4:
i = 24
elif ch_open == 5:
i = 39
elif ch_open == 6:
i = 5
elif ch_open in [7, 8]:
if i == ch[0]:
i = 15
elif i == ch[1]:
i = 25
else:
i = 5
elif ch_open == 9:
if i == ch[1]:
i = 28
else:
i = 12
elif ch_open == 10:
i = (i-3)%40
if i == g2j:
i = jail
table[i] += 1
a, b, c = sorted(table, reverse=True)[:3]
return '{:02d}{:02d}{:02d}'.format(table.index(a),
table.index(b), table.index(c))
print(problem84())101516
CPU times: user 232 ms, sys: 0 ns, total: 232 ms
Wall time: 234 msProblem 85
%%time
def problem85():
areas = []
rectangles = []
for n in range(1, 3000):
for m in range(n, 3000//n):
areas.append(n * m)
rectangles.append(n * m * (n+1) * (m+1) // 4)
ds = [int(abs(r - 2e6)) for r in rectangles]
return areas[ds.index(min(ds))]
print(problem85())2772
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 6.8 msProblem 86
from numba import jit%%time
@jit
def problem86():
n_sol = 0
M = 0
while n_sol <= 10**6:
M += 1
for a_plus_b in range(2, 2*M+1):
min_square = M**2 + a_plus_b**2
if min_square == (int(min_square**0.5)**2):
b_min = max(1, a_plus_b-M)
b_max = a_plus_b//2
n_sol += (b_max - b_min + 1)
return M
print(problem86())1818
CPU times: user 84 ms, sys: 0 ns, total: 84 ms
Wall time: 83.7 msProblem 87
import numpy as np
from numba import jit%%time
@jit
def problem87():
limit = 5*10**7-1
x_max = int(limit**(1/2))
y_max = int(limit**(1/3))
z_max = int(limit**(1/4))
sieve = np.ones(x_max+1, dtype=np.bool)
sieve[0] = sieve[1] = 0
for i in range(2, int(limit**0.5)+1):
if sieve[i] == 1:
sieve[2*i::i] = 0
x_list = np.nonzero(sieve[:x_max+1])[0]
y_list = np.nonzero(sieve[:y_max+1])[0]
z_list = np.nonzero(sieve[:z_max+1])[0]
A = np.zeros(limit+1, dtype=np.bool)
for x in x_list:
for y in y_list:
for z in z_list:
n = x**2 + y**3 + z**4
if n <= limit:
A[n] = 1
return A.sum()
print(problem87())1097343
CPU times: user 512 ms, sys: 4 ms, total: 516 ms
Wall time: 514 msProblem 88
%%time
def problem88():
k_max = 12000
product_max = 2 * k_max
a_max = k_max // 4
m_max = k_max
prod = 1
mps = [2*k_max] * (k_max+1)
mps[0] = mps[1] = 0
for a in range(1, a_max//prod+1):
prod = a
for b in range(a, a_max//prod+1):
prod = a*b
for c in range(b, a_max//prod+1):
prod = a*b*c
for d in range(c, a_max//prod+1):
prod = a*b*c*d
for e in range(d, a_max//prod+1):
prod = a*b*c*d*e
for f in range(e, a_max//prod+1):
prod = a*b*c*d*e*f
for g in range(f, a_max//prod+1):
prod = a*b*c*d*e*f*g
for h in range(g, a_max//prod+1):
prod = a*b*c*d*e*f*g*h
for i in range(h, a_max//prod+1):
prod = a*b*c*d*e*f*g*h*i
for j in range(i, a_max//prod+1):
prod = a*b*c*d*e*f*g*h*i*j
for k in range(j, a_max//prod+1):
prod = a*b*c*d*e*f*g*h*i*j*k
l_min = max(2, k)
l_max = k_max // (2*prod)
for l in range(l_min,
l_max+1):
for m in range(l,
k_max+1):
prod = (a*b*c*d*e*f*g
*h*i*j*k*l*m)
s = (a+b+c+d+e+f+g+h
+i+j+k+l+m)
kk = prod - s + 13
if kk > k_max:
break
if prod < mps[kk]:
mps[kk] = prod
return sum(set(mps))
print(problem88())7587457
CPU times: user 232 ms, sys: 0 ns, total: 232 ms
Wall time: 235 msProblem 89
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p089_roman.txt'
with urlopen(url) as response:
DATA = response.read().decode()
def minimize_form(number):
number = number.replace('VIIII', 'IX')
number = number.replace('IIII', 'IV')
number = number.replace('LXXXX', 'XC')
number = number.replace('XXXX', 'XL')
number = number.replace('DCCCC', 'CM')
number = number.replace('CCCC', 'CD')
return number%%time
def problem89():
return (sum([len(x) for x in DATA.split()])
- sum([len(minimize_form(x)) for x in DATA.split()]))
print(problem89())743
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 1.1 msProblem 90
from itertools import combinations, product
def check(square, pairs):
if (square[0], square[1]) in pairs or (square[1], square[0]) in pairs:
return True
else:
return False%%time
def problem90():
arrangements = [set(x) | {'6', '9'} if ('6' in x or '9' in x)
else set(x) for x in combinations('0123456789', 6)]
squares = ['01', '04', '09', '16', '25', '36', '49', '64', '81']
c = 0
for dice1 in arrangements:
for dice2 in arrangements:
pairs = list(product(dice1, dice2))
flag = True
for square in squares:
if not check(square, pairs):
flag = False
break
if flag == True:
c += 1
return c//2
print(problem90())1217
CPU times: user 360 ms, sys: 0 ns, total: 360 ms
Wall time: 360 msProblem 91
from numba import jit@jit
def problem91():
s = 0
for i in range(0, 51):
for j in range(0, i):
c = i**2 + j**2
for a in range(0, 51):
for b in range(0, 51):
if a == 0 and b == 0:
continue
if a == i and b == j:
continue
if a**2 + b**2 + (i-a)**2 + (j-b)**2 == c:
s += 1
for k in range(1, 51):
if k**2 + k**2 == c + (i-k)**2 + (j-k)**2:
s += 1
return 2*s + 50*50
print(problem91())14234Problem 92
from numba import jit
@jit
def make_sum_digits2_table():
sum_digits2_table = [0] * 10**7
digits2 = [x**2 for x in range(10)]
for i1 in range(10):
for i2 in range(10):
for i3 in range(10):
for i4 in range(10):
for i5 in range(10):
for i6 in range(10):
for i7 in range(10):
num = (i1+i2*10+i3*100+i4*1000+i5*10000
+i6*100000+i7*1000000)
sd2 = (digits2[i1]+digits2[i2]+digits2[i3]
+digits2[i4]+digits2[i5]
+digits2[i6]+digits2[i7])
sum_digits2_table[num] = sd2
return sum_digits2_table%%time
@jit
def problem92():
sum_digits2_table = make_sum_digits2_table()
chain_end = [0] * 10**7
chain_end[1] = 1
chain_end[89] = 2
for i in range(1, 10**7):
j = i
while chain_end[j] == 0:
j = sum_digits2_table[j]
chain_end[i] = chain_end[j]
c = 0
for i in range(10**7):
if chain_end[i] == 2:
c += 1
return c
print(problem92())8581146
CPU times: user 432 ms, sys: 16 ms, total: 448 ms
Wall time: 451 msProblem 93
from itertools import combinations, permutations
from operator import add, truediv, mul, sub%%time
def problem93():
combos = dict()
ops = [add, truediv, mul, sub,
lambda a, b: sub(b, a), lambda a, b: truediv(b, a)]
for four_digit in list(combinations(range(1, 10), 4)):
A = [0]*10000
for (a, b, c, d) in permutations(four_digit):
for op1 in ops:
for op2 in ops:
for op3 in ops:
try:
num = op3(op2(op1(a,b),c),d)
except ZeroDivisionError:
continue
if num > 0 and num - int(num) < 0.001:
A[int(num)] = 1
A[0] = 1
combos[four_digit] = A.index(0) - 1
max_combo = max(combos, key=combos.get)
return ''.join([str(x) for x in max_combo])
print(problem93())1258
CPU times: user 304 ms, sys: 0 ns, total: 304 ms
Wall time: 303 msProblem 94
from numba import jit%%time
@jit
def problem94():
n_max = (10**9 - 2) // 6
s = 0
for n in range(2, n_max+1):
h2 = 3*n*n + 4*n + 1
if h2 == int(h2**0.5)**2:
s += (6*n+2)
h2 = 3*n*n - 4*n + 1
if h2 == int(h2**0.5)**2:
s += (6*n-2)
n = n_max+1
h2 = 3*n*n - 4*n + 1
if h2 == int(h2**0.5)**2:
s += (6*n-2)
return s
print(problem94())518408346
CPU times: user 632 ms, sys: 8 ms, total: 640 ms
Wall time: 639 msProblem 95
import numpy as np
from numba import jit
@jit
def get_proper_sum(limit):
sieve = np.ones(limit+1)
proper_sum = np.ones(limit+1, dtype=np.int32)
current_n = np.arange(limit+1)
for p in range(2, int(limit**0.5)+1):
if sieve[p] == 1:
sieve[p::p] = 0
for n in range(p, limit+1, p):
temp = proper_sum[n]
while current_n[n] % p == 0:
current_n[n] //= p
proper_sum[n] = proper_sum[n]*p + temp
current_n = (current_n != 1) + current_n
proper_sum = proper_sum * current_n - np.arange(limit+1)
return proper_sum%%time
@jit
def problem95():
limit = 10**6
proper_sum = get_proper_sum(limit)
checked = np.zeros(limit+1, dtype=np.int8)
checked[proper_sum > limit] = -1
checked[proper_sum == 1] = -1
checked[1] = -1
len_max = 0
start_min = 0
for i in range(2, limit+1):
if checked[i] != 0:
continue
next_i = i
while checked[next_i] == 0:
checked[next_i] = 1
next_i = proper_sum[next_i]
if checked[next_i] == 1:
j = i
while j != next_i:
checked[j] = -1
j = proper_sum[j]
chain_len = 1
chain_min = next_i
j = proper_sum[next_i]
while j != next_i:
checked[j] = -1
chain_len += 1
if j < chain_min:
chain_min = j
j = proper_sum[j]
if chain_len > len_max:
len_max = chain_len
start_min = chain_min
else:
j = i
while checked[j] == 1:
checked[j] = -1
j = proper_sum[j]
return start_min
print(problem95())14316
CPU times: user 808 ms, sys: 0 ns, total: 808 ms
Wall time: 808 msProblem 96
from urllib.request import urlopen
import numpy as np
url = 'https://projecteuler.net/project/resources/p096_sudoku.txt'
with urlopen(url) as response:
DATA = response.read().decode()
def scan(sudoku):
for num in range(9):
for a in range(3):
for b in range(3):
if sudoku[a,b,:,:,num].sum() == 1:
c_list, d_list = np.nonzero(sudoku[a,b,:,:,num])
return a, b, c_list[0], d_list[0], num
for num in range(9):
for c in range(3):
for d in range(3):
if sudoku[:,:,c,d,num].sum() == 1:
a_list, b_list = np.nonzero(sudoku[:,:,c,d,num])
return a_list[0], b_list[0], c, d, num
for num in range(9):
for a in range(3):
for c in range(3):
if sudoku[a,:,c,:,num].sum() == 1:
b_list, d_list = np.nonzero(sudoku[a,:,c,:,num])
return a, b_list[0], c, d_list[0], num
for a in range(3):
for b in range(3):
for c in range(3):
for d in range(3):
if sudoku[a,b,c,d,:].sum() == 1:
num_list = np.nonzero(sudoku[a,b,c,d,:])
return a, b, c, d, num_list[0][0]
return 0, 0, 0, 0, -1
def fill(sudoku, a, b, c, d, num):
sudoku[a, b, :, :, num] = 0
sudoku[:, :, c, d, num] = 0
sudoku[a, :, c, :, num] = 0
sudoku[a, b, c, d, :] = 0
sudoku[a, b, c, d, num] = 10
def scan_and_fill(sudoku):
a, b, c, d, num = scan(sudoku)
if num == -1:
return False
fill(sudoku, a, b, c, d, num)
return True
def solve(sudoku):
unknown = 81 - (sudoku == 10).sum()
while unknown != 0:
if not scan_and_fill(sudoku):
a, b, c, d = np.unravel_index(sudoku.sum(axis=4).argmin(),
dims=(3,3,3,3))
num_list = np.nonzero(sudoku[a,b,c,d])[0]
for num in num_list:
new_sudoku = sudoku.copy()
fill(new_sudoku, a, b, c, d, num)
if solve(new_sudoku):
sudoku[:] = new_sudoku[:]
return True
return False
unknown -= 1
return True
def read(quiz):
sudoku = np.ones((3, 3, 3, 3, 9), dtype=np.uint8)
for row in range(9):
for col in range(9):
a = row // 3
b = row % 3
c = col // 3
d = col % 3
num = int(quiz[row][col])
if num != 0:
fill(sudoku, a, b, c, d, num-1)
return sudoku%%time
def problem96():
s = 0
for i in range(50):
quiz = DATA.split()[11*i+2:11*i+11]
sudoku = read(quiz)
solve(sudoku)
a, b, c = np.nonzero(sudoku[0,0,0,:])[1]
s += (a+1)*100 + (b+1)*10 + (c+1)
return s
print(problem96())24702
CPU times: user 552 ms, sys: 0 ns, total: 552 ms
Wall time: 552 msProblem 97
%%time
def problem97():
28433*2**7830457+1
two_to_100000 = (2**100000) % 10**10
two_to_30457 = (2**30457) % 10**10
return (28433 * two_to_100000**78 * two_to_30457 + 1) % 10**10
print(problem97())8739992577
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 86.5 µsProblem 98
from urllib.request import urlopen
from collections import defaultdict
url = 'https://projecteuler.net/project/resources/p098_words.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem98():
word_list = DATA.strip('"').split('","')
anagram_dict = defaultdict(list)
for word in word_list:
anagram_dict[''.join(sorted(word))].append(word)
filter_dict = dict((key, value)
for (key, value) in anagram_dict.items() if len(value)>1)
square_dict = dict()
for i in set(len(key) for key in filter_dict.keys()):
square_max = int((10**i-1)**0.5)
square_min = int((10**(i-1)-1)**0.5)+1
square_dict[i] = [x**2 for x in range(square_min, square_max+1)]
s_max = 0
for key in filter_dict:
if len(filter_dict[key]) == 2:
word1, word2 = filter_dict[key]
for square in square_dict[len(key)]:
match = {w: s for w, s in zip(word1, str(square))}
reverse_match = {s: w for w, s in zip(word1, str(square))}
if len(match) != len(key) or len(reverse_match) != len(key):
continue
square2 = int(''.join([match[c] for c in word2]))
if square2 in square_dict[len(key)]:
if square > s_max:
s_max = square
if square2 > s_max:
s_max = square2
return s_max
print(problem98())18769
CPU times: user 116 ms, sys: 0 ns, total: 116 ms
Wall time: 115 msProblem 99
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p099_base_exp.txt'
with urlopen(url) as response:
DATA = response.read().decode()%%time
def problem99():
x_max = 1
y_max = 1
line_max = 0
for line, pair in enumerate(DATA.split(), 1):
x, y = [int(a) for a in pair.split(',')]
if x > x_max**(y_max/y):
x_max, y_max = x, y
line_max = line
return line_max
print(problem99())709
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 1.05 msProblem 100
%%time
def problem100():
pell_fund = (1, 1)
x, y = pell_fund
while x <= 2*10**12-1:
x, y = 3*x + 4*y, 2*x + 3*y
return (y+1)//2
print(problem100())756872327473
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 122 µs