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...

In [1]:

```
%load_ext Cython
```

In [2]:

```
%%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
```

In [3]:

```
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.

In [31]:

```
import itertools
```

In [34]:

```
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)

In [60]:

```
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.

In [61]:

```
%%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

Out[61]:

13

In [62]:

```
%%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

Out[62]:

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.

In [63]:

```
%%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

Out[63]:

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.*

In [22]:

```
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
```

In [25]:

```
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)
```

In [28]:

```
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
```

In [29]:

```
%%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

Out[29]:

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?*

In [5]:

```
%load_ext Cython
```

The Cython extension is already loaded. To reload it, use: %reload_ext Cython

In [7]:

```
%%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
```

In [8]:

```
choose_kn(10, 23)
```

Out[8]:

1144066

In [19]:

```
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
```

In [20]:

```
how_many_choose_kn_are_greater_than_x(100, 1e6)
```

Out[20]:

4075

That was quite easy.

In [ ]:

```
```