euler-104-pandigital-fibonacci-ends-20170210.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Project Euler](https://projecteuler.net/)\n",
    "\n",
    "#### Pandigital Fibonacci ends\n",
    "\n",
    "\n",
    "[Problem 104](https://projecteuler.net/problem=104)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Fibonacci sequence is defined by the recurrence relation:\n",
    "\n",
    "> F<sub>n</sub> = F<sub>n−1</sub> + F<sub>n−2</sub>, where F<sub>1</sub> = 1 and F<sub>2</sub> = 1.\n",
    "\n",
    "It turns out that F<sub>541</sub>, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F<sub>2749</sub>, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.\n",
    "\n",
    "Given that F<sub>*k*</sub> is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find *k*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def fibonacci():\n",
    "    a, b = 0, 1\n",
    "    while True:\n",
    "        yield a\n",
    "        a, b = b, a+b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0),\n",
       " (1, 1),\n",
       " (2, 1),\n",
       " (3, 2),\n",
       " (4, 3),\n",
       " (5, 5),\n",
       " (6, 8),\n",
       " (7, 13),\n",
       " (8, 21),\n",
       " (9, 34)]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import islice\n",
    "list(islice(enumerate(fibonacci()), 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('293487109',\n",
       " '458723049',\n",
       " {'0', '1', '2', '3', '4', '7', '8', '9'},\n",
       " {'1', '2', '3', '4', '7', '8', '9'},\n",
       " 7,\n",
       " 5)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i = 29348710948704982734509283745029348572309458723049\n",
    "s = str(i)\n",
    "s0 = s[:9]\n",
    "s1 = s[-9:]\n",
    "s0, s1, set(s0), set(s0) - set('0'), len(set(s0) - set('0')), len(set(s0[:5]) - set('0'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_pandigital(s):\n",
    "    return len(set(s) - set('0')) == 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo():\n",
    "    for i, f in enumerate(fibonacci()):\n",
    "        s = str(f)\n",
    "        if is_pandigital(s[-9:]):\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "541"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo():\n",
    "    for i, f in enumerate(fibonacci()):\n",
    "        s = str(f)\n",
    "        if is_pandigital(s[:9]):\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2749"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo():\n",
    "    for i, f in enumerate(fibonacci()):\n",
    "        s = str(f)\n",
    "        if is_pandigital(s[:9]) and is_pandigital(s[-9:]):\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# foo()\n",
    "\n",
    "# This took far too long, so I had to refactor for speed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def foo():\n",
    "    n = 10 ** 9\n",
    "    for i, f in enumerate(fibonacci()):\n",
    "        if is_pandigital(str(f % n)) and is_pandigital(str(f)[:9]):\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 32.3 s per loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "329468"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%timeit foo()\n",
    "foo()"
   ]
  }
 ],
 "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
}