{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Project Euler](https://ProjectEuler.net)\n",
    "[This Python 3 notebook](Project%20Euler%20%28Python%203%29.ipynb) contains *some* solutions for the [Project Euler](https://ProjectEuler.net) challenge.\n",
    "\n",
    "### /!\\ **Warning:** do not spoil yourself the pleasure of solving these problems by yourself!\n",
    "\n",
    "[I (Lilian Besson)](http://perso.crans.org/besson/) started to work again on Project Euler in October 2020\n",
    "I should try to work on it again, hence this notebook...\n",
    "\n",
    "![Badge giving the number of solved problems](https://ProjectEuler.net/profile/Naereen.png?ok \"Badge giving the number of solved problems\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Common tool\n",
    "\n",
    "Let's write here a few efficient functions that are used in lots of problems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T11:11:02.088300Z",
     "start_time": "2020-10-16T11:11:01.675015Z"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T11:11:02.099602Z",
     "start_time": "2020-10-16T11:11:02.091219Z"
    }
   },
   "outputs": [],
   "source": [
    "%%cython\n",
    "import math\n",
    "\n",
    "def erathostene_sieve(int n):\n",
    "    cdef list primes = [False, False] + [True] * (n - 1)  # from 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T11:11:05.687141Z",
     "start_time": "2020-10-16T11:11:02.102348Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 664579 prime numbers smaller than 10 million\n"
     ]
    }
   ],
   "source": [
    "sieve10million = erathostene_sieve(int(1e7))\n",
    "primes_upto_10million = [p for p,b in enumerate(sieve10million) if b]\n",
    "print(f\"There are {len(primes_upto_10million)} prime numbers smaller than 10 million\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [Problem 51: prime digit replacements (pastis ! 51 je t'aime)](https://projecteuler.net/problem=51)\n",
    "\n",
    "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.\n",
    "\n",
    "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.\n",
    "\n",
    "*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.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Who it doesn't seem easy, I can't (yet) think of an efficient solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-17T11:09:43.862094Z",
     "start_time": "2020-10-17T11:09:43.856721Z"
    }
   },
   "outputs": [],
   "source": [
    "import itertools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-17T11:13:10.533412Z",
     "start_time": "2020-10-17T11:13:10.520216Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 1)\n",
      "(0, 2)\n",
      "(0, 3)\n",
      "(0, 4)\n",
      "(1, 2)\n",
      "(1, 3)\n",
      "(1, 4)\n",
      "(2, 3)\n",
      "(2, 4)\n",
      "(3, 4)\n"
     ]
    }
   ],
   "source": [
    "prime = 56003\n",
    "nb_digit_prime = len(str(prime))\n",
    "nb_replacements = 2\n",
    "for c in itertools.combinations(range(nb_digit_prime), nb_replacements):\n",
    "    print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-17T11:45:19.408110Z",
     "start_time": "2020-10-17T11:45:19.389618Z"
    }
   },
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "def find_prime_digit_replacements(max_size_family: int=6, primes: List[int]=primes_upto_10million) -> int:\n",
    "    set_primes = set(primes)\n",
    "    # we explore this list of primes in ascending order,\n",
    "    # so we'll find the smallest that satisfy the property\n",
    "    # for prime in primes:\n",
    "    for prime in range(10, max(primes) + 1):\n",
    "        str_prime = str(prime)\n",
    "        # for this prime, try all the possibilities\n",
    "        nb_digit_prime = len(str_prime)\n",
    "        for nb_replacements in range(1, nb_digit_prime + 1):  # cannot replace all the digits\n",
    "            # now try to replace nb_replacements digits (not necessarily adjacent)\n",
    "            for positions in itertools.combinations(range(nb_digit_prime), nb_replacements):\n",
    "                size_family = 0\n",
    "                good_digits = []\n",
    "                good_primes = []\n",
    "                for new_digit in range(0, 9 + 1):\n",
    "                    if positions[0] == 0 and new_digit == 0:\n",
    "                        continue\n",
    "                    new_prime = int(''.join(\n",
    "                        (c if i not in positions else str(new_digit))\n",
    "                        for i,c in enumerate(str_prime)\n",
    "                    ))\n",
    "                    if new_prime in set_primes:\n",
    "                        size_family += 1\n",
    "                        good_digits.append(new_digit)\n",
    "                        good_primes.append(new_prime)\n",
    "                if size_family >= max_size_family:\n",
    "                    print(f\"For p = {prime} with {nb_digit_prime} digits, and {nb_replacements} replacement(s), we found\")\n",
    "                    print(f\"a family of {size_family} prime(s) when replacing digit(s) at position(s) {positions}\")\n",
    "                    for new_digit, new_prime in zip(good_digits, good_primes):\n",
    "                        print(f\"    {new_prime} obtained by replacing with digit {new_digit}\")\n",
    "                    return prime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-17T11:45:22.004792Z",
     "start_time": "2020-10-17T11:45:21.942077Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For p = 13 with 2 digits, and 1 replacement(s), we found\n",
      "a family of 6 prime(s) when replacing digit(s) at position(s) (0,)\n",
      "    13 obtained by replacing with digit 1\n",
      "    23 obtained by replacing with digit 2\n",
      "    43 obtained by replacing with digit 4\n",
      "    53 obtained by replacing with digit 5\n",
      "    73 obtained by replacing with digit 7\n",
      "    83 obtained by replacing with digit 8\n",
      "CPU times: user 57.2 ms, sys: 24 µs, total: 57.2 ms\n",
      "Wall time: 56.1 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "find_prime_digit_replacements(max_size_family=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-17T11:45:45.406385Z",
     "start_time": "2020-10-17T11:45:23.262206Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For p = 56003 with 5 digits, and 2 replacement(s), we found\n",
      "a family of 7 prime(s) when replacing digit(s) at position(s) (2, 3)\n",
      "    56003 obtained by replacing with digit 0\n",
      "    56113 obtained by replacing with digit 1\n",
      "    56333 obtained by replacing with digit 3\n",
      "    56443 obtained by replacing with digit 4\n",
      "    56663 obtained by replacing with digit 6\n",
      "    56773 obtained by replacing with digit 7\n",
      "    56993 obtained by replacing with digit 9\n",
      "CPU times: user 22.1 s, sys: 17.7 ms, total: 22.1 s\n",
      "Wall time: 22.1 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "56003"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "find_prime_digit_replacements(max_size_family=7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-17T11:47:00.408383Z",
     "start_time": "2020-10-17T11:46:02.519766Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For p = 120303 with 6 digits, and 3 replacement(s), we found\n",
      "a family of 8 prime(s) when replacing digit(s) at position(s) (0, 2, 4)\n",
      "    121313 obtained by replacing with digit 1\n",
      "    222323 obtained by replacing with digit 2\n",
      "    323333 obtained by replacing with digit 3\n",
      "    424343 obtained by replacing with digit 4\n",
      "    525353 obtained by replacing with digit 5\n",
      "    626363 obtained by replacing with digit 6\n",
      "    828383 obtained by replacing with digit 8\n",
      "    929393 obtained by replacing with digit 9\n",
      "CPU times: user 57.9 s, sys: 0 ns, total: 57.9 s\n",
      "Wall time: 57.9 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "120303"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "find_prime_digit_replacements(max_size_family=8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Done!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [Problem 52: Permuted multiples](https://projecteuler.net/problem=52)\n",
    "It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.\n",
    "\n",
    "*Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T12:09:28.413003Z",
     "start_time": "2020-10-16T12:09:28.399814Z"
    }
   },
   "outputs": [],
   "source": [
    "def x_to_kx_contain_same_digits(x: int, kmax: int) -> bool:\n",
    "    digits_x = sorted(list(str(x)))\n",
    "    for k in range(2, kmax+1):\n",
    "        digits_kx = sorted(list(str(k*x)))\n",
    "        if digits_x != digits_kx:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T12:09:55.281567Z",
     "start_time": "2020-10-16T12:09:55.271069Z"
    }
   },
   "outputs": [],
   "source": [
    "assert not x_to_kx_contain_same_digits(125873, 2)\n",
    "assert x_to_kx_contain_same_digits(125874, 2)\n",
    "assert not x_to_kx_contain_same_digits(125875, 2)\n",
    "assert not x_to_kx_contain_same_digits(125874, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T12:12:40.555999Z",
     "start_time": "2020-10-16T12:12:40.545785Z"
    }
   },
   "outputs": [],
   "source": [
    "def find_smallest_x_such_that_x_to_6x_contain_same_digits(kmax: int=6) -> int:\n",
    "    x = 1\n",
    "    while True:\n",
    "        if x_to_kx_contain_same_digits(x, kmax):\n",
    "            print(f\"Found a solution x = {x}, proof:\")\n",
    "            for k in range(1, kmax + 1):\n",
    "                print(f\"    k x = {k}*{x}={k*x}\")\n",
    "            return x\n",
    "        x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T12:12:43.358750Z",
     "start_time": "2020-10-16T12:12:42.995893Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found a solution x = 142857, proof:\n",
      "    k x = 1*142857=142857\n",
      "    k x = 2*142857=285714\n",
      "    k x = 3*142857=428571\n",
      "    k x = 4*142857=571428\n",
      "    k x = 5*142857=714285\n",
      "    k x = 6*142857=857142\n",
      "CPU times: user 357 ms, sys: 76 µs, total: 357 ms\n",
      "Wall time: 356 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "142857"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "find_smallest_x_such_that_x_to_6x_contain_same_digits()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Done, it was quick."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [Problem 53: Combinatoric selections](https://projecteuler.net/problem=53)\n",
    "\n",
    "There are exactly ten ways of selecting three from five, 12345: 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345.\n",
    "\n",
    "In combinatorics, we use the notation, ${5 \\choose 3} = 10$.\n",
    "In general, $${n \\choose r} = \\frac{n!}{r! (n-r)!}$$\n",
    "\n",
    "It is not until $n=23$, that a value exceeds one-million: ${23 \\choose 10} = 1144066$.\n",
    "\n",
    "*How many, not necessarily distinct, values of ${n \\choose r}$ for $1 \\leq n \\leq 100$, are greater than one-million?*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T11:17:24.770636Z",
     "start_time": "2020-10-16T11:17:24.765196Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Cython extension is already loaded. To reload it, use:\n",
      "  %reload_ext Cython\n"
     ]
    }
   ],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T11:45:18.876238Z",
     "start_time": "2020-10-16T11:45:18.008365Z"
    }
   },
   "outputs": [],
   "source": [
    "%%cython\n",
    "\n",
    "def 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T11:45:24.056207Z",
     "start_time": "2020-10-16T11:45:24.039040Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1144066"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "choose_kn(10, 23)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T12:06:18.584843Z",
     "start_time": "2020-10-16T12:06:18.569350Z"
    }
   },
   "outputs": [],
   "source": [
    "def how_many_choose_kn_are_greater_than_x(max_n: int, x: int) -> int:\n",
    "    count = 0\n",
    "    for n in range(1, max_n + 1):\n",
    "        for k in range(1, n//2 + 1):\n",
    "            c_kn = choose_kn(k, n)\n",
    "            if c_kn > x:\n",
    "                count += 1\n",
    "                if n-k != k:\n",
    "                    # we count twice for (n choose k) and (n choose n-k)\n",
    "                    # only if n-k != k\n",
    "                    count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-10-16T12:06:21.066295Z",
     "start_time": "2020-10-16T12:06:21.024065Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4075"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "how_many_choose_kn_are_greater_than_x(100, 1e6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was quite easy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [Problem 54: ](https://projecteuler.net/problem=54)\n",
    "\n",
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## [Problem 55: ](https://projecteuler.net/problem=55)\n",
    "\n",
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Continue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "283.6px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}