euler-080-square-root-digital-expansion-20130828.ipynb

{
 "metadata": {
  "name": "euler-080-square-root-digital-expansion-20130828"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.  \n",
      "\n",
      "The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.  \n",
      "\n",
      "For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import sqrt"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "N_DIGITS = 100  # This is the number of digits to sum.\n",
      "N_DIGITS_SQUARED = 2 * (N_DIGITS + 5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "a = int(2 * 10 ** N_DIGITS_SQUARED)\n",
      "a"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sqrt(a)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "1.414213562373095e+105"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "long(sqrt(a))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "1414213562373095104787002847759798204858218373714391208861616932096043069664092695467347475431626131898368L"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "type(2 ** 1000)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "long"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "MAX_ITERATIONS = 10\n",
      "EPSILON = 1\n",
      "TOLERANCE = 1\n",
      "\n",
      "def newton(f, fprime, n):\n",
      "    xold = 1\n",
      "    xold = long(sqrt(n))\n",
      "    for i in range(MAX_ITERATIONS):\n",
      "        denominator = fprime(xold, n)\n",
      "        assert abs(denominator) >= EPSILON, 'too small'\n",
      "        xnew = xold - long(long(f(xold, n))/long(denominator))\n",
      "        # print i, xnew\n",
      "        if abs(xnew-xold) < TOLERANCE:\n",
      "            return xnew\n",
      "        xold = xnew\n",
      "    assert False, 'failed to converge %d, %d' % (i, xnew)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def f(x, n):\n",
      "    return x*x - n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def f_prime(x, n):\n",
      "    return 2*x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print a\n",
      "b = newton(f, f_prime, a)\n",
      "len(str(b)), b, sum((int(c) for c in str(b)[:100])), sum((int(c) for c in str(b)[1:101]))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "(106,\n",
        " 1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735014L,\n",
        " 475,\n",
        " 481)"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(n):\n",
      "    total = 0\n",
      "    for i in range(n + 1):\n",
      "        j = int(sqrt(i))\n",
      "        if j*j == i:\n",
      "            continue\n",
      "        # print i\n",
      "        a = i * 10 ** N_DIGITS_SQUARED\n",
      "        b = newton(f, f_prime, a)\n",
      "        total += sum((int(c) for c in str(b)[:100]))\n",
      "    return total"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 2\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 134 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "475"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 100\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100 loops, best of 3: 11.8 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 13,
       "text": [
        "40886"
       ]
      }
     ],
     "prompt_number": 13
    }
   ],
   "metadata": {}
  }
 ]
}