{
 "metadata": {
  "language": "fsharp",
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Pandigital prime\n",
      "####Problem 41\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, 2143 is a 4-digit pandigital and is also prime.\n",
      "\n",
      "What is the largest n-digit pandigital prime that exists?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "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 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",
      "// from Jon Harrop http://stackoverflow.com/questions/1526046/f-permutations\n",
      "\n",
      "let rec distribute e = function\n",
      "  | [] -> [[e]]\n",
      "  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]\n",
      "\n",
      "let rec permute = function\n",
      "  | [] -> [[]]\n",
      "  | e::xs -> List.collect (distribute e) (permute xs)\n",
      "  \n",
      "let rec loop k =\n",
      "    permute [1 .. k]\n",
      "    |> List.map (fun lst -> lst |> List.map (string) |> String.Concat) \n",
      "    |> List.map int\n",
      "    |> List.filter isPrime\n",
      "    |> function\n",
      "       | [] -> loop (k-1)\n",
      "       | lst -> List.max lst\n",
      "    \n",
      "loop 9"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 44,
       "text": [
        "val it : int = 7652413"
       ]
      }
     ],
     "prompt_number": 44
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Coded triangle numbers\n",
      "####Problem 42\n",
      "The nth term of the sequence of triangle numbers is given by, $t_n = \\frac 1 2 n(n+1)$; so the first ten triangle numbers are:  \n",
      "\n",
      "$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$  \n",
      "\n",
      "By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is $19 + 11 + 25 = 55 = t_{10}$. If the word value is a triangle number then we shall call the word a triangle word.  \n",
      "\n",
      "Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?  "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "open System.IO\n",
      "open System.Text.RegularExpressions\n",
      "\n",
      "let file = __SOURCE_DIRECTORY__ + \"/txt/p042.txt\"\n",
      "\n",
      "let text = File.ReadAllText(file)\n",
      "\n",
      "let score (s:string) =\n",
      "    s |> Seq.toArray\n",
      "      |> Array.sumBy (fun c -> int c - 64)\n",
      "\n",
      "let triNumbers = \n",
      "    Seq.initInfinite (fun n -> n*(n+1)/2)\n",
      "    |> Seq.skip 1\n",
      "\n",
      "let isTri n =\n",
      "    triNumbers\n",
      "    |> Seq.find (fun k -> k>=n)\n",
      "    |> (=) n\n",
      "\n",
      "[for w in Regex.Matches(text, \"[A-Z]+\") -> w.Value]\n",
      "|> List.map score\n",
      "|> List.filter isTri\n",
      "|> List.length"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "val it : int = 162"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Sub-string divisibility\n",
      "####Problem 43\n",
      "The number, $1406357289$, is a $0$ to $9$ pandigital number because it is made up of each of the digits $0$ to $9$ in some order, but it also has a rather interesting sub-string divisibility property.  \n",
      "\n",
      "Let $d_1$ be the 1st digit, $d_2$ be the 2nd digit, and so on. In this way, we note the following:  \n",
      "\n",
      "$d_2d_3d_4=406$ is divisible by 2  \n",
      "$d_3d_4d_5=063$ is divisible by 3  \n",
      "$d_4d_5d_6=635$ is divisible by 5  \n",
      "$d_5d_6d_7=357$ is divisible by 7  \n",
      "$d_6d_7d_8=572$ is divisible by 11  \n",
      "$d_7d_8d_9=728$ is divisible by 13  \n",
      "$d_8d_9d_{10}=289$ is divisible by 17  \n",
      "\n",
      "Find the sum of all $0$ to $9$ pandigital numbers with this property."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let rec distribute e = function\n",
      "  | [] -> [[e]]\n",
      "  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]\n",
      "\n",
      "let rec permute = function\n",
      "  | [] -> [[]]\n",
      "  | e::xs -> List.collect (distribute e) (permute xs)\n",
      "\n",
      "let test (n:string) =\n",
      "    n.[0] <> '0' &&\n",
      "    int (n.[1..3]) % 2 = 0 &&\n",
      "    int (n.[2..4]) % 3 = 0 &&\n",
      "    int (n.[3..5]) % 5 = 0 &&\n",
      "    int (n.[4..6]) % 7 = 0 &&\n",
      "    int (n.[5..7]) % 11 = 0 &&\n",
      "    int (n.[6..8]) % 13 = 0 &&\n",
      "    int (n.[7..9]) % 17 = 0 \n",
      "\n",
      "[ 0 .. 9 ]\n",
      "|> List.map string\n",
      "|> permute\n",
      "|> List.map (String.Concat)\n",
      "|> List.filter test\n",
      "|> List.sumBy (int64)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 60,
       "text": [
        "val it : int64 = 16695334890L"
       ]
      }
     ],
     "prompt_number": 60
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Pentagon numbers\n",
      "####Problem 44\n",
      "Pentagonal numbers are generated by the formula, $P_n=n(3n\u22121)/2$. The first ten pentagonal numbers are:  \n",
      "\n",
      "$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...$  \n",
      "\n",
      "It can be seen that $P_4 + P_7 = 22 + 70 = 92 = P_8$. However, their difference, $70 \u2212 22 = 48$, is not pentagonal.\n",
      "\n",
      "Find the pair of pentagonal numbers, $P_j$ and $P_k$, for which their sum and difference are pentagonal and $D = |Pk \u2212 Pj|$ is minimised; what is the value of $D$?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let pentagonals = \n",
      "    Seq.initInfinite (fun i -> int64 i*(3L*int64 i-1L)/2L) \n",
      "    |> Seq.skip 1 \n",
      "    |> Seq.takeWhile (fun n -> n < 10000000L) \n",
      "    |> set\n",
      "\n",
      "// assuming that pj and pk are under 10M\n",
      "\n",
      "pentagonals \n",
      "|> Seq.collect (fun j -> pentagonals |> Seq.map (fun k -> (j,k)))\n",
      "|> Seq.filter (fun (j,k) -> pentagonals |> Set.contains (j+k))\n",
      "|> Seq.filter (fun (j,k) -> pentagonals |> Set.contains (k-j))\n",
      "|> Seq.map (fun (j,k) -> k-j)\n",
      "|> Seq.min"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "val it : int64 = 5482660L"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Triangular, pentagonal, and hexagonal\n",
      "####Problem 45\n",
      "Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:  \n",
      "\n",
      "|            |                |                       |\n",
      "| ---------- | -------------- | --------------------- |\n",
      "| Triangle\t | $T_n=n(n+1)/2$  |\t1, 3, 6, 10, 15, ...  |\n",
      "| Pentagonal | $P_n=n(3n\u22121)/2$ | 1, 5, 12, 22, 35, ... |\n",
      "| Hexagonal\t | $H_n=n(2n\u22121)$\t  |\t1, 6, 15, 28, 45, ... |  \n",
      "\n",
      "It can be verified that $T_{285} = P_{165} = H_{143} = 40755$. \n",
      "\n",
      "Find the next triangle number that is also pentagonal and hexagonal."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let maxN = 10000000000L\n",
      "\n",
      "let hexs = \n",
      "    Seq.initInfinite (fun i -> int64 i*(2L*int64 i-1L)) \n",
      "    |> Seq.skipWhile (fun n -> n <= 40755L) \n",
      "    |> Seq.takeWhile (fun n -> n < maxN) \n",
      "    |> set\n",
      "let pents = \n",
      "    Seq.initInfinite (fun i -> int64 i*(3L*int64 i-1L)/2L) \n",
      "    |> Seq.skipWhile (fun n -> n <= 40755L) \n",
      "    |> Seq.takeWhile (fun n -> n < maxN) \n",
      "    |> set\n",
      "let tris = \n",
      "    Seq.initInfinite (fun i -> int64 i*(int64 i+1L)/2L) \n",
      "    |> Seq.skipWhile (fun n -> n <= 40755L) \n",
      "    |> Seq.takeWhile (fun n -> n < maxN) \n",
      "    |> set\n",
      "\n",
      "hexs\n",
      "|> Set.intersect pents\n",
      "|> Set.intersect tris\n",
      "|> Seq.head"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "val it : int64 = 1533776805L"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Goldbach's other conjecture\n",
      "####Problem 46\n",
      "It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.  \n",
      "\n",
      "$9 = 7 + 2\u00d71^2$  \n",
      "$15 = 7 + 2\u00d72^2$  \n",
      "$21 = 3 + 2\u00d73^2$  \n",
      "$25 = 7 + 2\u00d73^2$  \n",
      "$27 = 19 + 2\u00d72^2$  \n",
      "$33 = 31 + 2\u00d71^2$  \n",
      "\n",
      "It turns out that the conjecture was false.  \n",
      "\n",
      "What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let isSquare n = \n",
      "    let t = int (sqrt (float n))\n",
      "    n = t * t\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 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 valid n =\n",
      "    primes\n",
      "    |> Seq.takeWhile (fun k -> k < n)\n",
      "    |> Seq.tryFind (fun k -> (n - k) / 2 |> isSquare)\n",
      "    |> fun k -> k.IsSome\n",
      "\n",
      "Seq.initInfinite (fun k -> k*2+9)\n",
      "|> Seq.filter (fun k -> not(isPrime k))\n",
      "|> Seq.find (fun k -> not (valid k))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "val it : int = 5777"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Distinct primes factors\n",
      "####Problem 47\n",
      "The first two consecutive numbers to have two distinct prime factors are:  \n",
      "\n",
      "$14 = 2 \u00d7 7$  \n",
      "$15 = 3 \u00d7 5$  \n",
      "\n",
      "The first three consecutive numbers to have three distinct prime factors are:  \n",
      "\n",
      "$644 = 2^2 \u00d7 7 \u00d7 23$  \n",
      "$645 = 3 \u00d7 5 \u00d7 43$  \n",
      "$646 = 2 \u00d7 17 \u00d7 19$.\n",
      "\n",
      "Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "let factors n = Euler.FactorInteger n |> List.length\n",
      "\n",
      "let len = 4\n",
      "\n",
      "let rec loop (n:int64) (prior: bool list) =\n",
      "    let r = \n",
      "        (factors n = len) :: prior\n",
      "        |> Seq.take len\n",
      "    if r |> Seq.forall (fun t -> t=true) then\n",
      "        n - int64 len + 1L\n",
      "    else\n",
      "       loop (n+1L) (r |> Seq.toList)\n",
      "       \n",
      "loop 644L (List.init len (fun _ -> false))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 119,
       "text": [
        "val it : int64 = 134043L"
       ]
      }
     ],
     "prompt_number": 119
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Self powers\n",
      "####Problem 48\n",
      "The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$.  \n",
      "\n",
      "Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ 1 .. 1000 ]\n",
      "|> Seq.sumBy (fun i -> pown (bigint i) i)\n",
      "|> fun n -> n%(pown 10I 10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 52,
       "text": [
        "val it : Numerics.BigInteger = 9110846700 {IsEven = true;\r\n",
        "                                           IsOne = false;\r\n",
        "                                           IsPowerOfTwo = false;\r\n",
        "                                           IsZero = false;\r\n",
        "                                           Sign = 1;}"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Prime permutations\n",
      "####Problem 49\n",
      "The arithmetic sequence, $1487$, $4817$, $8147$, in which each of the terms increases by $3330$, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.\n",
      "\n",
      "There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.\n",
      "\n",
      "What 12-digit number do you form by concatenating the three terms in this sequence?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "open System.Collections\n",
      " \n",
      "let rec distribute e = function\n",
      "    | [] -> [[e]]\n",
      "    | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]\n",
      " \n",
      "let rec permute = function\n",
      "    | [] -> [[]]\n",
      "    | e::xs -> List.collect (distribute e) (permute xs)\n",
      " \n",
      "let rec comb n l =\n",
      "    match n, l with\n",
      "    | 0, _ -> [[]]\n",
      "    | _, [] -> []\n",
      "    | k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs\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 primes = getPrimes 10000\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",
      "// define function to get the 4-digit prime permutations of a number\n",
      "let getPrimePermutations n =\n",
      "    let digitsStr = string n |> Seq.toArray |> Array.map string\n",
      "    Array.toList digitsStr\n",
      "    |> permute\n",
      "    |> Seq.distinct\n",
      "    |> Seq.map (fun chars -> int(chars |> List.reduce (+)))\n",
      "    |> Seq.filter (fun x -> x >= 1000 && isPrime x)\n",
      "    |> Seq.sort\n",
      "    |> Seq.toList\n",
      " \n",
      "primeNumbers\n",
      "|> List.map getPrimePermutations\n",
      "|> List.filter (fun l -> l |> List.length >= 3)\n",
      "|> Seq.distinct\n",
      "|> Seq.toList\n",
      "|> List.map (fun l -> comb 3 l |> List.filter (fun x -> x.[1] - x.[0] = x.[2] - x.[1]))\n",
      "|> List.filter (fun l -> l |> List.length > 0)\n",
      "|> Seq.nth 1 // skip the first result (known)\n",
      "|> List.map (String.Concat)\n",
      "|> Seq.nth 0"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 91,
       "text": [
        "val it : string = \"296962999629\""
       ]
      }
     ],
     "prompt_number": 91
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Consecutive prime sum\n",
      "####Problem 50\n",
      "The prime $41$, can be written as the sum of six consecutive primes:  \n",
      "\n",
      "$41 = 2 + 3 + 5 + 7 + 11 + 13$  \n",
      "\n",
      "This is the longest sum of consecutive primes that adds to a prime below one-hundred.  \n",
      "\n",
      "The longest sum of consecutive primes below one-thousand that adds to a prime, contains $21$ terms, and is equal to $953$.  \n",
      "\n",
      "Which prime, below one-million, can be written as the sum of the most consecutive primes?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "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 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 maxPrime skip =\n",
      "    primes\n",
      "    |> Seq.skip skip\n",
      "    |> Seq.scan (fun state n -> ((1 + fst state), (n + snd state))) (0,0)\n",
      "    |> Seq.takeWhile (fun n -> (snd n)<1000000)\n",
      "    |> Seq.filter (fun n -> isPrime(snd n))\n",
      "    |> Seq.maxBy fst\n",
      "    \n",
      "let rec loop k result =\n",
      "    let test = \n",
      "        primes\n",
      "        |> Seq.skip k\n",
      "        |> Seq.take (fst result)\n",
      "        |> Seq.sum\n",
      "    if test > 1000000 then\n",
      "        snd result\n",
      "    else\n",
      "        [ maxPrime k; result ]\n",
      "        |> List.maxBy fst\n",
      "        |> fun r -> loop (k+1) r\n",
      "    \n",
      "loop 1 (maxPrime 0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 89,
       "text": [
        "val it : int = 997651"
       ]
      }
     ],
     "prompt_number": 89
    }
   ],
   "metadata": {}
  }
 ]
}