euler-025-1000-digit-fibonacci-number-20130808.ipynb

{
 "metadata": {
  "name": "euler-025-1000-digit-fibonacci-number-20130808"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The Fibonacci sequence is defined by the recurrence relation:  \n",
      "\n",
      "> F<sub>*n*</sub> = F<sub>*n*\u22121</sub> + F<sub>*n*\u22122</sub>, where F<sub>1</sub> = 1 and F<sub>2</sub> = 1.  \n",
      "\n",
      "Hence the first 12 terms will be:  \n",
      "\n",
      "> F<sub>1</sub> = 1  \n",
      "> F<sub>2</sub> = 1  \n",
      "> F<sub>3</sub> = 2  \n",
      "> F<sub>4</sub> = 3  \n",
      "> F<sub>5</sub> = 5  \n",
      "> F<sub>6</sub> = 8  \n",
      "> F<sub>7</sub> = 13  \n",
      "> F<sub>8</sub> = 21  \n",
      "> F<sub>9</sub> = 34  \n",
      "> F<sub>10</sub> = 55  \n",
      "> F<sub>11</sub> = 89  \n",
      "> F<sub>12</sub> = 144  \n",
      "\n",
      "The 12th term, F12, is the first term to contain three digits.  \n",
      "\n",
      "What is the first term in the Fibonacci sequence to contain 1000 digits?  "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import gen_fibonacci, gen_lte, term_of_ndigits_fibonacci, phi"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(gen_lte(gen_fibonacci(), 100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def gen_fib2():\n",
      "    yield 1\n",
      "    for i in gen_fibonacci():\n",
      "        yield i"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(gen_lte(gen_fib2(), 100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def gen_fib3():\n",
      "    yield 0\n",
      "    yield 1\n",
      "    for i in gen_fibonacci():\n",
      "        yield i"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(gen_lte(gen_fib3(), 100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    for i, fib in enumerate(gen_fib2(), 1):\n",
      "        if len(str(fib)) >= n:\n",
      "            return i"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "foo(3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "12"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 1000\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 250 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "4782"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For extra bonus points, directly calculate the number without generating any Fibonacci numbers.  \n",
      "\n",
      "Hint: Read Knuth. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 1000\n",
      "%timeit term_of_ndigits_fibonacci(n)\n",
      "term_of_ndigits_fibonacci(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100000 loops, best of 3: 1.93 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "4782"
       ]
      }
     ],
     "prompt_number": 10
    }
   ],
   "metadata": {}
  }
 ]
}