#!/usr/bin/env python # coding: utf-8 # # [Project Euler](https://ProjectEuler.net) # [This Python 3 notebook](Project%20Euler%20%28Python%203%29.ipynb) contains *some* solutions for the [Project Euler](https://ProjectEuler.net) challenge. # # ### /!\ **Warning:** do not spoil yourself the pleasure of solving these problems by yourself! # # [I (Lilian Besson)](http://perso.crans.org/besson/) started to work again on Project Euler in October 2020 # I should try to work on it again, hence this notebook... # # ![Badge giving the number of solved problems](https://ProjectEuler.net/profile/Naereen.png?ok "Badge giving the number of solved problems") # --- # ## Common tool # # Let's write here a few efficient functions that are used in lots of problems. # In[1]: get_ipython().run_line_magic('load_ext', 'Cython') # In[2]: get_ipython().run_cell_magic('cython', '', 'import math\n\ndef erathostene_sieve(int n):\n cdef list primes = [False, False] + [True] * (n - 1) #\xa0from 0 to n included\n cdef int max_divisor = math.floor(math.sqrt(n))\n cdef int i = 2\n for divisor in range(2, max_divisor + 1):\n if primes[divisor]:\n number = 2*divisor\n while number <= n:\n primes[number] = False\n number += divisor\n 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") # --- # ## [Problem 51: prime digit replacements (pastis ! 51 je t'aime)](https://projecteuler.net/problem=51) # # 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) # 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]: get_ipython().run_cell_magic('time', '', 'find_prime_digit_replacements(max_size_family=6)') # In[62]: get_ipython().run_cell_magic('time', '', 'find_prime_digit_replacements(max_size_family=7)') # 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]: get_ipython().run_cell_magic('time', '', 'find_prime_digit_replacements(max_size_family=8)') # Done! # --- # ## [Problem 52: Permuted multiples](https://projecteuler.net/problem=52) # 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]: get_ipython().run_cell_magic('time', '', 'find_smallest_x_such_that_x_to_6x_contain_same_digits()') # Done, it was quick. # --- # ## [Problem 53: Combinatoric selections](https://projecteuler.net/problem=53) # # 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]: get_ipython().run_line_magic('load_ext', 'Cython') # In[7]: get_ipython().run_cell_magic('cython', '', "\ndef choose_kn(int k, int n):\n # {k choose n} = {n-k choose n} so first let's keep the minimum\n if k < 0 or k > n:\n return 0\n elif k > n-k:\n k = n-k\n # instead of computing with factorials (that blow up VERY fast),\n # we can compute with product\n product = 1\n for p in range(k+1, n+1):\n product *= p\n for p in range(2, n-k+1):\n product //= p\n return product") # In[8]: choose_kn(10, 23) # 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) # That was quite easy. # --- # ## [Problem 54: ](https://projecteuler.net/problem=54) # # TODO # --- # ## [Problem 55: ](https://projecteuler.net/problem=55) # # TODO # --- # ## Continue # In[ ]: