Euler 088 - Product-sum numbers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euler Problem 88\n",
    "================\n",
    "\n",
    "A natural number, $N$, that can be written as the sum and product of a given set of at least two natural numbers, \n",
    "$\\{a_1, a_2, \\ldots, a_k\\}$ is called a product-sum number: \n",
    "$$N = a_1 + a_2 + \\cdots + a_k = a_1 \\times a_2 \\times \\cdots \\times a_k.$$\n",
    "\n",
    "For example, $6 = 1 + 2 + 3 = 1 \\times 2 \\times 3$.\n",
    "\n",
    "For a given set of size, $k$, we shall call the smallest $N$ with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, $k = 2, 3, 4, 5,$ and 6 are as follows.\n",
    "\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",
    "\n",
    "Hence for $2\\le k\\le 6$, the sum of all the minimal product-sum numbers is $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 \\le k \\le 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 \\le k \\le 12000$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7587457\n"
     ]
    }
   ],
   "source": [
    "N = 12000\n",
    "a = [2*N+1] * (N+1)\n",
    "a[1] = 1\n",
    "def gen(maxprod, start=2):\n",
    "    for i in range(start, maxprod+1):\n",
    "        yield (i,)\n",
    "    for i in range(start, int(maxprod**0.5) + 1):\n",
    "        for v in gen(maxprod//i, i):\n",
    "            yield (i,) + v\n",
    "\n",
    "def product(v):\n",
    "    pi = 1\n",
    "    for x in v:\n",
    "        pi *= x\n",
    "    return pi\n",
    "\n",
    "for v in gen(2*N):\n",
    "    pi = product(v)\n",
    "    k = pi - sum(v) + len(v)\n",
    "    if k <= N and a[k] > pi:\n",
    "        a[k] = pi\n",
    "\n",
    "print(sum(set(a[2:])))"
   ]
  },
  {
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}