{ "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 in February 2015, and worked occasionally on Project Euler problems in March and April 2015.\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?h \"Badge giving the number of solved problems\")" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "---\n", "## [Problem 12 : Highly divisible triangular number](https://projecteuler.net/problem=12)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:23:50.355809Z", "start_time": "2020-10-13T13:23:49.916028Z" } }, "outputs": [], "source": [ "%load_ext Cython" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:23:50.813947Z", "start_time": "2020-10-13T13:23:50.810013Z" } }, "outputs": [], "source": [ "from typing import List" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:23:51.061823Z", "start_time": "2020-10-13T13:23:51.056472Z" } }, "outputs": [], "source": [ "def divisors(n: int) -> List[int]:\n", " return [k for k in range(1, n+1) if n%k == 0]" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:23:51.458315Z", "start_time": "2020-10-13T13:23:51.443096Z" } }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 4, 7, 14, 28]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "divisors(28)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:23:55.161520Z", "start_time": "2020-10-13T13:23:55.152858Z" } }, "outputs": [], "source": [ "def number_of_divisors(n: int) -> int:\n", " return len(divisors(n))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:23:59.014506Z", "start_time": "2020-10-13T13:23:59.010607Z" } }, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "number_of_divisors(28)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:27:47.676815Z", "start_time": "2020-10-13T13:27:47.666262Z" } }, "outputs": [], "source": [ "def int_sqrt(n: int) -> int:\n", " if n <= 0: return 0\n", " if n == 1: return 1\n", " i = 0\n", " while i*i <= n:\n", " i += 1\n", " if i*i == n: return i\n", " return i-1" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:27:47.981791Z", "start_time": "2020-10-13T13:27:47.907710Z" } }, "outputs": [], "source": [ "import math\n", "for i in range(10000):\n", " assert int_sqrt(i) == math.floor(math.sqrt(i)), f\"{i}\"" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:27:48.131074Z", "start_time": "2020-10-13T13:27:48.127587Z" } }, "outputs": [], "source": [ "def number_of_divisors2(n: int) -> int:\n", " c = 0\n", " for k in range(1, n+1):\n", " if n%k == 0:\n", " c += 1\n", " return c" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:27:48.349530Z", "start_time": "2020-10-13T13:27:48.303472Z" } }, "outputs": [], "source": [ "for n in range(1000):\n", " assert number_of_divisors(n) == number_of_divisors2(n)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:28:54.039244Z", "start_time": "2020-10-13T13:28:54.027156Z" } }, "outputs": [], "source": [ "def number_of_divisors3(n: int) -> int:\n", " if n <= 0: return 0\n", " if n == 1: return 1\n", " c = 0\n", " for k in range(1, int_sqrt(n)+1):\n", " # print(f\"n = {n}, k = {k}, c = {c}\")\n", " if n%k == 0:\n", " c += 1 if k*k == n else 2\n", " return c" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:29:30.499386Z", "start_time": "2020-10-13T13:29:11.308794Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "45.7 ms ± 585 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n", "52.6 ms ± 1.22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n", "138 µs ± 1.49 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n" ] } ], "source": [ "%timeit number_of_divisors(1000000)\n", "%timeit number_of_divisors2(1000000)\n", "%timeit number_of_divisors3(1000000)" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:28:54.305768Z", "start_time": "2020-10-13T13:28:54.274594Z" } }, "outputs": [], "source": [ "for n in range(1000):\n", " assert number_of_divisors(n) == number_of_divisors3(n), f\"{n}\"" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:16.830158Z", "start_time": "2020-10-13T13:31:16.408378Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " Cython: _cython_magic_b421ed9aa342829a2e7bf32576065354.pyx\n", " \n", "\n", "\n", "

Generated by Cython 0.29.21

\n", "

\n", " Yellow lines hint at Python interaction.
\n", " Click on a line that starts with a \"+\" to see the C code that Cython generated for it.\n", "

\n", "
 01: 
\n", "
+02: cdef int int_sqrt(int n):
\n", "
static int __pyx_f_46_cython_magic_b421ed9aa342829a2e7bf32576065354_int_sqrt(int __pyx_v_n) {\n",
       "  int __pyx_v_i;\n",
       "  int __pyx_r;\n",
       "  __Pyx_RefNannyDeclarations\n",
       "  __Pyx_RefNannySetupContext(\"int_sqrt\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L0:;\n",
       "  __Pyx_RefNannyFinishContext();\n",
       "  return __pyx_r;\n",
       "}\n",
       "
+03:     if n <= 0: return 0
\n", "
  __pyx_t_1 = ((__pyx_v_n <= 0) != 0);\n",
       "  if (__pyx_t_1) {\n",
       "    __pyx_r = 0;\n",
       "    goto __pyx_L0;\n",
       "  }\n",
       "
+04:     elif n == 1: return 1
\n", "
  __pyx_t_1 = ((__pyx_v_n == 1) != 0);\n",
       "  if (__pyx_t_1) {\n",
       "    __pyx_r = 1;\n",
       "    goto __pyx_L0;\n",
       "  }\n",
       "
+05:     cdef int i = 0
\n", "
  __pyx_v_i = 0;\n",
       "
+06:     while i*i <= n:
\n", "
  while (1) {\n",
       "    __pyx_t_1 = (((__pyx_v_i * __pyx_v_i) <= __pyx_v_n) != 0);\n",
       "    if (!__pyx_t_1) break;\n",
       "
+07:         i += 1
\n", "
    __pyx_v_i = (__pyx_v_i + 1);\n",
       "
+08:         if i*i == n: return i
\n", "
    __pyx_t_1 = (((__pyx_v_i * __pyx_v_i) == __pyx_v_n) != 0);\n",
       "    if (__pyx_t_1) {\n",
       "      __pyx_r = __pyx_v_i;\n",
       "      goto __pyx_L0;\n",
       "    }\n",
       "  }\n",
       "
+09:     return i-1
\n", "
  __pyx_r = (__pyx_v_i - 1);\n",
       "  goto __pyx_L0;\n",
       "
 10: 
\n", "
+11: cdef int number_of_divisors(int n):
\n", "
static int __pyx_f_46_cython_magic_b421ed9aa342829a2e7bf32576065354_number_of_divisors(int __pyx_v_n) {\n",
       "  int __pyx_v_c;\n",
       "  PyObject *__pyx_v_k = NULL;\n",
       "  int __pyx_r;\n",
       "  __Pyx_RefNannyDeclarations\n",
       "  __Pyx_RefNannySetupContext(\"number_of_divisors\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  __Pyx_XDECREF(__pyx_t_2);\n",
       "  __Pyx_XDECREF(__pyx_t_3);\n",
       "  __Pyx_XDECREF(__pyx_t_6);\n",
       "  __Pyx_XDECREF(__pyx_t_8);\n",
       "  __Pyx_WriteUnraisable(\"_cython_magic_b421ed9aa342829a2e7bf32576065354.number_of_divisors\", __pyx_clineno, __pyx_lineno, __pyx_filename, 1, 0);\n",
       "  __pyx_r = 0;\n",
       "  __pyx_L0:;\n",
       "  __Pyx_XDECREF(__pyx_v_k);\n",
       "  __Pyx_RefNannyFinishContext();\n",
       "  return __pyx_r;\n",
       "}\n",
       "
+12:     if n <= 0: return 0
\n", "
  __pyx_t_1 = ((__pyx_v_n <= 0) != 0);\n",
       "  if (__pyx_t_1) {\n",
       "    __pyx_r = 0;\n",
       "    goto __pyx_L0;\n",
       "  }\n",
       "
+13:     elif n == 1: return 1
\n", "
  __pyx_t_1 = ((__pyx_v_n == 1) != 0);\n",
       "  if (__pyx_t_1) {\n",
       "    __pyx_r = 1;\n",
       "    goto __pyx_L0;\n",
       "  }\n",
       "
+14:     cdef int c = 0
\n", "
  __pyx_v_c = 0;\n",
       "
+15:     for k in range(1, int_sqrt(n)+1):
\n", "
  __pyx_t_2 = __Pyx_PyInt_From_long((__pyx_f_46_cython_magic_b421ed9aa342829a2e7bf32576065354_int_sqrt(__pyx_v_n) + 1)); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  __Pyx_GOTREF(__pyx_t_2);\n",
       "  __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  __Pyx_GOTREF(__pyx_t_3);\n",
       "  __Pyx_INCREF(__pyx_int_1);\n",
       "  __Pyx_GIVEREF(__pyx_int_1);\n",
       "  PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_int_1);\n",
       "  __Pyx_GIVEREF(__pyx_t_2);\n",
       "  PyTuple_SET_ITEM(__pyx_t_3, 1, __pyx_t_2);\n",
       "  __pyx_t_2 = 0;\n",
       "  __pyx_t_2 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_3, NULL); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  __Pyx_GOTREF(__pyx_t_2);\n",
       "  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n",
       "  if (likely(PyList_CheckExact(__pyx_t_2)) || PyTuple_CheckExact(__pyx_t_2)) {\n",
       "    __pyx_t_3 = __pyx_t_2; __Pyx_INCREF(__pyx_t_3); __pyx_t_4 = 0;\n",
       "    __pyx_t_5 = NULL;\n",
       "  } else {\n",
       "    __pyx_t_4 = -1; __pyx_t_3 = PyObject_GetIter(__pyx_t_2); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "    __Pyx_GOTREF(__pyx_t_3);\n",
       "    __pyx_t_5 = Py_TYPE(__pyx_t_3)->tp_iternext; if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "  }\n",
       "  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;\n",
       "  for (;;) {\n",
       "    if (likely(!__pyx_t_5)) {\n",
       "      if (likely(PyList_CheckExact(__pyx_t_3))) {\n",
       "        if (__pyx_t_4 >= PyList_GET_SIZE(__pyx_t_3)) break;\n",
       "        #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS\n",
       "        __pyx_t_2 = PyList_GET_ITEM(__pyx_t_3, __pyx_t_4); __Pyx_INCREF(__pyx_t_2); __pyx_t_4++; if (unlikely(0 < 0)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "        #else\n",
       "        __pyx_t_2 = PySequence_ITEM(__pyx_t_3, __pyx_t_4); __pyx_t_4++; if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "        __Pyx_GOTREF(__pyx_t_2);\n",
       "        #endif\n",
       "      } else {\n",
       "        if (__pyx_t_4 >= PyTuple_GET_SIZE(__pyx_t_3)) break;\n",
       "        #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS\n",
       "        __pyx_t_2 = PyTuple_GET_ITEM(__pyx_t_3, __pyx_t_4); __Pyx_INCREF(__pyx_t_2); __pyx_t_4++; if (unlikely(0 < 0)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "        #else\n",
       "        __pyx_t_2 = PySequence_ITEM(__pyx_t_3, __pyx_t_4); __pyx_t_4++; if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "        __Pyx_GOTREF(__pyx_t_2);\n",
       "        #endif\n",
       "      }\n",
       "    } else {\n",
       "      __pyx_t_2 = __pyx_t_5(__pyx_t_3);\n",
       "      if (unlikely(!__pyx_t_2)) {\n",
       "        PyObject* exc_type = PyErr_Occurred();\n",
       "        if (exc_type) {\n",
       "          if (likely(__Pyx_PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();\n",
       "          else __PYX_ERR(0, 15, __pyx_L1_error)\n",
       "        }\n",
       "        break;\n",
       "      }\n",
       "      __Pyx_GOTREF(__pyx_t_2);\n",
       "    }\n",
       "    __Pyx_XDECREF_SET(__pyx_v_k, __pyx_t_2);\n",
       "    __pyx_t_2 = 0;\n",
       "/* … */\n",
       "  }\n",
       "  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n",
       "
 16:         # print(f"n = {n}, k = {k}, c = {c}")
\n", "
+17:         if n%k == 0:
\n", "
    __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_n); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 17, __pyx_L1_error)\n",
       "    __Pyx_GOTREF(__pyx_t_2);\n",
       "    __pyx_t_6 = PyNumber_Remainder(__pyx_t_2, __pyx_v_k); if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 17, __pyx_L1_error)\n",
       "    __Pyx_GOTREF(__pyx_t_6);\n",
       "    __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;\n",
       "    __pyx_t_2 = __Pyx_PyInt_EqObjC(__pyx_t_6, __pyx_int_0, 0, 0); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 17, __pyx_L1_error)\n",
       "    __Pyx_GOTREF(__pyx_t_2);\n",
       "    __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;\n",
       "    __pyx_t_1 = __Pyx_PyObject_IsTrue(__pyx_t_2); if (unlikely(__pyx_t_1 < 0)) __PYX_ERR(0, 17, __pyx_L1_error)\n",
       "    __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;\n",
       "    if (__pyx_t_1) {\n",
       "/* … */\n",
       "    }\n",
       "
+18:             c += 1 if k*k == n else 2
\n", "
      __pyx_t_2 = PyNumber_Multiply(__pyx_v_k, __pyx_v_k); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 18, __pyx_L1_error)\n",
       "      __Pyx_GOTREF(__pyx_t_2);\n",
       "      __pyx_t_6 = __Pyx_PyInt_From_int(__pyx_v_n); if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 18, __pyx_L1_error)\n",
       "      __Pyx_GOTREF(__pyx_t_6);\n",
       "      __pyx_t_8 = PyObject_RichCompare(__pyx_t_2, __pyx_t_6, Py_EQ); __Pyx_XGOTREF(__pyx_t_8); if (unlikely(!__pyx_t_8)) __PYX_ERR(0, 18, __pyx_L1_error)\n",
       "      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;\n",
       "      __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;\n",
       "      __pyx_t_1 = __Pyx_PyObject_IsTrue(__pyx_t_8); if (unlikely(__pyx_t_1 < 0)) __PYX_ERR(0, 18, __pyx_L1_error)\n",
       "      __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0;\n",
       "      if (__pyx_t_1) {\n",
       "        __pyx_t_7 = 1;\n",
       "      } else {\n",
       "        __pyx_t_7 = 2;\n",
       "      }\n",
       "      __pyx_v_c = (__pyx_v_c + __pyx_t_7);\n",
       "
