Euler.12.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#Project Euler\n",
    "###Problem 12: Highly devisible triangular number\n",
    "The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:\n",
    "\n",
    "1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\n",
    "\n",
    "Let us list the factors of the first seven triangle numbers:\n",
    "\n",
    " 1: 1\n",
    " 3: 1,3\n",
    " 6: 1,2,3,6\n",
    "10: 1,2,5,10\n",
    "15: 1,3,5,15\n",
    "21: 1,3,7,21\n",
    "28: 1,2,4,7,14,28\n",
    "We can see that 28 is the first triangle number to have over five divisors.\n",
    "\n",
    "What is the value of the first triangle number to have over five hundred divisors?\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that a triangular number is from the formula of the sum of natural numbers:\n",
    "$$\\frac{N(N+1)}{2}$$\n",
    "Also remember that any number $x$ can be written as a factor of primes:\n",
    "$$x = \\prod_{p \\in P} p^{n_p}$$ with $n_p$ some natural number.\n",
    "Clearly, if we take any combination of these factors and some of the exponents and divide it from the number, some number remains. The amount of unique products that can be taken from combinations of these primes is the amount of divisors asked in the question. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pyecm\n",
    "import numpy as np\n",
    "triangulars = [N*(N+1)//2 for N in range(1,4000)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have number of unique primes in the prime set of any number $x$. For each prime p we can choose to take $n_p + 1$ options of that prime, since it could be chosen not to pick the prime at all. This means there's a total of $$ \\prod_{p \\in P} (1 + n_p) $$ divisors available. This number is exactly equal to the answer, even tough the combination of not picking any prime should be excluded. However, then we would need to add the possibility that the number one is taken (not a prime), so we add one again. So the answer is just fine as is. Now is the time to find the first triangular number whose divisors is higher than 500."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "48\n",
      "8\n",
      "64\n",
      "64\n",
      "16\n",
      "24\n",
      "24\n",
      "48\n",
      "96\n",
      "64\n",
      "16\n",
      "16\n",
      "32\n",
      "16\n",
      "48\n",
      "144\n",
      "48\n",
      "16\n",
      "8\n",
      "16\n",
      "64\n",
      "16\n",
      "4\n",
      "64\n",
      "288\n",
      "36\n",
      "16\n",
      "16\n",
      "16\n",
      "32\n",
      "32\n",
      "24\n",
      "36\n",
      "24\n",
      "16\n",
      "64\n",
      "32\n",
      "12\n",
      "24\n",
      "80\n",
      "40\n",
      "18\n",
      "36\n",
      "16\n",
      "64\n",
      "32\n",
      "8\n",
      "48\n",
      "24\n",
      "12\n",
      "48\n",
      "64\n",
      "32\n",
      "16\n",
      "32\n",
      "64\n",
      "32\n",
      "16\n",
      "32\n",
      "192\n",
      "48\n",
      "4\n",
      "8\n",
      "24\n",
      "24\n",
      "32\n",
      "16\n",
      "16\n",
      "96\n",
      "48\n",
      "16\n",
      "80\n",
      "80\n",
      "16\n",
      "48\n",
      "48\n",
      "16\n",
      "40\n",
      "20\n",
      "48\n",
      "192\n",
      "32\n",
      "8\n",
      "16\n",
      "32\n",
      "8\n",
      "24\n",
      "96\n",
      "16\n",
      "16\n",
      "32\n",
      "16\n",
      "16\n",
      "32\n",
      "32\n",
      "72\n",
      "72\n",
      "8\n",
      "8\n",
      "48\n",
      "48\n",
      "32\n",
      "32\n",
      "40\n",
      "160\n",
      "32\n",
      "8\n",
      "64\n",
      "32\n",
      "8\n",
      "32\n",
      "48\n",
      "24\n",
      "24\n",
      "48\n",
      "64\n",
      "32\n",
      "8\n",
      "4\n",
      "64\n",
      "64\n",
      "8\n",
      "24\n",
      "48\n",
      "48\n",
      "24\n",
      "16\n",
      "48\n",
      "96\n",
      "32\n",
      "16\n",
      "64\n",
      "64\n",
      "8\n",
      "32\n",
      "288\n",
      "36\n",
      "8\n",
      "16\n",
      "32\n",
      "48\n",
      "12\n",
      "8\n",
      "48\n",
      "96\n",
      "48\n",
      "24\n",
      "16\n",
      "16\n",
      "72\n",
      "72\n",
      "32\n",
      "32\n",
      "16\n",
      "16\n",
      "32\n",
      "64\n",
      "16\n",
      "24\n",
      "144\n",
      "48\n",
      "32\n",
      "16\n",
      "16\n",
      "64\n",
      "16\n",
      "4\n",
      "60\n",
      "60\n",
      "8\n",
      "32\n",
      "64\n",
      "32\n",
      "24\n",
      "36\n",
      "36\n",
      "36\n",
      "24\n",
      "24\n",
      "96\n",
      "32\n",
      "8\n",
      "16\n",
      "32\n",
      "96\n",
      "96\n",
      "16\n",
      "8\n",
      "16\n",
      "32\n",
      "16\n",
      "48\n",
      "96\n",
      "8\n",
      "24\n",
      "96\n",
      "32\n",
      "32\n",
      "32\n",
      "84\n",
      "168\n",
      "16\n",
      "4\n",
      "24\n",
      "48\n",
      "16\n",
      "16\n",
      "24\n",
      "12\n",
      "16\n",
      "48\n",
      "48\n",
      "128\n",
      "32\n",
      "8\n",
      "64\n",
      "32\n",
      "4\n",
      "16\n",
      "128\n",
      "32\n",
      "12\n",
      "24\n",
      "48\n",
      "144\n",
      "24\n",
      "8\n",
      "32\n",
      "16\n",
      "16\n",
      "48\n",
      "60\n",
      "40\n",
      "48\n",
      "48\n",
      "16\n",
      "32\n",
      "16\n",
      "8\n",
      "120\n",
      "120\n",
      "8\n",
      "16\n",
      "32\n",
      "32\n",
      "32\n",
      "16\n",
      "64\n",
      "144\n",
      "72\n",
      "16\n",
      "16\n",
      "16\n",
      "4\n",
      "32\n",
      "192\n",
      "24\n",
      "12\n",
      "12\n",
      "16\n",
      "32\n",
      "16\n",
      "16\n",
      "96\n",
      "96\n",
      "16\n",
      "48\n",
      "96\n",
      "32\n",
      "32\n",
      "16\n",
      "12\n",
      "24\n",
      "8\n",
      "12\n",
      "144\n",
      "96\n",
      "16\n",
      "16\n",
      "64\n",
      "64\n",
      "16\n",
      "24\n",
      "24\n",
      "48\n",
      "48\n",
      "16\n",
      "48\n",
      "96\n",
      "64\n",
      "32\n",
      "16\n",
      "16\n",
      "32\n",
      "32\n",
      "40\n",
      "80\n",
      "32\n",
      "8\n",
      "48\n",
      "48\n",
      "8\n",
      "24\n",
      "72\n",
      "48\n",
      "32\n",
      "16\n",
      "8\n",
      "16\n",
      "16\n",
      "32\n",
      "192\n",
      "48\n",
      "4\n",
      "32\n",
      "64\n",
      "16\n",
      "32\n",
      "16\n",
      "24\n",
      "120\n",
      "40\n",
      "8\n",
      "16\n",
      "96\n",
      "24\n",
      "8\n",
      "64\n",
      "32\n",
      "24\n",
      "24\n",
      "24\n",
      "96\n",
      "16\n",
      "16\n",
      "96\n",
      "48\n",
      "8\n",
      "24\n",
      "96\n",
      "32\n",
      "16\n",
      "8\n",
      "32\n",
      "128\n",
      "32\n",
      "8\n",
      "32\n",
      "64\n",
      "24\n",
      "24\n",
      "24\n",
      "24\n",
      "32\n",
      "64\n",
      "32\n",
      "24\n",
      "24\n",
      "8\n",
      "80\n",
      "80\n",
      "6\n",
      "24\n",
      "48\n",
      "24\n",
      "48\n",
      "96\n",
      "48\n",
      "24\n",
      "16\n",
      "8\n",
      "16\n",
      "16\n",
      "8\n",
      "64\n",
      "128\n",
      "32\n",
      "16\n",
      "16\n",
      "48\n",
      "144\n",
      "48\n",
      "16\n",
      "72\n",
      "72\n",
      "8\n",
      "8\n",
      "48\n",
      "24\n",
      "16\n",
      "16\n",
      "24\n",
      "144\n",
      "24\n",
      "16\n",
      "64\n",
      "32\n",
      "8\n",
      "16\n",
      "144\n",
      "72\n",
      "48\n",
      "48\n",
      "32\n",
      "64\n",
      "32\n",
      "8\n",
      "32\n",
      "64\n",
      "32\n",
      "48\n",
      "24\n",
      "8\n",
      "8\n",
      "16\n",
      "48\n",
      "96\n",
      "16\n",
      "8\n",
      "96\n",
      "96\n",
      "16\n",
      "32\n",
      "80\n",
      "60\n",
      "24\n",
      "16\n",
      "16\n",
      "32\n",
      "64\n",
      "32\n",
      "96\n",
      "48\n",
      "8\n",
      "32\n",
      "32\n",
      "16\n",
      "24\n",
      "24\n",
      "64\n",
      "128\n",
      "16\n",
      "8\n",
      "64\n",
      "128\n",
      "16\n",
      "12\n",
      "36\n",
      "12\n",
      "24\n",
      "96\n",
      "32\n",
      "16\n",
      "16\n",
      "16\n",
      "112\n",
      "56\n",
      "16\n",
      "32\n",
      "32\n",
      "16\n",
      "8\n",
      "8\n",
      "12\n",
      "144\n",
      "48\n",
      "4\n",
      "24\n",
      "24\n",
      "8\n",
      "32\n",
      "128\n",
      "64\n",
      "24\n",
      "36\n",
      "48\n",
      "64\n",
      "32\n",
      "24\n",
      "144\n",
      "72\n",
      "6\n",
      "20\n",
      "80\n",
      "64\n",
      "64\n",
      "32\n",
      "40\n",
      "40\n",
      "16\n",
      "8\n",
      "24\n",
      "48\n",
      "8\n",
      "16\n",
      "96\n",
      "48\n",
      "32\n",
      "16\n",
      "32\n",
      "96\n",
      "24\n",
      "16\n",
      "64\n",
      "64\n",
      "8\n",
      "16\n",
      "32\n",
      "24\n",
      "96\n",
      "32\n",
      "12\n",
      "24\n",
      "16\n",
      "32\n",
      "64\n",
      "16\n",
      "4\n",
      "24\n",
      "288\n",
      "96\n",
      "16\n",
      "16\n",
      "16\n",
      "48\n",
      "48\n",
      "8\n",
      "54\n",
      "54\n",
      "8\n",
      "32\n",
      "32\n",
      "8\n",
      "16\n",
      "64\n",
      "128\n",
      "128\n",
      "32\n",
      "8\n",
      "32\n",
      "32\n",
      "16\n",
      "32\n",
      "24\n",
      "24\n",
      "24\n",
      "12\n",
      "8\n",
      "48\n",
      "72\n",
      "24\n",
      "80\n",
      "160\n",
      "16\n",
      "24\n",
      "96\n",
      "16\n",
      "8\n",
      "8\n",
      "24\n",
      "48\n",
      "16\n",
      "16\n",
      "80\n",
      "160\n",
      "16\n",
      "16\n",
      "64\n",
      "32\n",
      "64\n",
      "32\n",
      "16\n",
      "48\n",
      "12\n",
      "24\n",
      "144\n",
      "72\n",
      "12\n",
      "8\n",
      "32\n",
      "16\n",
      "12\n",
      "12\n",
      "36\n",
      "144\n",
      "32\n",
      "16\n",
      "64\n",
      "64\n",
      "16\n",
      "64\n",
      "96\n",
      "12\n",
      "8\n",
      "16\n",
      "32\n",
      "64\n",
      "32\n",
      "16\n",
      "144\n",
      "144\n",
      "8\n",
      "8\n",
      "32\n",
      "64\n",
      "32\n",
      "8\n",
      "24\n",
      "72\n",
      "36\n",
      "24\n",
      "64\n",
      "32\n",
      "8\n",
      "32\n",
      "80\n",
      "20\n",
      "16\n",
      "64\n",
      "64\n",
      "64\n",
      "16\n",
      "4\n",
      "24\n",
      "96\n",
      "48\n",
      "72\n",
      "48\n",
      "16\n",
      "48\n",
      "24\n",
      "16\n",
      "64\n",
      "32\n",
      "16\n",
      "48\n",
      "24\n",
      "8\n",
      "16\n",
      "96\n",
      "96\n",
      "16\n",
      "8\n",
      "8\n",
      "56\n",
      "28\n",
      "8\n",
      "96\n",
      "96\n",
      "24\n",
      "24\n",
      "32\n",
      "32\n",
      "48\n",
      "96\n",
      "48\n",
      "48\n",
      "32\n",
      "8\n",
      "32\n",
      "64\n",
      "8\n",
      "24\n",
      "96\n",
      "32\n",
      "32\n",
      "32\n",
      "32\n",
      "32\n",
      "16\n",
      "8\n",
      "48\n",
      "48\n",
      "8\n",
      "72\n",
      "72\n",
      "8\n",
      "8\n",
      "16\n",
      "80\n",
      "120\n",
      "24\n",
      "16\n",
      "32\n",
      "64\n",
      "32\n",
      "16\n",
      "24\n",
      "48\n",
      "96\n",
      "24\n",
      "16\n",
      "32\n",
      "8\n",
      "8\n",
      "128\n",
      "64\n",
      "6\n",
      "24\n",
      "96\n",
      "24\n",
      "8\n",
      "24\n",
      "36\n",
      "96\n",
      "64\n",
      "16\n",
      "48\n",
      "24\n",
      "16\n",
      "32\n",
      "56\n",
      "56\n",
      "16\n",
      "16\n",
      "16\n",
      "48\n",
      "72\n",
      "12\n",
      "48\n",
      "72\n",
      "6\n",
      "16\n",
      "96\n",
      "72\n",
      "60\n",
      "20\n",
      "16\n",
      "64\n",
      "32\n",
      "32\n",
      "64\n",
      "16\n",
      "4\n",
      "24\n",
      "72\n",
      "24\n",
      "32\n",
      "16\n",
      "32\n",
      "128\n",
      "16\n",
      "8\n",
      "120\n",
      "240\n",
      "16\n",
      "8\n",
      "16\n",
      "16\n",
      "40\n",
      "60\n",
      "72\n",
      "96\n",
      "16\n",
      "8\n",
      "32\n",
      "48\n",
      "12\n",
      "16\n",
      "128\n",
      "32\n",
      "24\n",
      "48\n",
      "16\n",
      "32\n",
      "32\n",
      "8\n",
      "24\n",
      "24\n",
      "16\n",
      "48\n",
      "48\n",
      "64\n",
      "64\n",
      "48\n",
      "72\n",
      "48\n",
      "8\n",
      "4\n",
      "64\n",
      "128\n",
      "16\n",
      "32\n",
      "96\n",
      "48\n",
      "16\n",
      "16\n",
      "16\n",
      "24\n",
      "24\n",
      "16\n",
      "64\n",
      "32\n",
      "8\n",
      "64\n",
      "128\n",
      "16\n",
      "12\n",
      "24\n",
      "72\n",
      "144\n",
      "16\n",
      "4\n",
      "16\n",
      "32\n",
      "16\n",
      "40\n",
      "200\n",
      "80\n",
      "32\n",
      "32\n",
      "16\n",
      "32\n",
      "16\n",
      "16\n",
      "144\n",
      "72\n",
      "16\n",
      "32\n",
      "64\n",
      "16\n",
      "24\n",
      "24\n",
      "16\n",
      "144\n",
      "36\n",
      "8\n",
      "64\n",
      "64\n",
      "16\n",
      "16\n",
      "24\n",
      "12\n",
      "16\n",
      "64\n",
      "64\n",
      "32\n",
      "16\n",
      "16\n",
      "128\n",
      "128\n",
      "16\n",
      "48\n",
      "72\n",
      "24\n",
      "16\n",
      "8\n",
      "24\n",
      "48\n",
      "48\n",
      "24\n",
      "24\n",
      "24\n",
      "8\n",
      "32\n",
      "64\n",
      "64\n",
      "32\n",
      "16\n",
      "32\n",
      "128\n",
      "32\n",
      "4\n",
      "48\n",
      "96\n",
      "8\n",
      "8\n",
      "16\n",
      "16\n",
      "48\n",
      "72\n",
      "90\n",
      "60\n",
      "16\n",
      "32\n",
      "128\n",
      "32\n",
      "8\n",
      "24\n",
      "72\n",
      "24\n",
      "8\n",
      "16\n",
      "16\n",
      "64\n",
      "64\n",
      "24\n",
      "144\n",
      "48\n",
      "8\n",
      "16\n",
      "32\n",
      "32\n",
      "32\n",
      "64\n",
      "48\n",
      "36\n",
      "12\n",
      "8\n",
      "96\n",
      "96\n",
      "8\n",
      "8\n",
      "48\n",
      "96\n",
      "96\n",
      "24\n",
      "8\n",
      "16\n",
      "32\n",
      "16\n",
      "24\n",
      "96\n",
      "32\n",
      "64\n",
      "128\n",
      "16\n",
      "8\n",
      "8\n",
      "48\n",
      "96\n",
      "16\n",
      "8\n",
      "24\n",
      "72\n",
      "24\n",
      "64\n",
      "96\n",
      "12\n",
      "16\n",
      "16\n",
      "8\n",
      "48\n",
      "48\n",
      "16\n",
      "80\n",
      "80\n",
      "16\n",
      "32\n",
      "64\n",
      "32\n",
      "32\n",
      "16\n",
      "24\n",
      "96\n",
      "16\n",
      "4\n",
      "32\n",
      "64\n",
      "24\n",
      "36\n",
      "96\n",
      "64\n",
      "16\n",
      "32\n",
      "64\n",
      "32\n",
      "8\n",
      "8\n",
      "144\n",
      "144\n",
      "16\n",
      "16\n",
      "16\n",
      "32\n",
      "32\n",
      "8\n",
      "28\n",
      "210\n",
      "60\n",
      "24\n",
      "48\n",
      "32\n",
      "8\n",
      "24\n",
      "144\n",
      "48\n",
      "48\n",
      "48\n",
      "32\n",
      "32\n",
      "16\n",
      "16\n",
      "64\n",
      "64\n",
      "8\n",
      "12\n",
      "24\n",
      "8\n",
      "32\n",
      "64\n",
      "24\n",
      "48\n",
      "16\n",
      "16\n",
      "128\n",
      "64\n",
      "8\n",
      "16\n",
      "160\n"
     ]
    }
   ],
   "source": [
    "for i,x in [(factors.factors[x],x) for x in triangulars]:\n",
    "    print(np.prod([1+i[p] for p in i]))\n",
    "    if np.prod([1+i[p] for p in i]) > 500:\n",
    "        print('found number',x)\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}