{
 "metadata": {
  "language": "fsharp",
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Coin sums\n",
      "####Problem 31\n",
      "In England the currency is made up of pound, \u00a3, and pence, p, and there are eight coins in general circulation:  \n",
      "\n",
      "1p, 2p, 5p, 10p, 20p, 50p, \u00a31 (100p) and \u00a32 (200p).  \n",
      "It is possible to make \u00a32 in the following way:  \n",
      "\n",
      "1\u00d7\u00a31 + 1\u00d750p + 2\u00d720p + 1\u00d75p + 1\u00d72p + 3\u00d71p  \n",
      "How many different ways can \u00a32 be made using any number of coins?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "seq { \n",
      "    for p200 in 0..200..200 do\n",
      "        for p100 in 0..100..(200 - p200) do\n",
      "            for p50 in 0..50..(200 - p200 - p100) do\n",
      "                for p20 in 0..20..(200 - p200 - p100 - p50) do\n",
      "                    for p10 in 0..10..(200 - p200 - p100 - p50 - p20) do\n",
      "                        for p5 in 0..5..(200 - p200 - p100 - p50 - p20 - p10) do\n",
      "                            for p2 in 0..2..(200 - p200 - p100 - p50 - p20 - p10 - p5) do\n",
      "                                yield 1\n",
      "}\n",
      "|> Seq.length"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "val it : int = 73682"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Pandigital products\n",
      "####Problem 32\n",
      "We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.\n",
      "\n",
      "The product 7254 is unusual, as the identity, 39 \u00d7 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.\n",
      "\n",
      "Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.\n",
      "\n",
      "HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let isPandigital(n) =        \n",
      "    {2 .. int <| sqrt (float n)}    \n",
      "    |> Seq.filter (fun x -> n%x=0)     \n",
      "    |> Seq.map (fun x -> (string x + string (n/x) + string n) |> Set.ofSeq)    \n",
      "    |> Seq.exists ((=) (Set(\"123456789\" |> Set.ofSeq)))\n",
      "       \n",
      "[1000 .. 9999] \n",
      "|> List.filter isPandigital \n",
      "|> List.sum "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "val it : int = 45228"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Digit canceling fractions\n",
      "####Problem 33\n",
      "The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.\n",
      "\n",
      "We shall consider fractions like, 30/50 = 3/5, to be trivial examples.\n",
      "\n",
      "There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.\n",
      "\n",
      "If the product of these four fractions is given in its lowest common terms, find the value of the denominator."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "/// greatest common divisor\n",
      "let rec gcd a b = if b = 0L then a else gcd b (a%b)\n",
      "\n",
      "let isCancelling a b =\n",
      "    let aStr, bStr = string a, string b     \n",
      "    if aStr.[0] = bStr.[0] then \n",
      "        float(string aStr.[1]) / float(string bStr.[1]) = float a / float b    \n",
      "    else if aStr.[0] = bStr.[1] then \n",
      "        float(string aStr.[1]) / float(string bStr.[0]) = float a / float b    \n",
      "    else if aStr.[1] = bStr.[0] then \n",
      "        float(string aStr.[0]) / float(string bStr.[1]) = float a / float b    \n",
      "    else if aStr.[1] = bStr.[1] then \n",
      "        float(string aStr.[0]) / float(string bStr.[0]) = float a / float b    \n",
      "    else false  \n",
      "    \n",
      "let numbers n = [n..99] |> List.filter (fun x -> x % 10 <> 0 && (x % 10 <> x/10))   \n",
      "    \n",
      "let fraction =         \n",
      "    numbers 10         \n",
      "    |> List.collect (fun x -> numbers (x+1) |> List.map (fun y -> (x, y)))         \n",
      "    |> List.filter (fun (x, y) -> isCancelling x y)         \n",
      "    |> List.reduce (fun (num, denom) (x, y) -> (num*x, denom*y))     \n",
      "    \n",
      "// then define the denominator by the greatest common divisor     \n",
      "(int64<| snd fraction) / gcd (int64 <| fst fraction) (int64 <| snd fraction) "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "val it : int64 = 100L"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Digit factorials\n",
      "####Problem 34\n",
      "145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.\n",
      "\n",
      "Find the sum of all numbers which are equal to the sum of the factorial of their digits.\n",
      "\n",
      "Note: as 1! = 1 and 2! = 2 are not sums they are not included."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "  let factorial = function\n",
      "    |0|1 -> 1\n",
      "    |n -> {1 .. n} |> Seq.reduce ( * )\n",
      "\n",
      "  let factsum (n:int) =\n",
      "    string n \n",
      "    |> Seq.toArray\n",
      "    |> Array.sumBy (string >> int >> factorial)\n",
      "\n",
      "  let maxN =\n",
      "    Seq.initInfinite (id)\n",
      "    |> Seq.map (fun x -> ( x , x * (factorial 9) ))\n",
      "    |> Seq.find (fun (a,b) -> ( (pown 10 a) - 1 ) > b )\n",
      "    |> (fun (a,b) -> (a - 1) * (factorial 9) )\n",
      "\n",
      "  seq { for i in 3..maxN -> (i, factsum i) }\n",
      "  |> Seq.sumBy (fun (a,b) -> if a=b then a else 0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "val it : int = 40730"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Circular primes\n",
      "####Problem 35\n",
      "The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.\n",
      "\n",
      "There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.\n",
      "\n",
      "How many circular primes are there below one million?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "// primve sieve that generates primes under 'n'\n",
      "let getPrimes n = \n",
      "    let p = Array.create (n+1) true\n",
      "    for i = 2 to int(sqrt(float n)) do\n",
      "        if p.[i] then\n",
      "            for k = 2 to n/i do\n",
      "                p.[k*i] <- false\n",
      "    [ for i = 2 to n do\n",
      "        if p.[i] then yield i ]\n",
      "\n",
      "let containsEven (n : int) = \n",
      "        string n\n",
      "        |> Seq.toArray\n",
      "        |> Seq.map (string >> int)\n",
      "        |> Seq.exists (fun k -> (k%2=0)\n",
      "    \n",
      "let primes = \n",
      "    getPrimes 1000000\n",
      "    |> Seq.filter(fun n -> not <| containsEven n)\n",
      "    |> set\n",
      "        \n",
      "let nextP n = primes |> Seq.tryFind(fun m -> m > n)\n",
      "    \n",
      "let shift(n : int) = \n",
      "        let s = string n\n",
      "        s.[1 .. s.Length - 1] + string s.[0]\n",
      "        |> int\n",
      "    \n",
      "let circle n = \n",
      "        Seq.unfold (fun m -> \n",
      "            let nextM = shift m\n",
      "            if m = n then None\n",
      "            else Some(m, nextM)) (shift n)\n",
      "        |> Seq.append [ n ]\n",
      "    \n",
      "let mutable n = Some 2\n",
      "\n",
      "while n.IsSome do\n",
      "        let a = circle(n.Value)\n",
      "        if not(a |> Seq.forall(fun n -> primes.Contains(n))) then \n",
      "            a |> Seq.iter(fun n -> primes.Remove(n) |> ignore)\n",
      "        n <- nextP(n.Value)\n",
      "\n",
      "(primes |> Seq.length) + 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "val it : int = 3218"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Double-base palindromes\n",
      "####Problem 36\n",
      "The decimal number, $585 = 1001001001_2$ (binary), is palindromic in both bases.\n",
      "\n",
      "Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.\n",
      "\n",
      "(Please note that the palindromic number, in either base, may not include leading zeros.)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let decIsPalindrome (n:int) = \n",
      "    string n \n",
      "    |> Seq.toArray \n",
      "    |> Array.rev \n",
      "    |> String.Concat = string n\n",
      "\n",
      "let binIsPalindrome (n:int) = \n",
      "    Seq.unfold (fun n -> if n = 0 then None else Some (n%2,n/2)) n \n",
      "    |> Seq.toList \n",
      "    |> fun l -> l = (List.rev l)\n",
      "\n",
      "[1 .. 1000000]\n",
      "|> List.filter decIsPalindrome\n",
      "|> List.filter binIsPalindrome\n",
      "|> List.sum"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "val it : int = 872187"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Truncatable primes\n",
      "####Problem 37\n",
      "The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.\n",
      "\n",
      "Find the sum of the only eleven primes that are both truncatable from left to right and right to left.\n",
      "\n",
      "NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "// primve sieve that generates primes under 'n'\n",
      "let getPrimes n = \n",
      "    let p = Array.create (n+1) true\n",
      "    for i = 2 to int(sqrt(float n)) do\n",
      "        if p.[i] then\n",
      "            for k = 2 to n/i do\n",
      "                p.[k*i] <- false\n",
      "    [ for i = 2 to n do\n",
      "        if p.[i] then yield i ]\n",
      "\n",
      "/// assume that primes under 1M is enough\n",
      "let primes = getPrimes 1000000\n",
      "\n",
      "let isPrime n = \n",
      "    match n with\n",
      "    |1 -> false\n",
      "    |n ->\n",
      "        primes\n",
      "        |> Seq.takeWhile (fun k -> k*k <= n)\n",
      "        |> Seq.exists ( fun k -> n%k = 0 )\n",
      "        |> not\n",
      "\n",
      "let isTPrime (v:int) =\n",
      "    let n = string v\n",
      "    [ for i = 0 to n.Length-2 do\n",
      "            yield n.[ 0 .. i ]\n",
      "            yield n.[ i+1 .. n.Length-1 ]]\n",
      "    |> Seq.exists (fun k -> not <| isPrime (int k))\n",
      "    |> not\n",
      "     \n",
      "primes\n",
      "|> Seq.skipWhile (fun n -> n<10)\n",
      "|> Seq.toList\n",
      "|> List.filter isTPrime\n",
      "|> Seq.sum"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 65,
       "text": [
        "val it : int = 748317"
       ]
      }
     ],
     "prompt_number": 65
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Pandigital multiples\n",
      "####Problem 38\n",
      "Take the number 192 and multiply it by each of 1, 2, and 3:\n",
      "\n",
      "192 \u00d7 1 = 192\n",
      "192 \u00d7 2 = 384\n",
      "192 \u00d7 3 = 576\n",
      "By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)\n",
      "\n",
      "The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).\n",
      "\n",
      "What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let panProduct (n:int) =\n",
      "    let digits = [ 1 .. 9 ] |> List.collect (fun k -> Seq.toList (string k)) |> set\n",
      "    let rec loop k =\n",
      "        match ([ 1 .. k ] |> List.map ( fun i -> string (n*i) ) |> String.Concat) with\n",
      "        |s when s.Length > 9 -> None\n",
      "        |s when s.Length < 9 -> loop (k+1)\n",
      "        |s -> \n",
      "            Set.difference digits (s |> Seq.toList |> set)\n",
      "            |> Set.count = 0\n",
      "            |> function\n",
      "               |true -> Some (int s)\n",
      "               |false -> None\n",
      "    loop 2\n",
      "\n",
      "// find max trial\n",
      "let maxTrial =\n",
      "    let rec loop (n:int) = \n",
      "        match (string n) + (string (n*2)) with\n",
      "        | s when s.Length < 10 -> loop (n+1)\n",
      "        | s -> n-1\n",
      "    loop 1\n",
      "   \n",
      "[ 1 .. maxTrial ]\n",
      "|> Seq.map panProduct\n",
      "|> Seq.filter (fun n -> n.IsSome)\n",
      "|> Seq.max"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 57,
       "text": [
        "val it : int option = Some 932718654"
       ]
      }
     ],
     "prompt_number": 57
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Integer right triangles\n",
      "####Problem 39\n",
      "If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.\n",
      "\n",
      "{20,48,52}, {24,45,51}, {30,40,50}\n",
      "\n",
      "For which value of p \u2264 1000, is the number of solutions maximised?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let sols p =\n",
      "    seq { for a in 1 .. p-2 do\n",
      "            for b in a .. p-a-1 do\n",
      "                let c = p - a - b\n",
      "                if c*c = a*a + b*b then\n",
      "                    yield 1 }\n",
      "    |> Seq.sum\n",
      "    \n",
      "{ 3 .. 1000}\n",
      "|> Seq.maxBy sols"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "val it : int = 840"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Champernowne's constant\n",
      "####Problem 40\n",
      "An irrational decimal fraction is created by concatenating the positive integers:\n",
      "\n",
      "0.123456789101112131415161718192021...\n",
      "\n",
      "It can be seen that the 12th digit of the fractional part is 1.\n",
      "\n",
      "If $d_n$ represents the nth digit of the fractional part, find the value of the following expression.\n",
      "\n",
      "$d_1 \u00d7 d_{10} \u00d7 d_{100} \u00d7 d_{1000} \u00d7 d_{10000} \u00d7 d_{100000} \u00d7 d_{1000000}$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let s =\n",
      "    [ 1 .. 500000 ] \n",
      "    |> List.map string \n",
      "    |> String.Concat\n",
      "\n",
      "let d n = s.[n-1] |> string |> int\n",
      "\n",
      "List.init 7 (fun i -> pown 10 i)\n",
      "|> List.map d\n",
      "|> List.reduce ( * )"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 42,
       "text": [
        "val it : int = 210"
       ]
      }
     ],
     "prompt_number": 42
    }
   ],
   "metadata": {}
  }
 ]
}