euler-problem-88.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Euler-Problem 88: *Product-sum numbers*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to solve [Euler-Problem 88](https://projecteuler.net/problem=88)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A natural number, N, that can be written as the sum and product of a given set of at\n",
    "least two natural numbers,\n",
    "$\\{a_1, a_2, … , a_k\\}$\n",
    "is called a product-sum number: \n",
    "$N = a_1 + a_2 + \\dots + a_k = a_1 · a_2 · … · a_k.$\n",
    "\n",
    "For example, $6 = 1 + 2 + 3 = 1 · 2 · 3$.\n",
    "\n",
    "For a given set of size, $k$, we shall call the smallest $N$ with this property\n",
    "a minimal product-sum number.\n",
    "The minimal product-sum numbers for sets of size, $k = 2, 3, 4, 5,$ and $6$ are as follows.\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "    k=2&: ~~ 4 = 2 · 2 = 2 + 2 \\\\\n",
    "    k=3&: ~~ 6 = 1 · 2 · 3 = 1 + 2 + 3 \\\\\n",
    "    k=4&: ~~ 8 = 1 · 1 · 2 · 4 = 1 + 1 + 2 + 4 \\\\\n",
    "    k=5&: ~~ 8 = 1 · 1 · 2 · 2 · 2 = 1 + 1 + 2 + 2 + 2 \\\\\n",
    "    k=6&: ~~ 12 = 1 · 1 · 1 · 1 · 2 · 6 = 1 + 1 + 1 + 1 + 2 + 6 \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Hence for $2 ≤ k ≤ 6$, the sum of all the minimal product-sum numbers is\n",
    "$4+6+8+12 = 30$; note that $8$ is only counted once in the sum.\n",
    "\n",
    "In fact, as the complete set of minimal product-sum numbers for $2≤k≤12$ is $\\{4, 6, 8, 12, 15, 16\\}$,\n",
    "the sum is $61$.\n",
    "\n",
    "What is the sum of all the minimal product-sum numbers for $2≤k≤12000$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prime Sieve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "import operator\n",
    "def prod(iterable):\n",
    "    return reduce(operator.mul, iterable, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prod_str(factors, ones=0) -> str: \n",
    "    return (\"1 * \" * ones) + \" * \".join(str(f) for f in factors)\n",
    "def sum_str(factors, ones=0) -> str: \n",
    "    return (\"1 + \" * ones) + \" + \".join(str(f) for f in factors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_max = int(12000 * 1.4)  # 40% overhead should be more than enough"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some restrictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$N$ cannot be a prime number, since\n",
    "$p = 1 · … · 1 · p < 1 + … + 1 + p$ for every prime number $p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every other $N = p_1 · p_2 · … · p_n$ can be created by just adding enough ones:\n",
    "\n",
    "$N = 1 · … · 1 · p_1 · p_2 · … · p_n = 1 + … + 1 + p_1 + p_2 + … + p_n$\n",
    "\n",
    "The product of two natural number $a_1, a_2 \\geq 2$ is always bigger or equal their sum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course some of those will not be minimal for any $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the possible values for $k$ with which an $N$ can be created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = list(range(2, N_max // 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is of course another possibility"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_and_hash(a):\n",
    "    N = prod(a)\n",
    "    if N > N_max: return False\n",
    "    k = (N - sum(a)) + len(a)\n",
    "    \n",
    "    # try:\n",
    "    #     N_hash[N].add(k)\n",
    "    # except KeyError:\n",
    "    #     N_hash[N] = {k}\n",
    "    try:\n",
    "        k_hash[k].add(N)\n",
    "    except KeyError:\n",
    "        k_hash[k] = {N}\n",
    "    return True\n",
    "\n",
    "def try_numbers(old_a):\n",
    "    for a_i in numbers:\n",
    "        a = old_a + [a_i]\n",
    "        if not calc_and_hash(a): break\n",
    "        try_numbers(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 20.2 s, sys: 34.1 ms, total: 20.2 s\n",
      "Wall time: 20.3 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "# N_hash = {}\n",
    "k_hash = {}\n",
    "for a1 in numbers:\n",
    "    try_numbers([a1]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Okay, this isn't under 10 seconds but my algorithm is not optimized at all and tries almost all combinations at least twice, since I am lazy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2: [4]\n",
      "3: [6]\n",
      "4: [8]\n",
      "5: [8, 9, 10]\n",
      "6: [12]\n",
      "7: [12, 14]\n",
      "8: [12, 16]\n",
      "9: [15, 18]\n",
      "10: [16, 20]\n",
      "11: [16, 18, 22]\n",
      "12: [16, 24]\n",
      "13: [18, 20, 21, 26]\n",
      "14: [20, 28]\n",
      "15: [24, 30]\n",
      "16: [24, 32]\n",
      "17: [24, 25, 27, 34]\n",
      "18: [24, 36]\n",
      "19: [24, 28, 30, 38]\n",
      "20: [28, 40]\n",
      "21: [27, 30, 33, 42]\n",
      "22: [32, 44]\n",
      "23: [30, 32, 36, 46]\n",
      "24: [48]\n",
      "25: [32, 35, 36, 39, 50]\n",
      "26: [32, 36, 52]\n",
      "27: [32, 42, 54]\n",
      "28: [36, 40, 56]\n",
      "29: [36, 40, 45, 58]\n",
      "30: [36, 60]\n",
      "31: [42, 44, 48, 62]\n",
      "32: [40, 44, 64]\n",
      "33: [40, 42, 45, 51, 66]\n",
      "34: [48, 68]\n",
      "35: [48, 54, 70]\n",
      "36: [48, 72]\n",
      "37: [45, 49, 50, 52, 57, 74]\n",
      "38: [48, 52, 76]\n",
      "39: [48, 60, 78]\n",
      "40: [48, 56, 80]\n",
      "41: [48, 50, 54, 55, 56, 63, 82]\n",
      "42: [48, 84]\n",
      "43: [54, 56, 60, 66, 86]\n",
      "44: [60, 88]\n",
      "45: [54, 60, 69, 90]\n",
      "46: [56, 60, 64, 92]\n",
      "47: [54, 56, 64, 72, 94]\n",
      "48: [60, 96]\n",
      "49: [63, 65, 68, 75, 98]\n",
      "50: [60, 64, 68, 100]\n",
      "51: [60, 66, 78, 102]\n",
      "52: [60, 72, 104]\n",
      "53: [63, 64, 66, 70, 72, 81, 106]\n",
      "54: [64, 108]\n",
      "55: [64, 70, 76, 84, 110]\n",
      "56: [64, 72, 76, 112]\n",
      "57: [64, 72, 75, 87, 114]\n",
      "58: [64, 72, 80, 116]\n",
      "59: [70, 80, 90, 118]\n",
      "60: [72, 120]\n",
      "61: [72, 77, 78, 80, 84, 93, 122]\n",
      "62: [72, 84, 124]\n",
      "63: [72, 78, 96, 126]\n",
      "64: [72, 80, 88, 128]\n",
      "65: [72, 75, 81, 85, 88, 99, 130]\n",
      "66: [84, 132]\n",
      "67: [80, 84, 92, 102, 134]\n",
      "68: [80, 84, 92, 136]\n",
      "69: [81, 90, 105, 138]\n",
      "70: [80, 96, 140]\n",
      "71: [80, 88, 90, 96, 108, 142]\n",
      "72: [80, 84, 144]\n",
      "73: [81, 84, 90, 91, 95, 100, 111, 146]\n",
      "74: [84, 88, 100, 148]\n",
      "75: [88, 114, 150]\n",
      "76: [96, 104, 152]\n",
      "77: [90, 100, 104, 117, 154]\n",
      "78: [96, 156]\n",
      "79: [90, 98, 108, 120, 158]\n",
      "80: [108, 160]\n",
      "81: [90, 96, 99, 102, 105, 123, 162]\n",
      "82: [96, 100, 112, 164]\n",
      "83: [96, 102, 112, 126, 166]\n",
      "84: [96, 168]\n",
      "85: [96, 98, 99, 104, 105, 110, 116, 129, 170]\n",
      "86: [96, 100, 108, 116, 172]\n",
      "87: [96, 132, 174]\n",
      "88: [96, 104, 108, 120, 176]\n",
      "89: [96, 100, 104, 108, 115, 120, 135, 178]\n",
      "90: [100, 180]\n",
      "91: [110, 112, 114, 124, 138, 182]\n",
      "92: [112, 124, 184]\n",
      "93: [105, 108, 114, 120, 141, 186]\n",
      "94: [108, 128, 188]\n",
      "95: [108, 110, 112, 128, 144, 190]\n",
      "96: [108, 112, 120, 192]\n",
      "97: [117, 119, 125, 132, 147, 194]\n",
      "98: [108, 112, 120, 132, 196]\n",
      "99: [108, 120, 150, 198]\n",
      "...\n"
     ]
    }
   ],
   "source": [
    "for k in sorted(k_hash):\n",
    "    if 0 < k < 100:\n",
    "        print(f\"{k}: {sorted(k_hash[k])}\")\n",
    "print('...')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_min = {min(N_set) for k, N_set in k_hash.items() if k <= 12000}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to check, that we really found one for all k, otherwise increase `N_max`!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[k for k in range(12000+1) if k not in k_hash]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now calculate the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7587457"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(N_min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Hooray!**"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}