This Python 3 notebook contains some solutions for the Project Euler challenge.
I (Lilian Besson) started to work again on Project Euler in October 2020 I should try to work on it again, hence this notebook...
%load_ext Cython
%%cython
import math
def erathostene_sieve(int n):
cdef list primes = [False, False] + [True] * (n - 1) # from 0 to n included
cdef int max_divisor = math.floor(math.sqrt(n))
cdef int i = 2
for divisor in range(2, max_divisor + 1):
if primes[divisor]:
number = 2*divisor
while number <= n:
primes[number] = False
number += divisor
return primes
sieve10million = erathostene_sieve(int(1e7))
primes_upto_10million = [p for p,b in enumerate(sieve10million) if b]
print(f"There are {len(primes_upto_10million)} prime numbers smaller than 10 million")
There are 664579 prime numbers smaller than 10 million
By replacing the 1st digit of the 2-digit number x3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56xx3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
Who it doesn't seem easy, I can't (yet) think of an efficient solution.
import itertools
prime = 56003
nb_digit_prime = len(str(prime))
nb_replacements = 2
for c in itertools.combinations(range(nb_digit_prime), nb_replacements):
print(c)
(0, 1) (0, 2) (0, 3) (0, 4) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
from typing import List
def find_prime_digit_replacements(max_size_family: int=6, primes: List[int]=primes_upto_10million) -> int:
set_primes = set(primes)
# we explore this list of primes in ascending order,
# so we'll find the smallest that satisfy the property
# for prime in primes:
for prime in range(10, max(primes) + 1):
str_prime = str(prime)
# for this prime, try all the possibilities
nb_digit_prime = len(str_prime)
for nb_replacements in range(1, nb_digit_prime + 1): # cannot replace all the digits
# now try to replace nb_replacements digits (not necessarily adjacent)
for positions in itertools.combinations(range(nb_digit_prime), nb_replacements):
size_family = 0
good_digits = []
good_primes = []
for new_digit in range(0, 9 + 1):
if positions[0] == 0 and new_digit == 0:
continue
new_prime = int(''.join(
(c if i not in positions else str(new_digit))
for i,c in enumerate(str_prime)
))
if new_prime in set_primes:
size_family += 1
good_digits.append(new_digit)
good_primes.append(new_prime)
if size_family >= max_size_family:
print(f"For p = {prime} with {nb_digit_prime} digits, and {nb_replacements} replacement(s), we found")
print(f"a family of {size_family} prime(s) when replacing digit(s) at position(s) {positions}")
for new_digit, new_prime in zip(good_digits, good_primes):
print(f" {new_prime} obtained by replacing with digit {new_digit}")
return prime
Let's try to obtain the examples given in the problem statement, with the smallest prime giving a 6-sized family being 13 and the smallest prime giving a 7-sized family being 56003.
%%time
find_prime_digit_replacements(max_size_family=6)
For p = 13 with 2 digits, and 1 replacement(s), we found
a family of 6 prime(s) when replacing digit(s) at position(s) (0,)
13 obtained by replacing with digit 1
23 obtained by replacing with digit 2
43 obtained by replacing with digit 4
53 obtained by replacing with digit 5
73 obtained by replacing with digit 7
83 obtained by replacing with digit 8
CPU times: user 57.2 ms, sys: 24 µs, total: 57.2 ms
Wall time: 56.1 ms
13
%%time
find_prime_digit_replacements(max_size_family=7)
For p = 56003 with 5 digits, and 2 replacement(s), we found
a family of 7 prime(s) when replacing digit(s) at position(s) (2, 3)
56003 obtained by replacing with digit 0
56113 obtained by replacing with digit 1
56333 obtained by replacing with digit 3
56443 obtained by replacing with digit 4
56663 obtained by replacing with digit 6
56773 obtained by replacing with digit 7
56993 obtained by replacing with digit 9
CPU times: user 22.1 s, sys: 17.7 ms, total: 22.1 s
Wall time: 22.1 s
56003
The code seems to work pretty well. It's not that fast... but let's try to obtain the smallest prime giving a 8-sized family.
%%time
find_prime_digit_replacements(max_size_family=8)
For p = 120303 with 6 digits, and 3 replacement(s), we found
a family of 8 prime(s) when replacing digit(s) at position(s) (0, 2, 4)
121313 obtained by replacing with digit 1
222323 obtained by replacing with digit 2
323333 obtained by replacing with digit 3
424343 obtained by replacing with digit 4
525353 obtained by replacing with digit 5
626363 obtained by replacing with digit 6
828383 obtained by replacing with digit 8
929393 obtained by replacing with digit 9
CPU times: user 57.9 s, sys: 0 ns, total: 57.9 s
Wall time: 57.9 s
120303
Done!
It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.
def x_to_kx_contain_same_digits(x: int, kmax: int) -> bool:
digits_x = sorted(list(str(x)))
for k in range(2, kmax+1):
digits_kx = sorted(list(str(k*x)))
if digits_x != digits_kx:
return False
return True
assert not x_to_kx_contain_same_digits(125873, 2)
assert x_to_kx_contain_same_digits(125874, 2)
assert not x_to_kx_contain_same_digits(125875, 2)
assert not x_to_kx_contain_same_digits(125874, 3)
def find_smallest_x_such_that_x_to_6x_contain_same_digits(kmax: int=6) -> int:
x = 1
while True:
if x_to_kx_contain_same_digits(x, kmax):
print(f"Found a solution x = {x}, proof:")
for k in range(1, kmax + 1):
print(f" k x = {k}*{x}={k*x}")
return x
x += 1
%%time
find_smallest_x_such_that_x_to_6x_contain_same_digits()
Found a solution x = 142857, proof:
k x = 1*142857=142857
k x = 2*142857=285714
k x = 3*142857=428571
k x = 4*142857=571428
k x = 5*142857=714285
k x = 6*142857=857142
CPU times: user 357 ms, sys: 76 µs, total: 357 ms
Wall time: 356 ms
142857
Done, it was quick.
There are exactly ten ways of selecting three from five, 12345: 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345.
In combinatorics, we use the notation, ${5 \choose 3} = 10$. In general, $${n \choose r} = \frac{n!}{r! (n-r)!}$$
It is not until $n=23$, that a value exceeds one-million: ${23 \choose 10} = 1144066$.
How many, not necessarily distinct, values of ${n \choose r}$ for $1 \leq n \leq 100$, are greater than one-million?
%load_ext Cython
The Cython extension is already loaded. To reload it, use: %reload_ext Cython
%%cython
def choose_kn(int k, int n):
# {k choose n} = {n-k choose n} so first let's keep the minimum
if k < 0 or k > n:
return 0
elif k > n-k:
k = n-k
# instead of computing with factorials (that blow up VERY fast),
# we can compute with product
product = 1
for p in range(k+1, n+1):
product *= p
for p in range(2, n-k+1):
product //= p
return product
choose_kn(10, 23)
1144066
def how_many_choose_kn_are_greater_than_x(max_n: int, x: int) -> int:
count = 0
for n in range(1, max_n + 1):
for k in range(1, n//2 + 1):
c_kn = choose_kn(k, n)
if c_kn > x:
count += 1
if n-k != k:
# we count twice for (n choose k) and (n choose n-k)
# only if n-k != k
count += 1
return count
how_many_choose_kn_are_greater_than_x(100, 1e6)
4075
That was quite easy.