Euler Project Gursh.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:0bde27d28d9e41f8127839bfad7b4acb67ae3fa69446b2530253886b23c8993f"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "<b>Problem 5</b>\n",
      "\n",
      "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.\n",
      "\n",
      "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from fractions import gcd"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "least_common_multiple = 1\n",
      "for i in range(1,20):\n",
      "    greatest_divisor = gcd(least_common_multiple,i+1)\n",
      "    least_common_multiple = least_common_multiple*(i+1)/greatest_divisor\n",
      "print (least_common_multiple)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "232792560.0\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "https://projecteuler.net/problem=11\n",
      "\n",
      "\n",
      "\n",
      "https://projecteuler.net/problem=15\n",
      "\n",
      "[Can't be bothered this requires a dictionary] https://projecteuler.net/problem=17\n",
      "https://projecteuler.net/problem=18\n",
      "https://projecteuler.net/problem=19"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b>Problem 7</b>\n",
      "\n",
      "By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.\n",
      "\n",
      "What is the 10 001st prime number?\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import sqrt"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def find_n_primes(number_of_primes):\n",
      "    \"This function returns a list of all containing the first n primes\"\n",
      "    i = 2\n",
      "    primelist = []\n",
      "    while(len(primelist) < number_of_primes):\n",
      "        marker = \"Prime\"\n",
      "        for j in range(2,int(sqrt(i))+1):\n",
      "                   if( i%j == 0):\n",
      "                       marker =\"No\"\n",
      "                       break\n",
      "                        \n",
      "        if (marker == \"Prime\" ):\n",
      "            primelist.append(i)\n",
      "            #print(i)\n",
      "        i +=1\n",
      "    return(primelist)\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list = find_n_primes(10001)\n",
      "list[-1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 35,
       "text": [
        "104743"
       ]
      }
     ],
     "prompt_number": 35
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b> Problem 8 </b>\n",
      "\n",
      "The four adjacent digits in the 1000-digit number that have the greatest product are 9 \u00d7 9 \u00d7 8 \u00d7 9 = 5832.\n",
      "<br>\n",
      "73167176531330624919225119674426574742355349194934<br>\n",
      "96983520312774506326239578318016984801869478851843<br>\n",
      "85861560789112949495459501737958331952853208805511<br>\n",
      "12540698747158523863050715693290963295227443043557<br>\n",
      "66896648950445244523161731856403098711121722383113<br>\n",
      "62229893423380308135336276614282806444486645238749<br>\n",
      "30358907296290491560440772390713810515859307960866<br>\n",
      "70172427121883998797908792274921901699720888093776<br>\n",
      "65727333001053367881220235421809751254540594752243<br>\n",
      "52584907711670556013604839586446706324415722155397<br>\n",
      "53697817977846174064955149290862569321978468622482<br>\n",
      "83972241375657056057490261407972968652414535100474<br>\n",
      "82166370484403199890008895243450658541227588666881<br>\n",
      "16427171479924442928230863465674813919123162824586<br>\n",
      "17866458359124566529476545682848912883142607690042<br>\n",
      "24219022671055626321111109370544217506941658960408<br>\n",
      "07198403850962455444362981230987879927244284909188<br>\n",
      "84580156166097919133875499200524063689912560717606<br>\n",
      "05886116467109405077541002256983155200055935729725<br>\n",
      "71636269561882670428252483600823257530420752963450<br>\n",
      "\n",
      "Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_as_string = str(731671765313306249192251196\\\n",
      "74426574742355349194934969835203127745063262395783\\\n",
      "1801698480186947885184385861560789112949495459501737958331952853208805511\\\n",
      "12540698747158523863050715693290963295227443043557\\\n",
      "66896648950445244523161731856403098711121722383113\\\n",
      "62229893423380308135336276614282806444486645238749\\\n",
      "30358907296290491560440772390713810515859307960866\\\n",
      "70172427121883998797908792274921901699720888093776\\\n",
      "65727333001053367881220235421809751254540594752243\\\n",
      "52584907711670556013604839586446706324415722155397\\\n",
      "53697817977846174064955149290862569321978468622482\\\n",
      "83972241375657056057490261407972968652414535100474\\\n",
      "82166370484403199890008895243450658541227588666881\\\n",
      "16427171479924442928230863465674813919123162824586\\\n",
      "17866458359124566529476545682848912883142607690042\\\n",
      "24219022671055626321111109370544217506941658960408\\\n",
      "07198403850962455444362981230987879927244284909188\\\n",
      "84580156166097919133875499200524063689912560717606\\\n",
      "05886116467109405077541002256983155200055935729725\\\n",
      "71636269561882670428252483600823257530420752963450)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "max_product = 0\n",
      "for i in range(len(number_as_string)-13):\n",
      "    product = 1\n",
      "    for j in range(13):\n",
      "        product *= int(number_as_string[i+j])\n",
      "    if (product > max_product):\n",
      "        max_product = product\n",
      "        adjacent_digits = number_as_string[i:i+13]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(max_product, adjacent_digits)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "23514624000 5576689664895\n"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b> Problem 9 </b>\n",
      "\n",
      "A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,\n",
      "a2 + b2 = c2\n",
      "\n",
      "For example, 32 + 42 = 9 + 16 = 25 = 52.\n",
      "\n",
      "There exists exactly one Pythagorean triplet for which a + b + c = 1000.\n",
      "Find the product abc.\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for a in range(1,1000):\n",
      "    for b in range(a+1,1000):\n",
      "        c = 1000 - a - b\n",
      "        if (a**2 + b**2 == c**2):\n",
      "            print(a , b, c)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "200 375 425\n"
       ]
      }
     ],
     "prompt_number": 37
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b> Problem 10 </b>\n",
      "\n",
      "The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.\n",
      "\n",
      "Find the sum of all the primes below two million."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import sqrt\n",
      "def primesum_upto(max_number):\n",
      "    \"This function returns a list of primes upto the input value which is assumed to be positive\"\n",
      "    i = 2\n",
      "    sum_of_primes = 0\n",
      "    while(i < max_number):\n",
      "        marker = \"Prime\"\n",
      "        for j in range(2,int(sqrt(i))+1):\n",
      "                   if( i%j == 0):\n",
      "                       marker =\"No\"\n",
      "                       break\n",
      "                        \n",
      "        if (marker == \"Prime\" ):\n",
      "            sum_of_primes += i\n",
      "        i +=1\n",
      "    return(sum_of_primes)\n",
      "    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "primesum_upto(2*10**6)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "142913828922"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b> Problem 12 </b>\n",
      "\n",
      "The sequence of triangle numbers is generated by adding the natural numbers. <br>\n",
      "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",
      "\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",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import sqrt\n",
      "\n",
      "def triangle_number(n):\n",
      "    \"returns the nth triangle number\"\n",
      "    return(int(n*(n+1)/2))\n",
      "\n",
      "def factorlist(n):\n",
      "    \"Returns a list of all the divisors of the given value n\"\n",
      "    factorslist = [1, n]\n",
      "    for i in range(2,int(sqrt(n))+1):\n",
      "        if (n%i == 0):\n",
      "            factorslist.append(i)\n",
      "            if( i  != int(n/i)):\n",
      "                factorslist.append(int(n/i))\n",
      "    return(factorslist)\n",
      "        \n",
      "        \n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 47
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "number_of_divisors = 0\n",
      "n = 0\n",
      "while(number_of_divisors < 500):\n",
      "    n += 1\n",
      "    number_of_divisors = len(factorlist(triangle_number(n)))\n",
      "    #print(\"\\nn = \",n,\"\\tTriangle Number = \", triangle_number(n),\"\\tNumber of divisors =\", number_of_divisors)\n",
      "    \n",
      "print(\"\\nn = \",n,\"\\tTriangle Number = \", triangle_number(n),\"\\tNumber of divisors =\", number_of_divisors)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "n =  12375 \tTriangle Number =  76576500 \tNumber of divisors = 576\n"
       ]
      }
     ],
     "prompt_number": 70
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b>Problem 13 </b><br>\n",
      "Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.<br><br>\n",
      "37107287533902102798797998220837590246510135740250 <br>\n",
      "46376937677490009712648124896970078050417018260538 <br>\n",
      "74324986199524741059474233309513058123726617309629 <br>\n",
      "91942213363574161572522430563301811072406154908250 <br>\n",
      "23067588207539346171171980310421047513778063246676 <br>\n",
      "89261670696623633820136378418383684178734361726757 <br>\n",
      "28112879812849979408065481931592621691275889832738 <br>\n",
      "44274228917432520321923589422876796487670272189318 <br>\n",
      "47451445736001306439091167216856844588711603153276 <br>\n",
      "70386486105843025439939619828917593665686757934951 <br>\n",
      "62176457141856560629502157223196586755079324193331 <br>\n",
      "64906352462741904929101432445813822663347944758178 <br>\n",
      "92575867718337217661963751590579239728245598838407 <br>\n",
      "58203565325359399008402633568948830189458628227828 <br>\n",
      "80181199384826282014278194139940567587151170094390 <br>\n",
      "35398664372827112653829987240784473053190104293586 <br>\n",
      "86515506006295864861532075273371959191420517255829 <br>\n",
      "71693888707715466499115593487603532921714970056938 <br>\n",
      "54370070576826684624621495650076471787294438377604 <br>\n",
      "53282654108756828443191190634694037855217779295145 <br>\n",
      "36123272525000296071075082563815656710885258350721 <br>\n",
      "45876576172410976447339110607218265236877223636045 <br>\n",
      "17423706905851860660448207621209813287860733969412 <br>\n",
      "81142660418086830619328460811191061556940512689692 <br>\n",
      "51934325451728388641918047049293215058642563049483 <br>\n",
      "62467221648435076201727918039944693004732956340691 <br>\n",
      "15732444386908125794514089057706229429197107928209 <br>\n",
      "55037687525678773091862540744969844508330393682126 <br>\n",
      "18336384825330154686196124348767681297534375946515 <br>\n",
      "80386287592878490201521685554828717201219257766954 <br>\n",
      "78182833757993103614740356856449095527097864797581 <br>\n",
      "16726320100436897842553539920931837441497806860984 <br>\n",
      "48403098129077791799088218795327364475675590848030 <br>\n",
      "87086987551392711854517078544161852424320693150332 <br>\n",
      "59959406895756536782107074926966537676326235447210 <br>\n",
      "69793950679652694742597709739166693763042633987085<br>\n",
      "41052684708299085211399427365734116182760315001271<br>\n",
      "65378607361501080857009149939512557028198746004375<br>\n",
      "35829035317434717326932123578154982629742552737307<br>\n",
      "94953759765105305946966067683156574377167401875275<br>\n",
      "88902802571733229619176668713819931811048770190271<br>\n",
      "25267680276078003013678680992525463401061632866526<br>\n",
      "36270218540497705585629946580636237993140746255962<br>\n",
      "24074486908231174977792365466257246923322810917141<br>\n",
      "91430288197103288597806669760892938638285025333403<br>\n",
      "34413065578016127815921815005561868836468420090470<br>\n",
      "23053081172816430487623791969842487255036638784583<br>\n",
      "11487696932154902810424020138335124462181441773470<br>\n",
      "63783299490636259666498587618221225225512486764533<br>\n",
      "67720186971698544312419572409913959008952310058822<br>\n",
      "95548255300263520781532296796249481641953868218774<br>\n",
      "76085327132285723110424803456124867697064507995236<br>\n",
      "37774242535411291684276865538926205024910326572967<br>\n",
      "23701913275725675285653248258265463092207058596522<br>\n",
      "29798860272258331913126375147341994889534765745501<br>\n",
      "18495701454879288984856827726077713721403798879715<br>\n",
      "38298203783031473527721580348144513491373226651381<br>\n",
      "34829543829199918180278916522431027392251122869539<br>\n",
      "40957953066405232632538044100059654939159879593635<br>\n",
      "29746152185502371307642255121183693803580388584903<br>\n",
      "41698116222072977186158236678424689157993532961922<br>\n",
      "62467957194401269043877107275048102390895523597457<br>\n",
      "23189706772547915061505504953922979530901129967519<br>\n",
      "86188088225875314529584099251203829009407770775672<br>\n",
      "11306739708304724483816533873502340845647058077308<br>\n",
      "82959174767140363198008187129011875491310547126581<br>\n",
      "97623331044818386269515456334926366572897563400500<br>\n",
      "42846280183517070527831839425882145521227251250327<br>\n",
      "55121603546981200581762165212827652751691296897789<br>\n",
      "32238195734329339946437501907836945765883352399886<br>\n",
      "75506164965184775180738168837861091527357929701337<br>\n",
      "62177842752192623401942399639168044983993173312731<br>\n",
      "32924185707147349566916674687634660915035914677504<br>\n",
      "99518671430235219628894890102423325116913619626622<br>\n",
      "73267460800591547471830798392868535206946944540724<br>\n",
      "76841822524674417161514036427982273348055556214818<br>\n",
      "97142617910342598647204516893989422179826088076852<br>\n",
      "87783646182799346313767754307809363333018982642090<br>\n",
      "10848802521674670883215120185883543223812876952786<br>\n",
      "71329612474782464538636993009049310363619763878039<br>\n",
      "62184073572399794223406235393808339651327408011116<br>\n",
      "66627891981488087797941876876144230030984490851411<br>\n",
      "60661826293682836764744779239180335110989069790714<br>\n",
      "85786944089552990653640447425576083659976645795096<br>\n",
      "66024396409905389607120198219976047599490197230297<br>\n",
      "64913982680032973156037120041377903785566085089252<br>\n",
      "16730939319872750275468906903707539413042652315011<br>\n",
      "94809377245048795150954100921645863754710598436791<br>\n",
      "78639167021187492431995700641917969777599028300699<br>\n",
      "15368713711936614952811305876380278410754449733078<br>\n",
      "40789923115535562561142322423255033685442488917353<br>\n",
      "44889911501440648020369068063960672322193204149535<br>\n",
      "41503128880339536053299340368006977710650566631954<br>\n",
      "81234880673210146739058568557934581403627822703280<br>\n",
      "82616570773948327592232845941706525094512325230608<br>\n",
      "22918802058777319719839450180888072429661980811197<br>\n",
      "77158542502016545090413245809786882778948721859617<br>\n",
      "72107838435069186155435662884062257473692284509516<br>\n",
      "20849603980134001723930671666823555245252804609722<br>\n",
      "53503534226472524250874054075591789781264330331690<br>"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#The above list of numbers should be copied and pasted into a file called project_euler_problem13.txt\n",
      "filehandle = open(\"project_euler_problem13.txt\",\"r\")\n",
      "sum_of_values = 0\n",
      "for line in filehandle:\n",
      "    sum_of_values += int(line)\n",
      "print(\"The total sume is\",sum_of_values)    \n",
      "print(\"The first ten digits are\",(str(sum_of_values))[0:10])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The total sume is 5537376230390876637302048746832985971773659831892672\n",
        "The first ten digits are 5537376230\n"
       ]
      }
     ],
     "prompt_number": 88
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b>Problem 14</b>\n",
      "\n",
      "The following iterative sequence is defined for the set of positive integers:<br>\n",
      "\n",
      "n \u2192 n/2 (n is even)<br>\n",
      "n \u2192 3n + 1 (n is odd)<br>\n",
      "\n",
      "Using the rule above and starting with 13, we generate the following sequence:<br>\n",
      "13 \u2192 40 \u2192 20 \u2192 10 \u2192 5 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1<br>\n",
      "\n",
      "It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.\n",
      "\n",
      "Which starting number, under one million, produces the longest chain?<br>\n",
      "\n",
      "NOTE: Once the chain starts the terms are allowed to go above one million.<br>\n",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def next_term_in_collatz_chain( n ):\n",
      "    #Returns n/2 (if n even) or 3n+1 otherwise\n",
      "    if(n%2 == 0):\n",
      "        return(int(n/2))\n",
      "    elif( n == 1):\n",
      "            return(1)        \n",
      "    else:\n",
      "        return(3*n+1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Slowest of all solutions\n",
      "max_iterations = 10**6\n",
      "max_chain_length = 0\n",
      "max_chain_start_term = 1\n",
      "\n",
      "for i in range(1,max_iterations):\n",
      "    chain = []\n",
      "    term_value = i\n",
      "    while(term_value > 1):\n",
      "        term_value = next_term_in_collatz_chain(term_value)\n",
      "        chain.append(term_value)\n",
      "    if(len(chain) > max_chain_length):\n",
      "        max_chain_length = len(chain)\n",
      "        max_chain_start_term = i\n",
      "    \n",
      "print(\"The max chain length is\", max_chain_length,\"with start term\",max_chain_start_term)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The max chain length is 524 with start term 837799\n"
       ]
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Optimised 1\n",
      "#This code should run a lot faster than the one above because redundant chains not generated\n",
      "#i.e. if a value appears WITHIN chain then this value itself cannot be the start of the longest chain.\n",
      "#The max chain length is 524 with start term 837799\n",
      "\n",
      "max_iterations = 10**6\n",
      "max_chain_length = 0\n",
      "max_chain_start_term = 1\n",
      "\n",
      "a = [1]*max_iterations #Filter list, this will keep a record of which chains have already been seen\n",
      "\n",
      "for i in range(1,max_iterations):\n",
      "    if (a[i] == 1):\n",
      "        chain = []\n",
      "        term_value = i\n",
      "        while(term_value > 1):\n",
      "            term_value = next_term_in_collatz_chain(term_value)\n",
      "            if(term_value < len(a)):\n",
      "                a[term_value] = 0\n",
      "            chain.append(term_value)\n",
      "        if(len(chain) > max_chain_length):\n",
      "            max_chain_length = len(chain)\n",
      "            max_chain_start_term = i\n",
      "        \n",
      "    \n",
      "print(\"The max chain length is\", max_chain_length,\"with start term\",max_chain_start_term)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The max chain length is 524 with start term 837799\n"
       ]
      }
     ],
     "prompt_number": 53
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b> Problem 15 </b>\n",
      "\n",
      "Starting in the top left corner of a 2\u00d72 grid, and only being able to move to the right and down, <br>\n",
      "there are exactly 6 routes to the bottom right corner.<br><br>\n",
      "\n",
      "How many such routes are there through a 20\u00d720 grid?\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import factorial\n",
      "routes  = int(factorial(40)/factorial(20)**2)\n",
      "print(\"The number of routes on a 20x20 grid is\",routes)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The number of routes on a 20x20 grid is 137846528820\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Here we generate all the different possible paths for fun\n",
      "#An outcome tree similar to a probabilty tree will be used\n",
      "#del list[:] and list[:]=[] will be used to conserve memory\n",
      "#list.pop() could also have been used\n",
      "\n",
      "def right_node_creator(old_node, new_nodes):\n",
      "    #This creates a node element with one move to the right\n",
      "    return(new_nodes.append([old_node[0]+'R',old_node[1]-1,old_node[2]]))\n",
      "\n",
      "def down_node_creator(old_node, new_nodes):\n",
      "    #This creates a node element with one move to the right\n",
      "    return(new_nodes.append([old_node[0]+'D',old_node[1],old_node[2]-1]))\n",
      "\n",
      "old_nodes = [['',20,20]]\n",
      "for move_number in range(1,10):\n",
      "    new_nodes = []\n",
      "    for i in old_nodes:\n",
      "        if(i[1] > 0): #Right node creation test\n",
      "            right_node_creator( i , new_nodes )\n",
      "        if(i[2] > 0): #Down node creation test\n",
      "            down_node_creator( i , new_nodes )\n",
      "    del old_nodes[:]\n",
      "    old_nodes = new_nodes"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%reset out"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Once deleted, variables cannot be recovered. Proceed (y/[n])? y\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Flushing output cache (0 entries)\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "from math import factorial\n",
      "routes  = int(factorial(40)/factorial(20)**2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Using Numpy arrays\n",
      "#Here we generate all the different possible paths for fun\n",
      "#An outcome tree similar to a probabilty tree will be used\n",
      "#Numpy arrays are contiginous memmory allocation therefore \n",
      "#inplace append and insert does not exist. Memory allocation needs\n",
      "#to be declared at start for maximum efficiency. ... Great(!)...\n",
      "\n",
      "#def right_node_creator(nodes):\n",
      "    #This creates a node element with one move to the right\n",
      " #   return(np.array([old_node[0]+'R',int(old_node[1])-1,old_node[2]]))\n",
      "\n",
      "#def down_node_creator(nodes):\n",
      "    #This creates a node element with one move to the right\n",
      " #   return(np.array([old_node[0]+'D',old_node[1],int(old_node[2])-1]))\n",
      "\n",
      "nodes = np.array([0]*(100000000))\n",
      "100000000\n",
      "137846528820\n",
      "#nodes[1] = ['',20,20]\n",
      "j = 1 #This will keep track of the next unused memory slot in the Numpy array\n",
      "\n",
      "#for move_number in range(1,2):\n",
      "#    new_nodes = np.array([])\n",
      "#    for i in old_nodes:\n",
      "#        if(int(i[1]) > 0): #Right node creation test\n",
      "#            a = right_node_creator( i )\n",
      "#            np.append(new_nodes,a,axis=0)\n",
      "#        if(int(i[2]) > 0): #Down node creation test\n",
      "#            a = down_node_creator( i )\n",
      "#            np.append(new_nodes,a,axis=0)\n",
      "#    print(old_nodes)\n",
      "    #print(new_nodes)\n",
      "    #old_nodes = new_nodes\n",
      "#type(a)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "nodes.nbytes"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "800000000"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<b> Problem 20 </b>\n",
      "\n",
      "n! means n \u00d7 (n \u2212 1) \u00d7 ... \u00d7 3 \u00d7 2 \u00d7 1\n",
      "\n",
      "For example, 10! = 10 \u00d7 9 \u00d7 ... \u00d7 3 \u00d7 2 \u00d7 1 = 3628800,\n",
      "and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.\n",
      "\n",
      "Find the sum of the digits in the number 100!\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import factorial"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 42
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#The approach below is WRONG due to the trailing zeros on the end of 100!\n",
      "n = factorial(100)\n",
      "sum_digits = 0\n",
      "while ( n ):\n",
      "    sum_digits += (n % 10)\n",
      "    n = int( n/10 )\n",
      "print (sum_digits)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "675\n"
       ]
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#This approach yields the correct answer!\n",
      "n_string = str(factorial(100))\n",
      "sum_digits = 0\n",
      "for i in n_string:\n",
      "    sum_digits += int(i)\n",
      "print (sum_digits)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "648\n"
       ]
      }
     ],
     "prompt_number": 70
    }
   ],
   "metadata": {}
  }
 ]
}