euler-047-distinct-primes-factors-20170110.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Project Euler](https://projecteuler.net/)\n",
    "\n",
    "#### Distinct primes factors\n",
    "\n",
    "\n",
    "[Problem 47](https://projecteuler.net/problem=47)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first two consecutive numbers to have two distinct prime factors are:  \n",
    "\n",
    "> 14 = 2 × 7  \n",
    "> 15 = 3 × 5\n",
    "\n",
    "The first three consecutive numbers to have three distinct prime factors are:  \n",
    "\n",
    "> 644 = 2² × 7 × 23   \n",
    "> 645 = 3 × 5 × 43  \n",
    "> 646 = 2 × 17 × 19.\n",
    "\n",
    "Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from euler import canonical_decomposition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 2, 7: 1, 23: 1}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = canonical_decomposition(644)\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from itertools import count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    for i in count(2):\n",
    "        for j in range(i, i + n):\n",
    "            if len(canonical_decomposition(j)) != n:\n",
    "                break\n",
    "        else:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.77 s per loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "134043"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 4\n",
    "%timeit foo(n)\n",
    "foo(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache(n)\n",
    "def n_distinct_prime_factors(x):\n",
    "    return len(canonical_decomposition(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    for i in count(2):\n",
    "        for j in range(i, i + n):\n",
    "            if n_distinct_prime_factors(j) != n:\n",
    "                break\n",
    "        else:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.56 s per loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "134043"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 4\n",
    "%timeit foo(n)\n",
    "foo(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    i = 2\n",
    "    while True:\n",
    "        for j in range(i, i + n):\n",
    "            if len(canonical_decomposition(j)) != n:\n",
    "                i = j + 1\n",
    "                break\n",
    "        else:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.49 s per loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "134043"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 4\n",
    "%timeit foo(n)\n",
    "foo(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, -1, -2]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = 2\n",
    "list(range(i-1, i-n-1, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo(n):\n",
    "    i = 2\n",
    "    while True:\n",
    "        if n_distinct_prime_factors(i) != n:\n",
    "            i += n\n",
    "            continue\n",
    "\n",
    "        # Search backwards.\n",
    "        for j in range(i-1, i-n-1, -1):\n",
    "            if j < 2 or n_distinct_prime_factors(j) != n:\n",
    "                first_good = j + 1\n",
    "                break\n",
    "        else:\n",
    "            first_good = j\n",
    "\n",
    "        # Search forwards.\n",
    "        for j in range(i+1, first_good+n):\n",
    "            if n_distinct_prime_factors(j) != n:\n",
    "                i = j + n\n",
    "                break\n",
    "        else:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 479 ms per loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "134043"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 4\n",
    "%timeit foo(n)\n",
    "foo(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I like cells 8 and 9 the most. They have the best combination of readability and speed.\n",
    "\n",
    "Cell 11 is a little faster, but the while loop is ugly.\n",
    "\n",
    "Cell 14 is fast, but makes my head hurt."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}