Solutions to Project Euler's second 50 problems
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¶
In [1]:
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
In [2]:
%%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())
Problem 52¶
In [3]:
%%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())
Problem 53¶
In [4]:
from math import factorial
In [5]:
%%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())
Problem 54¶
In [6]:
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)
In [7]:
%%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())
Problem 55¶
In [8]:
%%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())
Problem 56¶
In [9]:
%%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())
Problem 57¶
In [10]:
from fractions import Fraction
In [11]:
%%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())
Problem 58¶
In [12]:
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
In [13]:
%%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())
Problem 59¶
In [14]:
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p059_cipher.txt'
with urlopen(url) as response:
DATA = response.read().decode()
In [15]:
%%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())
Problem 60¶
In [16]:
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
In [17]:
%%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())
Problem 61¶
In [18]:
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
In [19]:
%%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())
Problem 62¶
In [20]:
from collections import Counter
In [21]:
%%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())
Problem 63¶
In [22]:
%%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())
Problem 64¶
In [23]:
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
In [24]:
%%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())
Problem 65¶
In [25]:
from fractions import Fraction
In [26]:
%%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())
Problem 66¶
In [27]:
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
In [28]:
%%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())
Problem 67¶
In [29]:
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p067_triangle.txt'
with urlopen(url) as response:
DATA = response.read().decode()
In [30]:
%%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())
Problem 68¶
In [31]:
%%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())
Problem 69¶
In [32]:
import numpy as np
In [33]:
%%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())
Problem 70¶
In [34]:
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
In [35]:
%%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())
Problem 71¶
In [36]:
from fractions import Fraction
In [37]:
%%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())
Problem 72¶
In [38]:
import numpy as np
from numba import jit
In [39]:
%%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())
Problem 73¶
In [40]:
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
In [41]:
%%time
def problem73(limit=12000):
return count_Stern_Brocot(12000, 1, 3, 1, 2)
print(problem73())
Problem 74¶
In [42]:
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
In [43]:
%%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())
Problem 75¶
In [44]:
from numba import jit
@jit
def gcd(m, n):
if m == 0:
return n
return gcd(n % m, m)
In [45]:
%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())
Problem 76¶
In [46]:
import numpy as np
In [47]:
%%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())
Problem 77¶
In [48]:
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
In [49]:
%%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())
Problem 78¶
In [50]:
from numba import jit
In [51]:
%%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())
Problem 79¶
In [52]:
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()
In [53]:
%%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())
Problem 80¶
In [54]:
from decimal import getcontext, Decimal
In [55]:
%%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())
Problem 81¶
In [56]:
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p081_matrix.txt'
with urlopen(url) as response:
DATA = response.read().decode()
In [57]:
%%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())
Problem 82¶
In [58]:
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()
In [59]:
%%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())
Problem 83¶
In [60]:
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]
In [61]:
%%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())
Problem 84¶
In [62]:
from random import randint
In [63]:
%%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())
Problem 85¶
In [64]:
%%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())
Problem 86¶
In [65]:
from numba import jit
In [66]:
%%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())
Problem 87¶
In [67]:
import numpy as np
from numba import jit
In [68]:
%%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())
Problem 88¶
In [69]:
%%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())
Problem 89¶
In [70]:
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
In [71]:
%%time
def problem89():
return (sum([len(x) for x in DATA.split()])
- sum([len(minimize_form(x)) for x in DATA.split()]))
print(problem89())
Problem 90¶
In [72]:
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
In [73]:
%%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())
Problem 91¶
In [74]:
from numba import jit
In [75]:
@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())
Problem 92¶
In [76]:
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
In [77]:
%%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())
Problem 93¶
In [78]:
from itertools import combinations, permutations
from operator import add, truediv, mul, sub
In [79]:
%%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())
Problem 94¶
In [80]:
from numba import jit
In [81]:
%%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())
Problem 95¶
In [82]:
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
In [83]:
%%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())
Problem 96¶
In [84]:
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
In [85]:
%%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())
Problem 97¶
In [86]:
%%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())
Problem 98¶
In [87]:
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()
In [88]:
%%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())
Problem 99¶
In [89]:
from urllib.request import urlopen
url = 'https://projecteuler.net/project/resources/p099_base_exp.txt'
with urlopen(url) as response:
DATA = response.read().decode()
In [90]:
%%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())
Problem 100¶
In [91]:
%%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())
Comments
Comments powered by Disqus