+19:     return c
\n", "
  __pyx_r = __pyx_v_c;\n",
       "  goto __pyx_L0;\n",
       "
 20: 
\n", "
+21: def first_highly_divisible_triangular_number(int nb_of_divisors=5):
\n", "
/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_b421ed9aa342829a2e7bf32576065354_1first_highly_divisible_triangular_number(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static PyMethodDef __pyx_mdef_46_cython_magic_b421ed9aa342829a2e7bf32576065354_1first_highly_divisible_triangular_number = {\"first_highly_divisible_triangular_number\", (PyCFunction)(void*)(PyCFunctionWithKeywords)__pyx_pw_46_cython_magic_b421ed9aa342829a2e7bf32576065354_1first_highly_divisible_triangular_number, METH_VARARGS|METH_KEYWORDS, 0};\n",
       "static PyObject *__pyx_pw_46_cython_magic_b421ed9aa342829a2e7bf32576065354_1first_highly_divisible_triangular_number(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {\n",
       "  int __pyx_v_nb_of_divisors;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  __Pyx_RefNannyDeclarations\n",
       "  __Pyx_RefNannySetupContext(\"first_highly_divisible_triangular_number (wrapper)\", 0);\n",
       "  {\n",
       "    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_nb_of_divisors,0};\n",
       "    PyObject* values[1] = {0};\n",
       "    if (unlikely(__pyx_kwds)) {\n",
       "      Py_ssize_t kw_args;\n",
       "      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);\n",
       "      switch (pos_args) {\n",
       "        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  0: break;\n",
       "        default: goto __pyx_L5_argtuple_error;\n",
       "      }\n",
       "      kw_args = PyDict_Size(__pyx_kwds);\n",
       "      switch (pos_args) {\n",
       "        case  0:\n",
       "        if (kw_args > 0) {\n",
       "          PyObject* value = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_nb_of_divisors);\n",
       "          if (value) { values[0] = value; kw_args--; }\n",
       "        }\n",
       "      }\n",
       "      if (unlikely(kw_args > 0)) {\n",
       "        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, \"first_highly_divisible_triangular_number\") < 0)) __PYX_ERR(0, 21, __pyx_L3_error)\n",
       "      }\n",
       "    } else {\n",
       "      switch (PyTuple_GET_SIZE(__pyx_args)) {\n",
       "        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  0: break;\n",
       "        default: goto __pyx_L5_argtuple_error;\n",
       "      }\n",
       "    }\n",
       "    if (values[0]) {\n",
       "      __pyx_v_nb_of_divisors = __Pyx_PyInt_As_int(values[0]); if (unlikely((__pyx_v_nb_of_divisors == (int)-1) && PyErr_Occurred())) __PYX_ERR(0, 21, __pyx_L3_error)\n",
       "    } else {\n",
       "      __pyx_v_nb_of_divisors = ((int)5);\n",
       "    }\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L5_argtuple_error:;\n",
       "  __Pyx_RaiseArgtupleInvalid(\"first_highly_divisible_triangular_number\", 0, 0, 1, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 21, __pyx_L3_error)\n",
       "  __pyx_L3_error:;\n",
       "  __Pyx_AddTraceback(\"_cython_magic_b421ed9aa342829a2e7bf32576065354.first_highly_divisible_triangular_number\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __Pyx_RefNannyFinishContext();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_b421ed9aa342829a2e7bf32576065354_first_highly_divisible_triangular_number(__pyx_self, __pyx_v_nb_of_divisors);\n",
       "  int __pyx_lineno = 0;\n",
       "  const char *__pyx_filename = NULL;\n",
       "  int __pyx_clineno = 0;\n",
       "\n",
       "  /* function exit code */\n",
       "  __Pyx_RefNannyFinishContext();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_b421ed9aa342829a2e7bf32576065354_first_highly_divisible_triangular_number(CYTHON_UNUSED PyObject *__pyx_self, int __pyx_v_nb_of_divisors) {\n",
       "  int __pyx_v_triangular_number;\n",
       "  int __pyx_v_i;\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  __Pyx_RefNannyDeclarations\n",
       "  __Pyx_RefNannySetupContext(\"first_highly_divisible_triangular_number\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  __Pyx_XDECREF(__pyx_t_2);\n",
       "  __Pyx_AddTraceback(\"_cython_magic_b421ed9aa342829a2e7bf32576065354.first_highly_divisible_triangular_number\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  __Pyx_XGIVEREF(__pyx_r);\n",
       "  __Pyx_RefNannyFinishContext();\n",
       "  return __pyx_r;\n",
       "}\n",
       "/* … */\n",
       "  __pyx_tuple_ = PyTuple_Pack(3, __pyx_n_s_nb_of_divisors, __pyx_n_s_triangular_number, __pyx_n_s_i); if (unlikely(!__pyx_tuple_)) __PYX_ERR(0, 21, __pyx_L1_error)\n",
       "  __Pyx_GOTREF(__pyx_tuple_);\n",
       "  __Pyx_GIVEREF(__pyx_tuple_);\n",
       "/* … */\n",
       "  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_b421ed9aa342829a2e7bf32576065354_1first_highly_divisible_triangular_number, NULL, __pyx_n_s_cython_magic_b421ed9aa342829a2e); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 21, __pyx_L1_error)\n",
       "  __Pyx_GOTREF(__pyx_t_1);\n",
       "  if (PyDict_SetItem(__pyx_d, __pyx_n_s_first_highly_divisible_triangula, __pyx_t_1) < 0) __PYX_ERR(0, 21, __pyx_L1_error)\n",
       "  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;\n",
       "
+22:     cdef int triangular_number = 1
\n", "
  __pyx_v_triangular_number = 1;\n",
       "
+23:     cdef int i = 2
\n", "
  __pyx_v_i = 2;\n",
       "
+24:     while number_of_divisors(triangular_number) < nb_of_divisors:
\n", "
  while (1) {\n",
       "    __pyx_t_1 = ((__pyx_f_46_cython_magic_b421ed9aa342829a2e7bf32576065354_number_of_divisors(__pyx_v_triangular_number) < __pyx_v_nb_of_divisors) != 0);\n",
       "    if (!__pyx_t_1) break;\n",
       "
+25:         triangular_number += i
\n", "
    __pyx_v_triangular_number = (__pyx_v_triangular_number + __pyx_v_i);\n",
       "
+26:         i += 1
\n", "
    __pyx_v_i = (__pyx_v_i + 1);\n",
       "  }\n",
       "
+27:     return triangular_number
\n", "
  __Pyx_XDECREF(__pyx_r);\n",
       "  __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_triangular_number); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 27, __pyx_L1_error)\n",
       "  __Pyx_GOTREF(__pyx_t_2);\n",
       "  __pyx_r = __pyx_t_2;\n",
       "  __pyx_t_2 = 0;\n",
       "  goto __pyx_L0;\n",
       "
" ], "text/plain": [ "" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%cython -a\n", "\n", "cdef int int_sqrt(int n):\n", " if n <= 0: return 0\n", " elif n == 1: return 1\n", " cdef int i = 0\n", " while i*i <= n:\n", " i += 1\n", " if i*i == n: return i\n", " return i-1\n", "\n", "cdef int number_of_divisors(int n):\n", " if n <= 0: return 0\n", " elif n == 1: return 1\n", " cdef int c = 0\n", " for k in range(1, int_sqrt(n)+1):\n", " # print(f\"n = {n}, k = {k}, c = {c}\")\n", " if n%k == 0:\n", " c += 1 if k*k == n else 2\n", " return c\n", "\n", "def first_highly_divisible_triangular_number(int nb_of_divisors=5):\n", " cdef int triangular_number = 1\n", " cdef int i = 2\n", " while number_of_divisors(triangular_number) < nb_of_divisors:\n", " triangular_number += i\n", " i += 1\n", " return triangular_number" ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:34.047159Z", "start_time": "2020-10-13T13:31:34.042770Z" } }, "outputs": [ { "data": { "text/plain": [ "28" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(5)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:35.022158Z", "start_time": "2020-10-13T13:31:34.984775Z" } }, "outputs": [ { "data": { "text/plain": [ "749700" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(150)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:36.154452Z", "start_time": "2020-10-13T13:31:36.069503Z" } }, "outputs": [ { "data": { "text/plain": [ "2031120" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(200)" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:38.727546Z", "start_time": "2020-10-13T13:31:38.650004Z" } }, "outputs": [ { "data": { "text/plain": [ "2162160" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(250)" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:39.730018Z", "start_time": "2020-10-13T13:31:39.639065Z" } }, "outputs": [ { "data": { "text/plain": [ "2162160" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(300)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:40.904913Z", "start_time": "2020-10-13T13:31:40.316522Z" } }, "outputs": [ { "data": { "text/plain": [ "17907120" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(350)" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:42.606304Z", "start_time": "2020-10-13T13:31:42.023299Z" } }, "outputs": [ { "data": { "text/plain": [ "17907120" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(400)" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:43.642124Z", "start_time": "2020-10-13T13:31:43.063015Z" } }, "outputs": [ { "data": { "text/plain": [ "17907120" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(450)" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:31:47.489599Z", "start_time": "2020-10-13T13:31:45.057586Z" } }, "outputs": [ { "data": { "text/plain": [ "76576500" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first_highly_divisible_triangular_number(500)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That's slow if you test for divisors until n, but using this $\\lfloor \\sqrt{n} \\rfloor$ trick speeds it up!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 19: Counting Sundays](https://projecteuler.net/problem=19)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:28:37.164133Z", "start_time": "2020-10-13T12:28:37.157399Z" } }, "outputs": [], "source": [ "from datetime import date, timedelta" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:28:37.634837Z", "start_time": "2020-10-13T12:28:37.628947Z" } }, "outputs": [], "source": [ "def isSunday(current_date: date) -> bool:\n", " current_iso_date = current_date.isocalendar()\n", " weekday = current_iso_date[2]\n", " return weekday == 7" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:28:38.094044Z", "start_time": "2020-10-13T12:28:38.069973Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Between 1901-01-01 and 2000-12-31, there were 171 Sundays happening the first day of a month.\n" ] } ], "source": [ "start_date = date(year=1901, month=1, day=1)\n", "current_date = start_date\n", "tomorrow = timedelta(days=+1)\n", "max_date = date(year=2000, month=12, day=31)\n", "number_of_sundays = 0\n", "\n", "while current_date <= max_date:\n", " if current_date.day == 1:\n", " if isSunday(current_date):\n", " number_of_sundays += 1\n", " current_date += tomorrow\n", "\n", "print(f\"Between {start_date} and {max_date}, there were {number_of_sundays} Sundays happening the first day of a month.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "==> 171" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 26: Reciprocal cycles](https://projecteuler.net/problem=36) TODO" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:45:33.227422Z", "start_time": "2020-10-13T12:45:33.224352Z" } }, "outputs": [], "source": [ "import decimal\n", "D = decimal.Decimal" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try with 1000 digits, and I'll just increase it if the solution is not good." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:45:42.185140Z", "start_time": "2020-10-13T12:45:42.182992Z" } }, "outputs": [], "source": [ "decimal.getcontext().prec = 1000" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Example:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:45:42.885763Z", "start_time": "2020-10-13T12:45:42.874858Z" } }, "outputs": [ { "data": { "text/plain": [ "Decimal('0.1428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571429')" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D('1') / D('7')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How to detect a cycle and its length:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:55:46.482473Z", "start_time": "2020-10-13T12:55:46.468274Z" } }, "outputs": [], "source": [ "def detect_cycle_length_str_offset(s: str, offset: int=0) -> int:\n", " s = s[offset:]\n", " length = 1\n", " n = len(s)\n", " cycle = s[:length]\n", " while length < n:\n", " cut_size = n//length\n", " if s[:cut_size * length] == cycle * cut_size:\n", " return length\n", " cycle += s[length]\n", " length += 1\n", " return 0" ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:55:46.482473Z", "start_time": "2020-10-13T12:55:46.468274Z" } }, "outputs": [], "source": [ "def detect_cycle_length_str(s: str, offset: int=0) -> int:\n", " s = s[offset:]\n", " length = 1\n", " n = len(s)\n", " cycle = s[:length]\n", " while length < n:\n", " cut_size = n//length\n", " if s[:cut_size * length] == cycle * cut_size:\n", " return length\n", " cycle += s[length]\n", " length += 1\n", " return 0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 50, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:55:46.968277Z", "start_time": "2020-10-13T12:55:46.960295Z" } }, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "detect_cycle_length_str('1428571428571428571428571429')\n", "# '142857' is a cycle so ==> 6" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:55:25.974379Z", "start_time": "2020-10-13T12:55:25.961760Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "offset = 0\n", "length = 1\n", "cut_size = 19\n", "s[offset : offset + cut_size * length] = 1666666666666666666\n", "cycle * cut_size = 1111111111111111111\n", "\n", "offset = 0\n", "length = 2\n", "cut_size = 9\n", "s[offset : offset + cut_size * length] = 166666666666666666\n", "cycle * cut_size = 161616161616161616\n", "\n", "offset = 0\n", "length = 3\n", "cut_size = 6\n", "s[offset : offset + cut_size * length] = 166666666666666666\n", "cycle * cut_size = 166166166166166166\n", "\n", "offset = 0\n", "length = 4\n", "cut_size = 4\n", "s[offset : offset + cut_size * length] = 1666666666666666\n", "cycle * cut_size = 1666166616661666\n", "\n", "offset = 0\n", "length = 5\n", "cut_size = 3\n", "s[offset : offset + cut_size * length] = 166666666666666\n", "cycle * cut_size = 166661666616666\n", "\n", "offset = 0\n", "length = 6\n", "cut_size = 3\n", "s[offset : offset + cut_size * length] = 166666666666666666\n", "cycle * cut_size = 166666166666166666\n", "\n", "offset = 0\n", "length = 7\n", "cut_size = 2\n", "s[offset : offset + cut_size * length] = 16666666666666\n", "cycle * cut_size = 16666661666666\n", "\n", "offset = 0\n", "length = 8\n", "cut_size = 2\n", "s[offset : offset + cut_size * length] = 1666666666666666\n", "cycle * cut_size = 1666666616666666\n", "\n", "offset = 0\n", "length = 9\n", "cut_size = 2\n", "s[offset : offset + cut_size * length] = 166666666666666666\n", "cycle * cut_size = 166666666166666666\n", "\n", "offset = 0\n", "length = 10\n", "cut_size = 1\n", "s[offset : offset + cut_size * length] = 1666666666\n", "cycle * cut_size = 1666666666\n", "10\n", "\n", "offset = 1\n", "length = 1\n", "cut_size = 18\n", "s[offset : offset + cut_size * length] = 666666666666666666\n", "cycle * cut_size = 666666666666666666\n", "1\n" ] } ], "source": [ "print(detect_cycle_length_str('1666666666666666666', offset=0))\n", "print(detect_cycle_length_str('1666666666666666666', offset=1))" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:48:55.464598Z", "start_time": "2020-10-13T12:48:55.453743Z" } }, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "detect_cycle_length_str('1428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571428571429')\n", "# '142857' is a cycle so ==> 6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How to detect a cycle in a decimal number of the form $\\frac{1}{d}$:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:45:58.085684Z", "start_time": "2020-10-13T12:45:58.081853Z" } }, "outputs": [], "source": [ "def detect_cycle_length(denominator: str, nominator: str='1') -> int:\n", " x = D(nominator) / D(denominator)\n", " s = str(x).split('.')[1]\n", " return detect_cycle_length_str(s)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:49:18.522314Z", "start_time": "2020-10-13T12:49:18.511531Z" } }, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "detect_cycle_length('7')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now it's easy to find a number with maximum cycle length:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:49:27.454747Z", "start_time": "2020-10-13T12:49:27.449975Z" } }, "outputs": [], "source": [ "def number_with_longest_cycle(start: int=2, end: int=1000) -> int:\n", " max_cycle_length = 0\n", " candidate_d = None\n", " for number in range(start, end):\n", " cycle_length = detect_cycle_length(str(number))\n", " if cycle_length > max_cycle_length:\n", " candidate_d = number\n", " max_cycle_length = cycle_length\n", " return candidate_d, max_cycle_length" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T12:49:27.906496Z", "start_time": "2020-10-13T12:49:27.899284Z" } }, "outputs": [ { "data": { "text/plain": [ "(6, 501)" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "number_with_longest_cycle(start=2, end=11)\n", "# ==> 7, 6 as 1/7 has a cycle length of 6" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "number_with_longest_cycle(start=1, end=100)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "number_with_longest_cycle(start=1, end=1000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I have not yet found a way to conclude. Working with strings and `decimal.Decimal` numbers is probably a wrong idea." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 32: Pandigital products](https://projecteuler.net/problem=32)" ] }, { "cell_type": "code", "execution_count": 223, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:46:35.134985Z", "start_time": "2020-10-13T20:46:35.128961Z" } }, "outputs": [ { "data": { "text/plain": [ "{'1', '2', '3', '4', '5'}" ] }, "execution_count": 223, "metadata": {}, "output_type": "execute_result" } ], "source": [ "set(str(15234))" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:55:29.591570Z", "start_time": "2020-10-13T13:55:29.580169Z" } }, "outputs": [ { "data": { "text/plain": [ "{'1', '2', '3', '4', '5'}" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "set(''.join(map(str, range(1, 5+1))))" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T13:55:29.879447Z", "start_time": "2020-10-13T13:55:29.875918Z" } }, "outputs": [], "source": [ "from typing import Union" ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T17:26:36.936261Z", "start_time": "2020-10-13T17:26:36.925641Z" } }, "outputs": [], "source": [ "def is_pandigital(n: Union[str, int], start: int=1, end: int=9):\n", " str_n = str(n)\n", " if len(str_n) != (end - start + 1):\n", " return False\n", " return set(str(n)) == set(''.join(map(str, range(start, end+1))))" ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T17:26:38.123849Z", "start_time": "2020-10-13T17:26:38.120259Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "False\n" ] } ], "source": [ "print(is_pandigital(15234, start=1, end=5)) # True\n", "print(is_pandigital(15234, start=1, end=9)) # False" ] }, { "cell_type": "code", "execution_count": 106, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:34.742544Z", "start_time": "2020-10-13T18:03:34.739055Z" } }, "outputs": [], "source": [ "set_1to9 = {1,2,3,4,5,6,7,8,9}\n", "\n", "def is_pandigital_1to9(n: Union[str, int]):\n", " str_n = str(n)\n", " if len(str_n) != 9:\n", " return False\n", " return ('0' not in str_n) and len(set(str_n)) == 9" ] }, { "cell_type": "code", "execution_count": 107, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:35.131118Z", "start_time": "2020-10-13T18:03:35.127142Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "False\n", "True\n" ] } ], "source": [ "print(is_pandigital_1to9(15234)) # False\n", "print(is_pandigital_1to9(152346987)) # False" ] }, { "cell_type": "code", "execution_count": 108, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.305977Z", "start_time": "2020-10-13T18:03:35.732453Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "179 ns ± 1.41 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n", "368 ns ± 3.05 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n" ] } ], "source": [ "%timeit f\"{39}{186}{7254}\"\n", "%timeit str(39) + str(186) + str(7254)" ] }, { "cell_type": "code", "execution_count": 109, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.319683Z", "start_time": "2020-10-13T18:03:53.316668Z" } }, "outputs": [], "source": [ "def are_pandigital(multiplicand: int, multiplier: int, product: int) -> bool:\n", " # assert multiplicand * multiplier == product\n", " n = f\"{multiplicand}{multiplier}{product}\"\n", " return is_pandigital_1to9(n)" ] }, { "cell_type": "code", "execution_count": 110, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.337564Z", "start_time": "2020-10-13T18:03:53.332279Z" } }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "are_pandigital(39, 186, 7254)" ] }, { "cell_type": "code", "execution_count": 111, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.357205Z", "start_time": "2020-10-13T18:03:53.354794Z" } }, "outputs": [], "source": [ "from typing import Tuple" ] }, { "cell_type": "code", "execution_count": 112, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.376161Z", "start_time": "2020-10-13T18:03:53.371561Z" } }, "outputs": [], "source": [ "def find_pandigital_products(n: int) -> Tuple[bool, Tuple[int, int]]:\n", " x = 2\n", " while x*x <= n:\n", " if n % x == 0:\n", " y = n // x\n", " if are_pandigital(x, y, n):\n", " return True, (x, y)\n", " x += 1\n", " return False, (None, None)" ] }, { "cell_type": "code", "execution_count": 113, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.395801Z", "start_time": "2020-10-13T18:03:53.391506Z" } }, "outputs": [ { "data": { "text/plain": [ "(True, (39, 186))" ] }, "execution_count": 113, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_pandigital_products(7254)" ] }, { "cell_type": "code", "execution_count": 114, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.419143Z", "start_time": "2020-10-13T18:03:53.414901Z" } }, "outputs": [], "source": [ "def all_pandigital_products(maxi=10000):\n", " return [n for n in range(1, maxi + 1) if find_pandigital_products(n)[0]]" ] }, { "cell_type": "code", "execution_count": 115, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.442611Z", "start_time": "2020-10-13T18:03:53.438103Z" } }, "outputs": [], "source": [ "def sum_of_all_pandigital_products(maxi=10000):\n", " s = 0\n", " for n in range(1, maxi + 1):\n", " b, (x, y) = find_pandigital_products(n)\n", " if b:\n", " print(f\"n = {n} is pandigital with x = {x} and y = {y}, and current sum = {s}...\")\n", " s += n\n", " return s\n", " # return sum(all_pandigital_products())" ] }, { "cell_type": "code", "execution_count": 116, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T18:03:53.561736Z", "start_time": "2020-10-13T18:03:53.460812Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 4396 is pandigital with x = 28 and y = 157, and current sum = 0...\n", "n = 5346 is pandigital with x = 18 and y = 297, and current sum = 4396...\n", "n = 5796 is pandigital with x = 12 and y = 483, and current sum = 9742...\n", "n = 6952 is pandigital with x = 4 and y = 1738, and current sum = 15538...\n", "n = 7254 is pandigital with x = 39 and y = 186, and current sum = 22490...\n", "n = 7632 is pandigital with x = 48 and y = 159, and current sum = 29744...\n", "n = 7852 is pandigital with x = 4 and y = 1963, and current sum = 37376...\n" ] }, { "data": { "text/plain": [ "45228" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum_of_all_pandigital_products()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 33: Digit cancelling fractions](https://projecteuler.net/problem=33)" ] }, { "cell_type": "code", "execution_count": 119, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:32:54.384218Z", "start_time": "2020-10-13T19:32:54.367829Z" } }, "outputs": [], "source": [ "import fractions\n", "F = fractions.Fraction" ] }, { "cell_type": "code", "execution_count": 123, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:33:50.172468Z", "start_time": "2020-10-13T19:33:50.161392Z" } }, "outputs": [ { "data": { "text/plain": [ "(Fraction(1, 2), Fraction(1, 2), True)" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F('49/98'), F('4/8'), F('49/98') == F('4/8')" ] }, { "cell_type": "code", "execution_count": 133, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:39:58.670313Z", "start_time": "2020-10-13T19:39:58.664142Z" } }, "outputs": [], "source": [ "def all_fractions_of_n_digits(n=2):\n", " start = '1'*n\n", " end = '9'*n\n", " for i in range(int(start), int(end) + 1):\n", " for j in range(i + 1, int(end) + 1):\n", " yield F(f\"{i}/{j}\"), i, j" ] }, { "cell_type": "code", "execution_count": 134, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:39:59.918389Z", "start_time": "2020-10-13T19:39:59.883547Z" } }, "outputs": [ { "data": { "text/plain": [ "3916" ] }, "execution_count": 134, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(list(all_fractions_of_n_digits(2)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So there are 3916 fractions of $x/y$ with $x,y$ having exactly two numbers, such that $x/y \\leq 1$.\n", "For each of them, we will try to remove one of the digits from $x$ and from $y$, and check if the resulting \"reduced\" fraction is equal to the original one. If we remove $0$, we won't count it." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's easy to remove digits when working with strings:" ] }, { "cell_type": "code", "execution_count": 137, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:40:17.898648Z", "start_time": "2020-10-13T19:40:17.896229Z" } }, "outputs": [], "source": [ "si, sj = \"49\", \"98\"" ] }, { "cell_type": "code", "execution_count": 136, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:40:01.225792Z", "start_time": "2020-10-13T19:40:01.221004Z" } }, "outputs": [ { "data": { "text/plain": [ "'4'" ] }, "execution_count": 136, "metadata": {}, "output_type": "execute_result" } ], "source": [ "si.replace(\"9\", \"\", 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we can check if the fraction $i/j$ can be \"wrongly\" simplified/reduced by such code:" ] }, { "cell_type": "code", "execution_count": 139, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:41:30.751388Z", "start_time": "2020-10-13T19:41:30.744940Z" } }, "outputs": [], "source": [ "def can_be_wrongly_simplified(i, j):\n", " si, sj = str(i), str(j)\n", " for digit in si:\n", " if digit != '0' and digit in sj:\n", " si_without_digit = int(si.replace(digit, \"\", 1))\n", " sj_without_digit = int(sj.replace(digit, \"\", 1))\n", " if sj_without_digit != 0 and F(f\"{i}/{j}\") == F(f\"{si_without_digit}/{sj_without_digit}\"):\n", " return True\n", " return False" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try it:" ] }, { "cell_type": "code", "execution_count": 140, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:41:31.569695Z", "start_time": "2020-10-13T19:41:31.518440Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1/4 with i = 16 and j = 64\n", "1/5 with i = 19 and j = 95\n", "2/5 with i = 26 and j = 65\n", "1/2 with i = 49 and j = 98\n" ] } ], "source": [ "for frac, i, j in all_fractions_of_n_digits(2):\n", " if can_be_wrongly_simplified(i, j):\n", " print(f\"{frac} with i = {i} and j = {j}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So there are indeed exactly four such fractions (with exactly two digits on nominator and denominator).\n", "\n", "Let's compute their product:" ] }, { "cell_type": "code", "execution_count": 142, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:42:36.013828Z", "start_time": "2020-10-13T19:42:35.964950Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1/4 with i = 16 and j = 64\n", "1/5 with i = 19 and j = 95\n", "2/5 with i = 26 and j = 65\n", "1/2 with i = 49 and j = 98\n", "Their product = 1/100\n" ] } ], "source": [ "product = F(1, 1)\n", "\n", "for frac, i, j in all_fractions_of_n_digits(2):\n", " if can_be_wrongly_simplified(i, j):\n", " print(f\"{frac} with i = {i} and j = {j}\")\n", " product *= frac\n", "\n", "print(f\"Their product = {product}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 34: Digit factorials](https://projecteuler.net/problem=34)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's compute efficiently the factorial function, by using memoisation:" ] }, { "cell_type": "code", "execution_count": 150, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:47:21.302418Z", "start_time": "2020-10-13T19:47:21.293931Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]\n" ] } ], "source": [ "from functools import lru_cache\n", "\n", "@lru_cache(maxsize=None)\n", "def factorial(n: int) -> int:\n", " if n <= 1: return 1\n", " else: return n * factorial(n - 1)\n", "\n", "factorials = [factorial(n) for n in range(0, 10)]\n", "print(factorials)" ] }, { "cell_type": "code", "execution_count": 167, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T19:59:44.314295Z", "start_time": "2020-10-13T19:59:44.306879Z" } }, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 167, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = 100\n", "math.ceil(math.log10(n)) # => 2 incorrect, needs + 1\n", "\n", "n = 145\n", "math.ceil(math.log10(n)) # => 3 correct" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, we need to bound the size of the largest integer that can be the sum of the factorials of its digits.\n", "\n", "Let $k$ the number of digits of $x$, for instance $k=2$. Then $x$ is between $100...0 = 10^{k-1}$ (eg $10$ for $k=2$) and $999..9 = 10^k - 1$ (eg $99 = 100-1$ for $k=2$).\n", "The sum of the factorials of the digits of $x$ is between $1 * 1! + (k-1) * 0! = 1$ and $k * 9! = 362880 k$.\n", "\n", "And thus, as soon as $362880 k < 10^{k-1}$ then it is not possible for $x$ to be equal to the sum of the factorials of its digits.\n", "\n", "For small values of $k$, such that $k=3$ (for the example $145$), $10^{k-1} \\leq 362880 k$ but we can easily find the smallest $k$ that violates this inequality.\n", "\n", "So the smallest $k$ that don't work is the smallest $k$ such that $362880 k < 10^{k-1}$. The right-hand side grows exponentially while the left-hand side grows linearly, so clearly there will be a solution. Intuitively, it won't be large.\n", "Let's find out manually:" ] }, { "cell_type": "code", "execution_count": 177, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:22:42.058446Z", "start_time": "2020-10-13T20:22:42.054073Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "6\n", "999999\n" ] } ], "source": [ "k = 1\n", "while 10**k <= 362880 * k:\n", " k += 1\n", "k = max(1, k - 1)\n", "print(k)\n", "max_nb_pb34 = 10**k - 1\n", "print(max_nb_pb34)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also easily test if a number is the sum of the factorials of its digits:" ] }, { "cell_type": "code", "execution_count": 178, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:22:44.949695Z", "start_time": "2020-10-13T20:22:44.946257Z" } }, "outputs": [], "source": [ "def is_sum_of_factorials_of_its_digits(n: int) -> bool:\n", " digits = map(int, list(str(n))) # 145 => [1, 4, 5]\n", " sum_of_factorials_of_its_digits = sum(map(factorial, digits))\n", " return sum_of_factorials_of_its_digits == n" ] }, { "cell_type": "code", "execution_count": 179, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:22:46.331126Z", "start_time": "2020-10-13T20:22:46.325127Z" } }, "outputs": [], "source": [ "assert not is_sum_of_factorials_of_its_digits(144)\n", "assert is_sum_of_factorials_of_its_digits(145)\n", "assert not is_sum_of_factorials_of_its_digits(146)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can list all the numbers up-to a certain bound, and keep the ones we want, then compute their sum:" ] }, { "cell_type": "code", "execution_count": 180, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:22:47.470287Z", "start_time": "2020-10-13T20:22:47.461955Z" } }, "outputs": [], "source": [ "def list_of_such_numbers_pb34(bound=max_nb_pb34):\n", " for i in range(3, bound + 1):\n", " if is_sum_of_factorials_of_its_digits(i):\n", " yield i\n", "\n", "def sum_of_such_numbers_pb34(bound=max_nb_pb34):\n", " return sum(list_of_such_numbers_pb34(bound=bound))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For numbers up-to $1000$, only 145 works:" ] }, { "cell_type": "code", "execution_count": 181, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:22:48.931284Z", "start_time": "2020-10-13T20:22:48.919688Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[145]\n", "145\n" ] } ], "source": [ "print(list(list_of_such_numbers_pb34(bound=1000)))\n", "print(sum_of_such_numbers_pb34(bound=1000))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's use the bound we computed:" ] }, { "cell_type": "code", "execution_count": 182, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:22:59.534184Z", "start_time": "2020-10-13T20:22:56.501504Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[145, 40585]\n", "40730\n" ] } ], "source": [ "print(list(list_of_such_numbers_pb34(bound=max_nb_pb34)))\n", "print(sum_of_such_numbers_pb34(bound=max_nb_pb34))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 35: Circular primes](https://projecteuler.net/problem=35)" ] }, { "cell_type": "code", "execution_count": 184, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:27:28.540850Z", "start_time": "2020-10-13T20:27:28.535748Z" } }, "outputs": [], "source": [ "import math" ] }, { "cell_type": "code", "execution_count": 189, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:30:25.303363Z", "start_time": "2020-10-13T20:30:25.299584Z" } }, "outputs": [], "source": [ "def erathostene_sieve(n: int) -> List[int]:\n", " primes = [False, False] + [True] * (n - 1) # from 0 to n included\n", " max_divisor = math.floor(math.sqrt(n))\n", " for divisor in range(2, max_divisor + 1):\n", " if primes[divisor]:\n", " i = 2\n", " while divisor * i <= n:\n", " primes[divisor * i] = False\n", " i += 1\n", " return primes" ] }, { "cell_type": "code", "execution_count": 191, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:30:47.371025Z", "start_time": "2020-10-13T20:30:47.363288Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, False, False, True, False, False, False]\n", "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n" ] } ], "source": [ "sieve100 = erathostene_sieve(100)\n", "print(sieve100)\n", "print([i for i, b in enumerate(sieve100) if b])" ] }, { "cell_type": "code", "execution_count": 194, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:32:38.982281Z", "start_time": "2020-10-13T20:32:38.641939Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "78498\n" ] } ], "source": [ "sieve1million = erathostene_sieve(int(1e6))\n", "print(len([i for i, b in enumerate(sieve1million) if b]))" ] }, { "cell_type": "code", "execution_count": 196, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:34:27.975671Z", "start_time": "2020-10-13T20:34:27.969516Z" } }, "outputs": [], "source": [ "def is_prime(n: int) -> bool:\n", " assert 1 <= n <= len(sieve1million) - 1\n", " return sieve1million[n]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we have all the prime numbers up-to one million, and a constant-time way of checking if small numbers are prime." ] }, { "cell_type": "code", "execution_count": 203, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:36:35.936773Z", "start_time": "2020-10-13T20:36:35.928667Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "197\n", "197\n", "971\n", "719\n" ] } ], "source": [ "s = '197'\n", "print(s)\n", "print(s[0:] + s[:0])\n", "print(s[1:] + s[:1])\n", "print(s[2:] + s[:2])" ] }, { "cell_type": "code", "execution_count": 206, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:38:53.563484Z", "start_time": "2020-10-13T20:38:53.555989Z" } }, "outputs": [], "source": [ "def circular_numbers(n: int) -> List[int]:\n", " str_n = str(n)\n", " return [ int(str_n[i:] + str_n[:i]) for i in range(1, len(str_n)) ]" ] }, { "cell_type": "code", "execution_count": 207, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:38:53.973223Z", "start_time": "2020-10-13T20:38:53.968095Z" } }, "outputs": [ { "data": { "text/plain": [ "[971, 719]" ] }, "execution_count": 207, "metadata": {}, "output_type": "execute_result" } ], "source": [ "circular_numbers(197)" ] }, { "cell_type": "code", "execution_count": 208, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:38:56.335407Z", "start_time": "2020-10-13T20:38:56.328165Z" } }, "outputs": [], "source": [ "def is_circular_prime(n: int) -> bool:\n", " if not is_prime(n):\n", " return False\n", " return all(map(is_prime, circular_numbers(n)))" ] }, { "cell_type": "code", "execution_count": 209, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:38:57.816819Z", "start_time": "2020-10-13T20:38:57.813291Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97]\n" ] } ], "source": [ "print([n for n in range(2, 100) if is_circular_prime(n)])" ] }, { "cell_type": "code", "execution_count": 210, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:39:21.455464Z", "start_time": "2020-10-13T20:39:21.022005Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "55\n" ] } ], "source": [ "print(len([n for n in range(2, int(1e6) + 1) if is_circular_prime(n)]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 36: Double-base palindromes](https://projecteuler.net/problem=36)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's very easy to check if $n$ is a palindrome in base $10$:" ] }, { "cell_type": "code", "execution_count": 211, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:41:08.957867Z", "start_time": "2020-10-13T20:41:08.954861Z" } }, "outputs": [], "source": [ "def is_palindrome_base10(n: int) -> bool:\n", " str_n = str(n)\n", " return str_n == str_n[::-1]" ] }, { "cell_type": "code", "execution_count": 212, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:41:27.890870Z", "start_time": "2020-10-13T20:41:27.885950Z" } }, "outputs": [], "source": [ "assert not is_palindrome_base10(584)\n", "assert is_palindrome_base10(585)\n", "assert not is_palindrome_base10(586)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's also very easy to check if $n$ is a palindrome in base $2$:" ] }, { "cell_type": "code", "execution_count": 215, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:42:08.806717Z", "start_time": "2020-10-13T20:42:08.803690Z" } }, "outputs": [ { "data": { "text/plain": [ "'1001001001'" ] }, "execution_count": 215, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin(585)[2:]" ] }, { "cell_type": "code", "execution_count": 216, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:42:34.812519Z", "start_time": "2020-10-13T20:42:34.809996Z" } }, "outputs": [], "source": [ "def is_palindrome_base2(n: int) -> bool:\n", " str_n_2 = bin(n)[2:]\n", " return str_n_2 == str_n_2[::-1]" ] }, { "cell_type": "code", "execution_count": 217, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:42:38.627686Z", "start_time": "2020-10-13T20:42:38.623340Z" } }, "outputs": [], "source": [ "assert not is_palindrome_base2(584)\n", "assert is_palindrome_base2(585)\n", "assert not is_palindrome_base2(586)" ] }, { "cell_type": "code", "execution_count": 218, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:43:41.204020Z", "start_time": "2020-10-13T20:43:41.199981Z" } }, "outputs": [], "source": [ "def palindromes_in_base10_and_base2(start: int=1, end: int=int(1e6)) -> List[int]:\n", " return [n for n in range(start, end + 1) if is_palindrome_base10(n) and is_palindrome_base2(n)]" ] }, { "cell_type": "code", "execution_count": 220, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:43:55.202338Z", "start_time": "2020-10-13T20:43:55.196680Z" } }, "outputs": [ { "data": { "text/plain": [ "[1, 3, 5, 7, 9, 33, 99, 313, 585, 717]" ] }, "execution_count": 220, "metadata": {}, "output_type": "execute_result" } ], "source": [ "palindromes_in_base10_and_base2(start=1, end=1000)" ] }, { "cell_type": "code", "execution_count": 222, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:44:17.086420Z", "start_time": "2020-10-13T20:44:16.782690Z" } }, "outputs": [ { "data": { "text/plain": [ "872187" ] }, "execution_count": 222, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(palindromes_in_base10_and_base2(start=1, end=int(1e6)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 37: Truncatable primes](https://projecteuler.net/problem=37)" ] }, { "cell_type": "code", "execution_count": 224, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:48:52.165872Z", "start_time": "2020-10-13T20:48:52.155298Z" } }, "outputs": [], "source": [ "def truncate_from_left_to_right(n: int) -> List[int]:\n", " str_n = str(n)\n", " return [int(str_n[i:]) for i in range(0, len(str_n))]" ] }, { "cell_type": "code", "execution_count": 225, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:48:58.148081Z", "start_time": "2020-10-13T20:48:58.142549Z" } }, "outputs": [ { "data": { "text/plain": [ "[3797, 797, 97, 7]" ] }, "execution_count": 225, "metadata": {}, "output_type": "execute_result" } ], "source": [ "truncate_from_left_to_right(3797)" ] }, { "cell_type": "code", "execution_count": 240, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:50:41.176945Z", "start_time": "2020-10-13T20:50:41.173888Z" } }, "outputs": [], "source": [ "def truncate_from_right_to_left(n: int) -> List[int]:\n", " str_n = str(n)\n", " return [int(str_n[:i]) for i in range(len(str_n), 0, -1)]" ] }, { "cell_type": "code", "execution_count": 241, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:50:41.458911Z", "start_time": "2020-10-13T20:50:41.453029Z" } }, "outputs": [ { "data": { "text/plain": [ "[3797, 379, 37, 3]" ] }, "execution_count": 241, "metadata": {}, "output_type": "execute_result" } ], "source": [ "truncate_from_right_to_left(3797)" ] }, { "cell_type": "code", "execution_count": 244, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:52:41.069804Z", "start_time": "2020-10-13T20:52:41.063585Z" } }, "outputs": [], "source": [ "def is_truncatable_prime(n: int, sieve: List[int]) -> bool:\n", " if n <= 7 or not sieve[n]: return False\n", " return all(sieve[k] for k in truncate_from_left_to_right(n) + truncate_from_right_to_left(n))" ] }, { "cell_type": "code", "execution_count": 248, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:54:11.615007Z", "start_time": "2020-10-13T20:54:11.611230Z" } }, "outputs": [], "source": [ "assert is_truncatable_prime(37, sieve=sieve1million)\n", "assert is_truncatable_prime(3797, sieve=sieve1million)\n", "assert not is_truncatable_prime(99371, sieve=sieve1million) # 99 is not prime!" ] }, { "cell_type": "code", "execution_count": 250, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T20:57:03.641523Z", "start_time": "2020-10-13T20:57:03.638390Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n" ] } ], "source": [ "print([i for i, b in enumerate(sieve100) if b])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The tricky part is to bound the largest number than can be a truncatable prime.\n", "The problem states that there are only eleven primes that are truncatable primes.\n", "How to find an upper bound on these numbers?\n", "\n", "Well, one solution could just to enumerate prime numbers until we find 11 candidates, then stop.\n", "Let's cheat and do that." ] }, { "cell_type": "code", "execution_count": 253, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T21:00:29.609019Z", "start_time": "2020-10-13T21:00:29.600412Z" } }, "outputs": [], "source": [ "def find_truncatable_primes(maxnumber=11, sieve=sieve1million):\n", " truncatable_primes = []\n", " number = 0\n", " for i, b in enumerate(sieve1million):\n", " if b:\n", " if is_truncatable_prime(i, sieve=sieve):\n", " truncatable_primes.append(i)\n", " number += 1\n", " if number >= maxnumber:\n", " return truncatable_primes" ] }, { "cell_type": "code", "execution_count": 264, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T21:00:45.194690Z", "start_time": "2020-10-13T21:00:44.916126Z" } }, "outputs": [ { "data": { "text/plain": [ "[23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]" ] }, "execution_count": 264, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_truncatable_primes(maxnumber=11)" ] }, { "cell_type": "code", "execution_count": 265, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T21:00:48.375736Z", "start_time": "2020-10-13T21:00:48.017390Z" } }, "outputs": [], "source": [ "find_truncatable_primes(maxnumber=12)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That's a good sign, for prime numbers up-to a million we could not find the 12th truncatable prime." ] }, { "cell_type": "code", "execution_count": 266, "metadata": { "ExecuteTime": { "end_time": "2020-10-13T21:01:22.136326Z", "start_time": "2020-10-13T21:01:21.858516Z" } }, "outputs": [ { "data": { "text/plain": [ "748317" ] }, "execution_count": 266, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(find_truncatable_primes(maxnumber=11))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 38: Pandigital multiples](https://projecteuler.net/problem=38)\n", "\n", "Well I wrote the code and my notebook froze so I lost everything... Not so motivated to start again.\n", "\n", "The first thing to do is to mathematically bound the largest integer $x$ such that the product of $x$ by $1,\\dots,n$ gives a 1-to-9 pandigital number.\n", "\n", "- $n$ clearly has to be smaller than $9$, otherwise the concatenated product have more than $10$ digits and cannot be 1-to-9 pandigital.\n", "- Now, for a fixed $n$, if $x$ has $d$ digits then $nd \\leq 9$, so this bounds the largest possible $x$ for a candidate $n$.\n", "\n", "Let's simply try them all." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:09:25.825136Z", "start_time": "2020-10-14T14:09:25.818951Z" } }, "outputs": [], "source": [ "from typing import Union" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:09:31.056207Z", "start_time": "2020-10-14T14:09:31.045900Z" } }, "outputs": [], "source": [ "def is_pandigital_1to9(n: Union[str, int]) -> bool:\n", " str_n = str(n)\n", " if len(str_n) != 9: return False\n", " return sorted(str_n) == ['1','2','3','4','5','6','7','8','9']" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:09:02.736288Z", "start_time": "2020-10-14T14:09:02.730190Z" } }, "outputs": [], "source": [ "assert is_pandigital_1to9(192384576)\n", "assert is_pandigital_1to9(918273645)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:10:14.126789Z", "start_time": "2020-10-14T14:10:14.119036Z" } }, "outputs": [], "source": [ "def concatenated_product_1ton(x: int, n: int) -> str:\n", " return ''.join(str(x * i) for i in range(1, n+1))" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:11:34.275713Z", "start_time": "2020-10-14T14:11:34.271660Z" } }, "outputs": [], "source": [ "assert is_pandigital_1to9(concatenated_product_1ton(192, 3))\n", "assert is_pandigital_1to9(concatenated_product_1ton(9, 5))\n", "assert is_pandigital_1to9(concatenated_product_1ton(1, 9))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can just try all the possible values for $x$ and $n$ and keep a list of the candidates and return the largest one." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:35:08.474387Z", "start_time": "2020-10-14T14:35:08.467559Z" } }, "outputs": [], "source": [ "def all_concatenated_product_pandigital_1to9(max_n: int):\n", " candidates = []\n", " for n in range(2, max_n + 1):\n", " print(f\"\\nStarting with n = {n}...\")\n", " d = 1\n", " while n*d <= 9:\n", " print(f\"\\tStarting with d = {d}...\")\n", " for x in range(10**(d-1), 10**d):\n", " prod_x_1ton = concatenated_product_1ton(x, n)\n", " if is_pandigital_1to9(prod_x_1ton):\n", " print(f\" ==> adding {prod_x_1ton} coming from x = {x}, d = {d} and n = {n}\")\n", " candidates.append(int(prod_x_1ton))\n", " d += 1\n", " return candidates" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:35:09.238939Z", "start_time": "2020-10-14T14:35:09.235140Z" } }, "outputs": [], "source": [ "def largest_concatenated_product_pandigital_1to9(max_n: int):\n", " candidates = all_concatenated_product_pandigital_1to9(max_n = max_n)\n", " return max(candidates)" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T14:35:10.929089Z", "start_time": "2020-10-14T14:35:10.884951Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Starting with n = 2...\n", "\tStarting with d = 1...\n", "\tStarting with d = 2...\n", "\tStarting with d = 3...\n", "\tStarting with d = 4...\n", " ==> adding 672913458 coming from x = 6729, d = 4 and n = 2\n", " ==> adding 679213584 coming from x = 6792, d = 4 and n = 2\n", " ==> adding 692713854 coming from x = 6927, d = 4 and n = 2\n", " ==> adding 726914538 coming from x = 7269, d = 4 and n = 2\n", " ==> adding 729314586 coming from x = 7293, d = 4 and n = 2\n", " ==> adding 732914658 coming from x = 7329, d = 4 and n = 2\n", " ==> adding 769215384 coming from x = 7692, d = 4 and n = 2\n", " ==> adding 792315846 coming from x = 7923, d = 4 and n = 2\n", " ==> adding 793215864 coming from x = 7932, d = 4 and n = 2\n", " ==> adding 926718534 coming from x = 9267, d = 4 and n = 2\n", " ==> adding 927318546 coming from x = 9273, d = 4 and n = 2\n", " ==> adding 932718654 coming from x = 9327, d = 4 and n = 2\n", "\n", "Starting with n = 3...\n", "\tStarting with d = 1...\n", "\tStarting with d = 2...\n", "\tStarting with d = 3...\n", " ==> adding 192384576 coming from x = 192, d = 3 and n = 3\n", " ==> adding 219438657 coming from x = 219, d = 3 and n = 3\n", " ==> adding 273546819 coming from x = 273, d = 3 and n = 3\n", " ==> adding 327654981 coming from x = 327, d = 3 and n = 3\n", "\n", "Starting with n = 4...\n", "\tStarting with d = 1...\n", "\tStarting with d = 2...\n", "\n", "Starting with n = 5...\n", "\tStarting with d = 1...\n", " ==> adding 918273645 coming from x = 9, d = 1 and n = 5\n", "\n", "Starting with n = 6...\n", "\tStarting with d = 1...\n", "\n", "Starting with n = 7...\n", "\tStarting with d = 1...\n", "\n", "Starting with n = 8...\n", "\tStarting with d = 1...\n", "\n", "Starting with n = 9...\n", "\tStarting with d = 1...\n", " ==> adding 123456789 coming from x = 1, d = 1 and n = 9\n" ] }, { "data": { "text/plain": [ "932718654" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "largest_concatenated_product_pandigital_1to9(9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 39: Integer right triangles](https://projecteuler.net/problem=39)\n", "If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120 : {20,48,52}, {24,45,51}, {30,40,50}\n", "\n", "For which value of p ≤ 1000, is the number of solutions maximised?\n", "\n", "Well there is no need to be smart here, we just need to try all the values $a,b,c=\\sqrt{a^2+b^2}$ such that the longer slide is an integer, keep the list of values of p and the number of solutions, and find the p that maximize this number of solutions.\n", "\n", "We could be much smarter in narrowing down the possible values for $a,b,c$, but we don't really need to." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T17:57:45.159540Z", "start_time": "2020-10-14T17:57:45.152227Z" } }, "outputs": [], "source": [ "import math" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:06:54.509834Z", "start_time": "2020-10-14T18:06:54.488748Z" } }, "outputs": [], "source": [ "def find_all_integer_right_triangle(max_p=1000):\n", " nb_of_solutions_by_p = {}\n", " solutions_by_p = {}\n", " for p in range(1, max_p + 1):\n", " nb_of_solutions_by_p[p] = 0\n", " solutions_by_p[p] = []\n", " max_side = p // 2\n", " for a in range(1, max_side + 1):\n", " for b in range(a + 1, max_side + 1):\n", " c = math.sqrt(a**2 + b**2)\n", " if int(c) == c:\n", " c = int(c)\n", " if a + b + c == p:\n", " nb_of_solutions_by_p[p] += 1\n", " solutions_by_p[p] += [(a,b,c)]\n", " max_nb_of_solutions = max(nb_solutions for nb_solutions in nb_of_solutions_by_p.values())\n", " print(max_nb_of_solutions)\n", " print([solutions_by_p[p] for p in solutions_by_p.keys() if nb_of_solutions_by_p[p] == max_nb_of_solutions])\n", " return [p for p in nb_of_solutions_by_p.keys() if nb_of_solutions_by_p[p] == max_nb_of_solutions]" ] }, { "cell_type": "code", "execution_count": 53, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:06:55.103691Z", "start_time": "2020-10-14T18:06:54.990236Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n", "[[(20, 48, 52), (24, 45, 51), (30, 40, 50)]]\n" ] }, { "data": { "text/plain": [ "[120]" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_all_integer_right_triangle(max_p=120)" ] }, { "cell_type": "code", "execution_count": 54, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:07:37.453191Z", "start_time": "2020-10-14T18:06:59.882579Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "8\n", "[[(40, 399, 401), (56, 390, 394), (105, 360, 375), (120, 350, 370), (140, 336, 364), (168, 315, 357), (210, 280, 350), (240, 252, 348)]]\n" ] }, { "data": { "text/plain": [ "[840]" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_all_integer_right_triangle(max_p=1000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So the answer is $p=840$, which have 8 solutions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 40: Champernowne's constant](https://projecteuler.net/problem=40)\n", "\n", "Let's use a huge string and simply access its value at index $i=1,10,100,1000,10000,100000,1000000$.\n", "It will take some time but it'll work easily." ] }, { "cell_type": "code", "execution_count": 55, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:14:31.123077Z", "start_time": "2020-10-14T18:14:31.115502Z" } }, "outputs": [], "source": [ "def construct_irrational_decimal_fraction(max_n=30):\n", " return ''.join(str(n) for n in range(1, max_n + 1))" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:14:54.896331Z", "start_time": "2020-10-14T18:14:54.887644Z" } }, "outputs": [], "source": [ "assert '1' == construct_irrational_decimal_fraction(30)[11] # 12th digit is 1, ok" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can just build a huge string and access it." ] }, { "cell_type": "code", "execution_count": 59, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:16:02.899968Z", "start_time": "2020-10-14T18:16:02.890636Z" } }, "outputs": [], "source": [ "def product(iterator):\n", " p = 1\n", " for value in iterator:\n", " p *= value\n", " return p" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:17:38.295676Z", "start_time": "2020-10-14T18:17:38.283383Z" } }, "outputs": [], "source": [ "def product_of_d1_to_dn(list_of_n=[1,10]):\n", " max_n = max(list_of_n)\n", " s = construct_irrational_decimal_fraction(max_n=1+max_n)\n", " return product(int(s[di]) for di in list_of_n)" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:17:38.500230Z", "start_time": "2020-10-14T18:17:38.495114Z" } }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([1, 11]) # product of 2th digit = 2 and 12th digit = 1 ==> 2" ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:18:34.296006Z", "start_time": "2020-10-14T18:18:34.285148Z" } }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([0, 9])" ] }, { "cell_type": "code", "execution_count": 71, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:18:34.935141Z", "start_time": "2020-10-14T18:18:34.929926Z" } }, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([0, 9, 99])" ] }, { "cell_type": "code", "execution_count": 72, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:18:40.893585Z", "start_time": "2020-10-14T18:18:40.469167Z" } }, "outputs": [ { "data": { "text/plain": [ "15" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([0, 9, 99, 999])" ] }, { "cell_type": "code", "execution_count": 73, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:18:40.893585Z", "start_time": "2020-10-14T18:18:40.469167Z" } }, "outputs": [ { "data": { "text/plain": [ "105" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([0, 9, 99, 999, 9999])" ] }, { "cell_type": "code", "execution_count": 74, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:18:40.893585Z", "start_time": "2020-10-14T18:18:40.469167Z" } }, "outputs": [ { "data": { "text/plain": [ "210" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([0, 9, 99, 999, 9999, 99999])" ] }, { "cell_type": "code", "execution_count": 75, "metadata": { "ExecuteTime": { "end_time": "2020-10-14T18:18:40.893585Z", "start_time": "2020-10-14T18:18:40.469167Z" } }, "outputs": [ { "data": { "text/plain": [ "210" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "product_of_d1_to_dn([0, 9, 99, 999, 9999, 99999, 999999])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 41: Pandigital prime](https://projecteuler.net/problem=41)\n", "\n", "If $p$ is a prime $n$-digit pandigital number, then $p$ is smaller than $n(n-1)..1$ (written in base $10$), eg with $n=5$, $p$ is smaller than $54321$.\n", "For $n=9$, the largest possible $9$-digit pandigital number is $987654321$.\n", "Let's build a Erathostene sieve of size $987654321+1$ and just check all the prime numbers for being $n$-digit pandigital, for $n=1$ to $n=9$.\n", "It won't be fast, but it'll work." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:29:32.326716Z", "start_time": "2020-10-15T12:29:32.319783Z" } }, "outputs": [], "source": [ "import math\n", "from typing import List" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:29:36.235529Z", "start_time": "2020-10-15T12:29:35.767304Z" } }, "outputs": [], "source": [ "%load_ext Cython" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:29:37.471747Z", "start_time": "2020-10-15T12:29:37.452664Z" } }, "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": "markdown", "metadata": {}, "source": [ "For 10 million primes, this takes about 3 seconds on my machine, thanks to Cython being faster than naive Python code." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:30:26.328234Z", "start_time": "2020-10-15T12:30:22.514996Z" } }, "outputs": [], "source": [ "sieve10million = erathostene_sieve(int(1e7))\n", "primes_upto_1e7 = [p for p,b in enumerate(sieve10million) if b]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For about 1 billion primes, this takes about 30 seconds on my machine, thanks to Cython being faster than naive Python code." ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:33:26.313919Z", "start_time": "2020-10-15T12:32:55.712881Z" } }, "outputs": [], "source": [ "sieve1billion = erathostene_sieve(98765432+1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For about 10 billion primes, this should take about 15 minutes on my machine, thanks to Cython being faster than naive Python code." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:39:16.628501Z", "start_time": "2020-10-15T12:33:33.092296Z" } }, "outputs": [], "source": [ "sieve10billion = erathostene_sieve(987654321+1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we have a LARGE bool array to check in constant time if a number is prime, we can build the list of prime numbers up-to this $max_p = 987654321$." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:41:53.555072Z", "start_time": "2020-10-15T12:40:49.774974Z" } }, "outputs": [], "source": [ "primes_upto_987654321 = [p for p,b in enumerate(sieve10billion) if b]" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:44:59.335602Z", "start_time": "2020-10-15T12:44:51.291886Z" } }, "outputs": [], "source": [ "del sieve1billion, sieve10billion # to save so RAM" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:45:21.603477Z", "start_time": "2020-10-15T12:45:21.587867Z" } }, "outputs": [ { "data": { "text/plain": [ "50251452" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(primes_upto_987654321) # not so large, there is about O(log n) primes smaller than n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's test if a number is 1-to-n pandigital." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:45:32.883606Z", "start_time": "2020-10-15T12:45:32.866436Z" }, "code_folding": [ 4 ] }, "outputs": [], "source": [ "from typing import Union\n", "\n", "def is_pandigital_1ton(x: Union[str, int], n: int) -> bool:\n", " str_x = str(x)\n", " if len(str_x) != n: return False\n", " # fastest version\n", " if n == 1:\n", " return sorted(str_x) == ['1']\n", " elif n == 2:\n", " return sorted(str_x) == ['1','2']\n", " elif n == 3:\n", " return sorted(str_x) == ['1','2','3']\n", " elif n == 4:\n", " return sorted(str_x) == ['1','2','3','4']\n", " elif n == 5:\n", " return sorted(str_x) == ['1','2','3','4','5']\n", " elif n == 6:\n", " return sorted(str_x) == ['1','2','3','4','5','6']\n", " elif n == 7:\n", " return sorted(str_x) == ['1','2','3','4','5','6','7']\n", " elif n == 8:\n", " return sorted(str_x) == ['1','2','3','4','5','6','7','8']\n", " elif n == 9:\n", " return sorted(str_x) == ['1','2','3','4','5','6','7','8','9']\n", " return False" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:45:44.197061Z", "start_time": "2020-10-15T12:45:44.184744Z" } }, "outputs": [], "source": [ "from typing import Dict\n", "\n", "def find_pandigital_primes(list_of_primes: List[int]) -> Dict[int, List[int]]:\n", " solutions = dict()\n", " for n in range(1, 9 + 1):\n", " solutions[n] = [ prime for prime in list_of_primes if is_pandigital_1ton(prime, n) ]\n", " return solutions" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:45:55.326601Z", "start_time": "2020-10-15T12:45:55.321055Z" } }, "outputs": [], "source": [ "def largest_pandigital_prime(list_of_primes: List[int]) -> int:\n", " solutions = find_pandigital_primes(list_of_primes)\n", " # print(\"All 1-to-n pandigital primes:\", {n: solutions[n] for n in range(1, 9 + 1)})\n", " max_primes = { n: max(solutions[n]) for n in range(1, 9 + 1) if solutions[n] }\n", " print(\"Max 1-to-n pandigital primes:\", max_primes)\n", " return max(max_primes.values())" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:46:09.152392Z", "start_time": "2020-10-15T12:46:06.536833Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Max 1-to-n pandigital primes: {4: 4231, 7: 7652413}\n" ] }, { "data": { "text/plain": [ "7652413" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "largest_pandigital_prime(primes_upto_1e7)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T12:49:55.759229Z", "start_time": "2020-10-15T12:46:20.473195Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Max 1-to-n pandigital primes: {4: 4231, 7: 7652413}\n" ] }, { "data": { "text/plain": [ "7652413" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "largest_pandigital_prime(primes_upto_987654321)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 32: Coded triangle numbers](https://projecteuler.net/problem=42)\n", "\n", "- We need to be able to check (quickly) if a word is a triangle word.\n", "- The simplest approach would be to first read all the words, compute the length $n_\\max$ of the longer one, and then say that the longest word value can be $t_{up} = 26* n_\\max$, so then we can compute all the triangle numbers up to $t_{up}$." ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T13:43:18.785752Z", "start_time": "2020-10-15T13:43:18.254821Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p042_words.txt\n", " 0 1 16345 p042_words.txt\n" ] } ], "source": [ "!ls p042_words.txt\n", "!wc p042_words.txt" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T13:46:58.544964Z", "start_time": "2020-10-15T13:46:58.540367Z" } }, "outputs": [], "source": [ "with open('p042_words.txt') as f:\n", " words = f.readline()\n", "words = words.replace('\"','').split(',')" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T13:47:25.315621Z", "start_time": "2020-10-15T13:47:25.310190Z" } }, "outputs": [ { "data": { "text/plain": [ "(list, 'A', 1786)" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(words), words[0], len(words)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we have these 1786 words." ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T13:48:10.726092Z", "start_time": "2020-10-15T13:48:10.717058Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There is 1786 words, of maximum length 14\n" ] } ], "source": [ "max_length_words = max(map(len, words))\n", "print(f\"There is {len(words)} words, of maximum length {max_length_words}\")" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T13:48:44.060795Z", "start_time": "2020-10-15T13:48:44.046614Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "So the largest word is 364\n" ] } ], "source": [ "largest_word_value = 26 * max_length_words\n", "print(f\"So the largest word is {largest_word_value}\")" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:00:29.951214Z", "start_time": "2020-10-15T14:00:29.946467Z" } }, "outputs": [], "source": [ "def triangle_numbers_upto(max_value: int) -> List[int]:\n", " triangle_numbers = []\n", " i = 1\n", " t = i\n", " while t <= max_value:\n", " triangle_numbers.append(t)\n", " i += 1\n", " t += i\n", " return triangle_numbers" ] }, { "cell_type": "code", "execution_count": 51, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:01:54.899154Z", "start_time": "2020-10-15T14:01:54.890363Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{1, 3, 6, 136, 10, 15, 276, 21, 153, 28, 36, 171, 300, 45, 55, 190, 66, 325, 78, 210, 91, 351, 231, 105, 120, 253}\n", "There are 26 triangle numbers smaller than 364\n" ] } ], "source": [ "triangles = set(triangle_numbers_upto(largest_word_value))\n", "# using a set() will make the test n in triangles faster!\n", "print(triangles)\n", "print(f\"There are {len(triangles)} triangle numbers smaller than {largest_word_value}\")" ] }, { "cell_type": "code", "execution_count": 56, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:05:46.447290Z", "start_time": "2020-10-15T14:05:46.443422Z" } }, "outputs": [], "source": [ "def letter_to_int(letter: str) -> int:\n", " return ord(letter) - ord('A') + 1\n", "\n", "# for letter in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':\n", "# print(f\"{letter} -> {letter_to_int(letter)}\")" ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:06:00.170090Z", "start_time": "2020-10-15T14:06:00.165922Z" } }, "outputs": [], "source": [ "def word_value(word: str) -> int:\n", " return sum(letter_to_int(letter) for letter in word)" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:06:13.880862Z", "start_time": "2020-10-15T14:06:13.875459Z" } }, "outputs": [ { "data": { "text/plain": [ "55" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "word_value(\"SKY\") # 19 + 11 + 25 = 55" ] }, { "cell_type": "code", "execution_count": 52, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:02:28.943585Z", "start_time": "2020-10-15T14:02:28.930731Z" } }, "outputs": [], "source": [ "def is_triangle_word(word: str) -> bool:\n", " value = word_value(word)\n", " return value in triangles" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:07:44.756179Z", "start_time": "2020-10-15T14:07:44.751289Z" } }, "outputs": [], "source": [ "def number_of_triangle_words(words: List[str]) -> int:\n", " return sum(1 for word in words if is_triangle_word(word))" ] }, { "cell_type": "code", "execution_count": 63, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:07:57.746828Z", "start_time": "2020-10-15T14:07:57.734897Z" } }, "outputs": [ { "data": { "text/plain": [ "162" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "number_of_triangle_words(words)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Good, it wasn't that hard!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 43: sub-string divisibility](https://projecteuler.net/problem=43)" ] }, { "cell_type": "code", "execution_count": 64, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:22:57.376312Z", "start_time": "2020-10-15T14:22:57.365316Z" }, "code_folding": [ 4 ] }, "outputs": [], "source": [ "from typing import Union\n", "\n", "def is_pandigital_0to9(x: Union[str, int]) -> bool:\n", " str_x = str(x)\n", " if len(str_x) != 10: return False\n", " return sorted(str_x) == ['0','1','2','3','4','5','6','7','8','9']" ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:23:13.458431Z", "start_time": "2020-10-15T14:23:13.448137Z" } }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_pandigital_0to9(1406357289)" ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:26:12.938228Z", "start_time": "2020-10-15T14:26:12.926229Z" } }, "outputs": [], "source": [ "def has_substring_divisibility(x: Union[str, int]) -> bool:\n", " x = str(x)\n", " digits = {i+1: int(c) for i,c in enumerate(x)}\n", " make_digit = lambda i: int(f\"{digits[i]}{digits[i+1]}{digits[i+2]}\")\n", " divisors = [2, 3, 5, 7, 11, 13, 17]\n", " return all(\n", " make_digit(i+2) % divisor == 0\n", " for i, divisor in enumerate(divisors)\n", " )" ] }, { "cell_type": "code", "execution_count": 69, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:26:59.955216Z", "start_time": "2020-10-15T14:26:59.947486Z" } }, "outputs": [], "source": [ "assert not has_substring_divisibility(1406357287)\n", "assert not has_substring_divisibility(1406357288)\n", "assert has_substring_divisibility(1406357289)\n", "assert not has_substring_divisibility(1406357290)\n", "assert not has_substring_divisibility(1406357291)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we simply have to try all the 0-to-9 pandigital numbers, from 0123456789 (smallest) to 9876543210 (largest), and count the number of such numbers that satisfy this property.\n", "\n", "It's easy to test all such pandigital numbers by using permutations of the string 0123456789, using [`itertools.permutations`](https://docs.python.org/3/library/itertools.html#itertools.permutations)." ] }, { "cell_type": "code", "execution_count": 70, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:30:00.655736Z", "start_time": "2020-10-15T14:30:00.645693Z" } }, "outputs": [], "source": [ "import itertools" ] }, { "cell_type": "code", "execution_count": 78, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:36:35.930861Z", "start_time": "2020-10-15T14:36:34.989600Z" } }, "outputs": [ { "data": { "text/plain": [ "3628800" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(list(itertools.permutations(list('0123456789'))))" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:36:53.853891Z", "start_time": "2020-10-15T14:36:53.841782Z" } }, "outputs": [], "source": [ "def find_all_substring_divisible_0to9_pandigital_numbers():\n", " candidates = []\n", " for digits in itertools.permutations(list('0123456789')):\n", " str_number = ''.join(digits)\n", " if is_pandigital_0to9(str_number):\n", " if has_substring_divisibility(str_number):\n", " print(f\"Adding a new number = {int(str_number)}\")\n", " candidates.append(int(str_number))\n", " return candidates\n", " return [ int(str_number) \n", " for str_number in itertools.permutations('0123456789')\n", " if is_pandigital_0to9(str_number)\n", " and has_substring_divisibility(str_number)\n", " ]" ] }, { "cell_type": "code", "execution_count": 80, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T14:37:32.628235Z", "start_time": "2020-10-15T14:37:06.051057Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Adding a new number = 1406357289\n", "Adding a new number = 1430952867\n", "Adding a new number = 1460357289\n", "Adding a new number = 4106357289\n", "Adding a new number = 4130952867\n", "Adding a new number = 4160357289\n", "There is 6 such numbers, their sum = 16695334890.\n" ] } ], "source": [ "candidates = find_all_substring_divisible_0to9_pandigital_numbers()\n", "print(f\"There is {len(candidates)} such numbers, their sum = {sum(candidates)}.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 44: pentagon numbers](https://projecteuler.net/problem=44)" ] }, { "cell_type": "code", "execution_count": 92, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T15:19:11.643250Z", "start_time": "2020-10-15T15:19:11.638585Z" } }, "outputs": [], "source": [ "def nth_pentagonal_number(n: int) -> int:\n", " # if n is odd, 3*n-1 is even, so n * (3n-1) is even\n", " # if n is even, n * (3n-1) is even\n", " # so the division by two is always an integer division\n", " return n * (3*n - 1) // 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "From the formula of $P_n = n(3n-1)/2$, it is clear that for any fixed $i$, $|P_{i+k}-P_i| = (i+k)(3(i+k)-1)/2 - i(3i-1)/2 = ( i(3i-1) + k(3i-1) + i(3k-1) + k(3k-1) - i(3i-1) )/2 = (k(3i-1) + i(3k-1) + k(3k-1))/2$ is an increasing function of $k$, and also for any fixed $k$, an increasing function of $i$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try naively to compute the first 1 million pentagonal numbers, put them in a set $\\mathcal{P}$ then check if there are any $P_j,P_k$ (with $k > j$) that satisfy $P_j+P_k \\in \\mathcal{P}$ and $P_k - P_j \\in \\mathcal{P}$.\n", "\n", "My intuition is that the solution that minimizes $D=|P_k-P_j|$ will be found within the first 1 million pentagonal numbers, so we don't need to mathematically bound the value of the largest $k,j$." ] }, { "cell_type": "code", "execution_count": 93, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T15:19:30.248855Z", "start_time": "2020-10-15T15:19:30.241330Z" } }, "outputs": [], "source": [ "def compute_all_pentagonal_numbers(max_n: int) -> List[int]:\n", " return [nth_pentagonal_number(n) for n in range(1, int(max_n) + 1)]" ] }, { "cell_type": "code", "execution_count": 98, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T15:22:53.692960Z", "start_time": "2020-10-15T15:22:53.608552Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 79.1 ms, sys: 0 ns, total: 79.1 ms\n", "Wall time: 76.4 ms\n" ] } ], "source": [ "%%time\n", "onemillion_pentagonal_numbers = compute_all_pentagonal_numbers(1e5)" ] }, { "cell_type": "code", "execution_count": 99, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T15:23:07.001171Z", "start_time": "2020-10-15T15:23:06.994160Z" } }, "outputs": [], "source": [ "def try_all_pairs_of_pentagonal_numbers(pentagonal_numbers: List[int]) -> List[int]:\n", " pairs_that_are_good = []\n", " pentagonal_numbers_set = set(pentagonal_numbers)\n", " n = len(pentagonal_numbers)\n", " for j in range(n):\n", " Pj = pentagonal_numbers[j]\n", " for k in range(j + 1, n):\n", " Pk = pentagonal_numbers[k]\n", " their_sum = Pk + Pj\n", " if their_sum not in pentagonal_numbers_set:\n", " continue\n", " their_difference = Pk - Pj\n", " if their_difference not in pentagonal_numbers_set:\n", " continue\n", " print(f\"Found another pair P{j} = {Pj}, P{k} = {Pk} whose sum = {their_sum} and difference = {their_difference} are pentagonal numbers too.\")\n", " pairs_that_are_good.append((their_difference, Pj, Pk, their_sum))\n", " return pairs_that_are_good" ] }, { "cell_type": "code", "execution_count": 100, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T15:26:03.165036Z", "start_time": "2020-10-15T15:23:21.715756Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Found another pair P1019 = 1560090, P2166 = 7042750 whose sum = 8602840 and difference = 5482660 are pentagonal numbers too.\n" ] }, { "ename": "KeyboardInterrupt", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mtry_all_pairs_of_pentagonal_numbers\u001b[0;34m(pentagonal_numbers)\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0mPj\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpentagonal_numbers\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mj\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mPk\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpentagonal_numbers\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 9\u001b[0m \u001b[0mtheir_sum\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mPk\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mPj\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtheir_sum\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mpentagonal_numbers_set\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mKeyboardInterrupt\u001b[0m: " ] } ], "source": [ "%%time\n", "try_all_pairs_of_pentagonal_numbers(onemillion_pentagonal_numbers)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I got bored of waiting, and tadam the first solution is the good one!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 45: Triangular, pentagonal, and hexagonal](https://projecteuler.net/problem=45)\n", "\n", "Ideally, this problem will be easy to solve if there is a $\\mathcal{O}(1)$ method to check if a number is a triangle, pentagonal and hexagonal number.\n", "I don't see an easy method, so let's just compute a lot of each of them, and try." ] }, { "cell_type": "code", "execution_count": 108, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:31:09.482948Z", "start_time": "2020-10-15T19:31:09.476516Z" } }, "outputs": [], "source": [ "def nth_triangle_number(n: int) -> int:\n", " return n * (n+1) // 2\n", "\n", "def nth_pentagonal_number(n: int) -> int:\n", " return n * (3*n - 1) // 2\n", "\n", "def nth_hexagonal_number(n: int) -> int:\n", " return n * (2*n - 1)" ] }, { "cell_type": "code", "execution_count": 109, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:31:17.407301Z", "start_time": "2020-10-15T19:31:17.404831Z" } }, "outputs": [], "source": [ "assert nth_triangle_number(285) == 40755\n", "assert nth_pentagonal_number(165) == 40755\n", "assert nth_hexagonal_number(143) == 40755" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can generate a set of a lot of triangle numbers, pentagonal numbers, hexagonal numbers, and find their intersection." ] }, { "cell_type": "code", "execution_count": 110, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:33:16.625407Z", "start_time": "2020-10-15T19:33:16.619981Z" } }, "outputs": [ { "data": { "text/plain": [ "{1}" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "{1, 3, 6, 10, 15} & {1, 5, 12, 22, 35} & {1, 6, 15, 28, 45}" ] }, { "cell_type": "code", "execution_count": 111, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:34:00.787571Z", "start_time": "2020-10-15T19:34:00.778717Z" } }, "outputs": [], "source": [ "def intersection_of_sets_of_three_kinds_of_numbers(max_n: int) -> List[int]:\n", " set_triangles = { nth_triangle_number(n) for n in range(1, max_n + 1) }\n", " set_pentagonals = { nth_pentagonal_number(n) for n in range(1, max_n + 1) }\n", " set_hexagonals = { nth_hexagonal_number(n) for n in range(1, max_n + 1) }\n", " intersection = set_triangles & set_pentagonals & set_hexagonals\n", " return sorted(list(intersection))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, let's check that 40755=$T_{285}=P_{165}=H_{143}$ can indeed be found using this approach:" ] }, { "cell_type": "code", "execution_count": 112, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:34:20.383483Z", "start_time": "2020-10-15T19:34:20.378047Z" } }, "outputs": [ { "data": { "text/plain": [ "[1, 40755]" ] }, "execution_count": 112, "metadata": {}, "output_type": "execute_result" } ], "source": [ "intersection_of_sets_of_three_kinds_of_numbers(300)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How can we know when to stop?\n", "I simply tried augmenting `max_n` until I found the next triangle number that is also pentagonal and hexagonal." ] }, { "cell_type": "code", "execution_count": 119, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:36:34.360512Z", "start_time": "2020-10-15T19:36:34.278218Z" } }, "outputs": [ { "data": { "text/plain": [ "[1, 40755, 1533776805]" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" } ], "source": [ "intersection_of_sets_of_three_kinds_of_numbers(100000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 46: Goldbach's other conjecture](https://projecteuler.net/problem=46)" ] }, { "cell_type": "code", "execution_count": 120, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:59:48.835355Z", "start_time": "2020-10-15T19:59:48.831426Z" } }, "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": 121, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T19:59:56.902679Z", "start_time": "2020-10-15T19:59:56.894232Z" } }, "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": "markdown", "metadata": {}, "source": [ "For 10 million primes, this takes about 3 seconds on my machine, thanks to Cython being faster than naive Python code." ] }, { "cell_type": "code", "execution_count": 122, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:00:07.540058Z", "start_time": "2020-10-15T20:00:04.846860Z" } }, "outputs": [], "source": [ "sieve10million = erathostene_sieve(int(1e7))\n", "primes_upto_1e7 = [p for p,b in enumerate(sieve10million) if b]" ] }, { "cell_type": "code", "execution_count": 126, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:01:19.117211Z", "start_time": "2020-10-15T20:01:19.114073Z" } }, "outputs": [], "source": [ "def is_integer_square(n: int) -> bool:\n", " sqrt_n = math.sqrt(n)\n", " return int(sqrt_n)**2 == n" ] }, { "cell_type": "code", "execution_count": 127, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:01:27.334054Z", "start_time": "2020-10-15T20:01:27.330941Z" } }, "outputs": [], "source": [ "assert not is_integer_square(24)\n", "assert is_integer_square(25)\n", "assert not is_integer_square(26)" ] }, { "cell_type": "code", "execution_count": 144, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:17:13.091146Z", "start_time": "2020-10-15T20:17:13.084391Z" } }, "outputs": [], "source": [ "def is_goldbach(n: int, primes: List[int], verbose: bool=True) -> bool:\n", " # n has to be odd to be Goldbach\n", " if n % 2 == 0:\n", " return False\n", " # n has to not be prime\n", " if n in primes:\n", " return False\n", " # now we can test possible candidate primes\n", " for p in primes:\n", " if p >= n:\n", " return False\n", " # if n = p + 2*(a square)\n", " remainder = n - p\n", " if remainder % 2 != 0:\n", " continue\n", " candidate_square = remainder // 2\n", " if is_integer_square(candidate_square):\n", " i = int(math.sqrt(candidate_square))\n", " if verbose: print(f\"n = {n} was found to satisfy Goldbach's property with prime p = {p} and i = {i} (n = p + 2 i²)\")\n", " return True\n", " return False" ] }, { "cell_type": "code", "execution_count": 145, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:17:21.307560Z", "start_time": "2020-10-15T20:17:21.242168Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 9 was found to satisfy Goldbach's property with prime p = 7 and i = 1 (n = p + 2 i²)\n", "n = 15 was found to satisfy Goldbach's property with prime p = 7 and i = 2 (n = p + 2 i²)\n", "n = 21 was found to satisfy Goldbach's property with prime p = 3 and i = 3 (n = p + 2 i²)\n", "n = 25 was found to satisfy Goldbach's property with prime p = 7 and i = 3 (n = p + 2 i²)\n", "n = 27 was found to satisfy Goldbach's property with prime p = 19 and i = 2 (n = p + 2 i²)\n", "n = 33 was found to satisfy Goldbach's property with prime p = 31 and i = 1 (n = p + 2 i²)\n", "n = 35 was found to satisfy Goldbach's property with prime p = 3 and i = 4 (n = p + 2 i²)\n", "n = 39 was found to satisfy Goldbach's property with prime p = 7 and i = 4 (n = p + 2 i²)\n", "n = 45 was found to satisfy Goldbach's property with prime p = 13 and i = 4 (n = p + 2 i²)\n", "n = 49 was found to satisfy Goldbach's property with prime p = 17 and i = 4 (n = p + 2 i²)\n", "For numbers n = 1 ... 50 we found 10 numbers satisfying Goldbach's conjecture.\n" ] } ], "source": [ "count = 0\n", "max_n = 50\n", "for n in range(1, max_n + 1):\n", " if is_goldbach(n, primes_upto_1e7, verbose=True):\n", " count += 1\n", "print(f\"For numbers n = 1 ... {max_n} we found {count} numbers satisfying Goldbach's conjecture.\")" ] }, { "cell_type": "code", "execution_count": 146, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:17:29.494758Z", "start_time": "2020-10-15T20:17:29.491837Z" } }, "outputs": [], "source": [ "def find_smallest_odd_composite_non_Goldbach_number(primes: List[int]) -> int:\n", " n = 7\n", " max_n = max(primes)\n", " while n <= max_n:\n", " n += 2\n", " # let's try all the odd numbers from 9\n", " if n in primes:\n", " continue\n", " # we skip the primes\n", " if not is_goldbach(n, primes, verbose=False):\n", " return n\n", " raise ValueError(f\"Not enough prime numbers in the list (max = {max_n}), no counter example was found...\")" ] }, { "cell_type": "code", "execution_count": 147, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:18:26.944704Z", "start_time": "2020-10-15T20:18:03.257824Z" } }, "outputs": [ { "data": { "text/plain": [ "5777" ] }, "execution_count": 147, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_smallest_odd_composite_non_Goldbach_number(primes_upto_1e7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It was that fast, about 24 seconds, but it's enough.\n", "There is surly plenty of solutions to solve this problem faster, but I don't care." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 47: distinct primes factors](https://projecteuler.net/problem=47)" ] }, { "cell_type": "code", "execution_count": 183, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:49:42.388667Z", "start_time": "2020-10-15T20:49:42.384938Z" } }, "outputs": [], "source": [ "def how_many_times_x_divides_y(x: int, y: int) -> int:\n", " c = 0\n", " while x % y == 0:\n", " x = x // y\n", " c += 1\n", " return c" ] }, { "cell_type": "code", "execution_count": 187, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:51:01.616269Z", "start_time": "2020-10-15T20:51:01.613565Z" } }, "outputs": [], "source": [ "assert 2 == how_many_times_x_divides_y(100, 10)\n", "assert 2 == how_many_times_x_divides_y(644, 2)\n", "assert 1 == how_many_times_x_divides_y(644, 7)\n", "assert 1 == how_many_times_x_divides_y(644, 23)\n", "assert 0 == how_many_times_x_divides_y(644, 39)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:47:44.201517Z", "start_time": "2020-10-15T20:47:44.186637Z" } }, "outputs": [], "source": [ "from functools import lru_cache\n", "from typing import Tuple\n", "\n", "@lru_cache(maxsize=None)\n", "def number_of_distinct_prime_factors(n: int, primes: Tuple[int]) -> int:\n", " return len([p for p in primes if p <= n and n % p == 0])" ] }, { "cell_type": "code", "execution_count": 192, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:54:50.364601Z", "start_time": "2020-10-15T20:54:50.358718Z" } }, "outputs": [], "source": [ "def distinct_prime_factors(n: int, primes: Tuple[int]) -> List[int]:\n", " prime_factors = [p for p in primes if p <= n and n % p == 0]\n", " return prime_factors\n", "\n", "def str_prime_decomposition(n: int, primes: Tuple[int]) -> str:\n", " prime_factors = distinct_prime_factors(n, primes)\n", " prime_decomposition = {\n", " p: how_many_times_x_divides_y(n, p) for p in prime_factors\n", " }\n", " return ' * '.join(\n", " f\"{p}**{power}\" if power >= 2 else f\"{p}\"\n", " for (p, power) in prime_decomposition.items()\n", " )\n", " " ] }, { "cell_type": "code", "execution_count": 168, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:42:58.886814Z", "start_time": "2020-10-15T20:42:58.884374Z" } }, "outputs": [], "source": [ "primes_upto_1e7 = tuple(primes_upto_1e7)" ] }, { "cell_type": "code", "execution_count": 169, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:43:06.681825Z", "start_time": "2020-10-15T20:43:06.643501Z" } }, "outputs": [], "source": [ "assert 2 == number_of_distinct_prime_factors(14, primes_upto_1e7)\n", "assert 2 == number_of_distinct_prime_factors(15, primes_upto_1e7)" ] }, { "cell_type": "code", "execution_count": 195, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:56:48.768150Z", "start_time": "2020-10-15T20:56:48.728582Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "14 = 2 * 7\n", "15 = 3 * 5\n" ] } ], "source": [ "for n in [14, 15]:\n", " print(f\"{n} = {str_prime_decomposition(n, primes_upto_1e7)}\")" ] }, { "cell_type": "code", "execution_count": 170, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:43:14.514929Z", "start_time": "2020-10-15T20:43:14.452504Z" } }, "outputs": [], "source": [ "assert 3 == number_of_distinct_prime_factors(644, primes_upto_1e7)\n", "assert 3 == number_of_distinct_prime_factors(645, primes_upto_1e7)\n", "assert 3 == number_of_distinct_prime_factors(646, primes_upto_1e7)" ] }, { "cell_type": "code", "execution_count": 194, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:56:37.732823Z", "start_time": "2020-10-15T20:56:37.653899Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "644 = 2**2 * 7 * 23\n", "645 = 3 * 5 * 43\n", "646 = 2 * 17 * 19\n" ] } ], "source": [ "for n in [644, 645, 646]:\n", " print(f\"{n} = {str_prime_decomposition(n, primes_upto_1e7)}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's find the first number to have $x$ consecutive integers each having $y$ prime factors:" ] }, { "cell_type": "code", "execution_count": 198, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:59:09.786487Z", "start_time": "2020-10-15T20:59:09.778635Z" } }, "outputs": [], "source": [ "def find_first_number_to_have_x_consecutive_int_with_y_prime_factors(max_n: int, x: int, y: int, primes: List[int]) -> int:\n", " n = 1\n", " primes = tuple([p for p in primes if y*p <= max_n])\n", " while n <= max_n:\n", " can_still_be_good = True\n", " number = n\n", " while number < n+x and can_still_be_good:\n", " if number_of_distinct_prime_factors(number, primes) != y:\n", " can_still_be_good = False\n", " # we can skip a few values for n\n", " n = number\n", " number += 1\n", " if can_still_be_good:\n", " print(f\"Proof that n = {n} has x = {x} consecutive integers with each y = {y} distinct prime factors:\")\n", " for i in range(n, n + x):\n", " print(f\" i = {i} has prime factors {distinct_prime_factors(i, primes)}\")\n", " print(f\" Proof: i = {i} == {str_prime_decomposition(i, primes)}\")\n", " return n\n", " n += 1\n", " raise ValueError(f\"Not enough prime numbers in the list (max = {max_n}), no counter example was found...\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's try with $x=y=2$ and $x=y=3$, to check the example given in the problem statement, before trying with $x=y=4$:" ] }, { "cell_type": "code", "execution_count": 199, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:59:19.318639Z", "start_time": "2020-10-15T20:59:19.278711Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Proof that n = 14 has x = 2 consecutive integers with each y = 2 distinct prime factors:\n", " i = 14 has prime factors [2, 7]\n", " Proof: i = 14 == 2 * 7\n", " i = 15 has prime factors [3, 5]\n", " Proof: i = 15 == 3 * 5\n" ] }, { "data": { "text/plain": [ "14" ] }, "execution_count": 199, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_first_number_to_have_x_consecutive_int_with_y_prime_factors(100, 2, 2, primes_upto_1e7)" ] }, { "cell_type": "code", "execution_count": 200, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T20:59:27.771193Z", "start_time": "2020-10-15T20:59:27.728910Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Proof that n = 644 has x = 3 consecutive integers with each y = 3 distinct prime factors:\n", " i = 644 has prime factors [2, 7, 23]\n", " Proof: i = 644 == 2**2 * 7 * 23\n", " i = 645 has prime factors [3, 5, 43]\n", " Proof: i = 645 == 3 * 5 * 43\n", " i = 646 has prime factors [2, 17, 19]\n", " Proof: i = 646 == 2 * 17 * 19\n" ] }, { "data": { "text/plain": [ "644" ] }, "execution_count": 200, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_first_number_to_have_x_consecutive_int_with_y_prime_factors(1000, 3, 3, primes_upto_1e7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now to answer the problem, let's compute for $x=y=4$:" ] }, { "cell_type": "code", "execution_count": 201, "metadata": { "ExecuteTime": { "end_time": "2020-10-15T21:00:06.031801Z", "start_time": "2020-10-15T20:59:35.665505Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Proof that n = 134043 has x = 4 consecutive integers with each y = 4 distinct prime factors:\n", " i = 134043 has prime factors [3, 7, 13, 491]\n", " Proof: i = 134043 == 3 * 7 * 13 * 491\n", " i = 134044 has prime factors [2, 23, 31, 47]\n", " Proof: i = 134044 == 2**2 * 23 * 31 * 47\n", " i = 134045 has prime factors [5, 17, 19, 83]\n", " Proof: i = 134045 == 5 * 17 * 19 * 83\n", " i = 134046 has prime factors [2, 3, 11, 677]\n", " Proof: i = 134046 == 2 * 3**2 * 11 * 677\n", "CPU times: user 30.2 s, sys: 114 ms, total: 30.4 s\n", "Wall time: 30.4 s\n" ] }, { "data": { "text/plain": [ "134043" ] }, "execution_count": 201, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "find_first_number_to_have_x_consecutive_int_with_y_prime_factors(150000, 4, 4, primes_upto_1e7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## [Problem 49: ](https://projecteuler.net/problem=47)\n", "TODO" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "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 }