<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Project Euler
This Python 3 notebook contains some solutions for the Project Euler challenge.
/!\ Warning
Step1:  Problem 51
Step2:  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.
Step3:  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.
Step4:  Done!
Problem 52
Step5:  Done, it was quick.
Problem 53
<ASSISTANT_TASK:>
Python Code:
%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")
Explanation: Project Euler
This Python 3 notebook contains some solutions for the Project Euler challenge.
/!\ Warning: do not spoil yourself the pleasure of solving these problems by yourself!
I (Lilian Besson) started to work again on Project Euler in October 2020
I should try to work on it again, hence this notebook...
Common tool
Let's write here a few efficient functions that are used in lots of problems.
End of explanation
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)
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
Explanation: Problem 51: prime digit replacements (pastis ! 51 je t'aime)
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.
End of explanation
%%time
find_prime_digit_replacements(max_size_family=6)
%%time
find_prime_digit_replacements(max_size_family=7)
Explanation: 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.
End of explanation
%%time
find_prime_digit_replacements(max_size_family=8)
Explanation: 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.
End of explanation
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()
Explanation: Done!
Problem 52: Permuted multiples
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.
End of explanation
%load_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)
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)
Explanation: Done, it was quick.
Problem 53: Combinatoric selections
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?
End of explanation
<END_TASK>