{ "metadata": { "language": "fsharp", "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "###Prime digit replacements\n", "####Problem 51\n", "By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: $13, 23, 43, 53, 73$, and $83$, are all prime.\n", "\n", "By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: $56003, 56113, 56333, 56443, 56663, 56773$, and $56993$. Consequently $56003$, being the first member of this family, is the smallest prime with this property.\n", "\n", "Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family." ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let t = System.\n", "\n", "let p51() =\n", " let groups n = \n", " seq [ for x in ['0'..'9'] ->\n", " set [ for y in ['0'..'9'] -> string n |> String.map (fun c -> if c=x then y else c) |> int ]\n", " |> Set.filter Math.PrimeQ ]\n", " |> Seq.filter (fun s -> s.Count = 8)\n", " \n", " // found answer with smallest of 857 ... leading zeros not allowed\n", " // code changed to take next\n", " \n", " Math.Primes32\n", " |> Seq.collect groups\n", " |> Seq.nth 1\n", " |> Set.minElement\n", " \n", "Euler.Timer(p51)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 1, "text": [ "val it : int * float = (121313, 5.0038227)" ] } ], "prompt_number": 1 }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Permuted multiples\n", "####Problem 52\n", "It can be seen that the number, $125874$, and its double, $251748$, contain exactly the same digits, but in a different order.\n", "\n", "Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits." ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p52() =\n", " let digits n = (string n).ToCharArray() |> set \n", " let sameMultiples n =\n", " let sets = [1..6] |> List.map (fun m -> digits(n*m))\n", " if sets.Tail |> List.forall((=) sets.Head) then Some n else None\n", " seq [100000..1000000]\n", " |> Seq.map sameMultiples\n", " |> Seq.find (fun n -> n.IsSome)\n", " \n", "Euler.Timer(p52)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 3, "text": [ "val it : int option * float = (Some 142857, 0.5343717)" ] } ], "prompt_number": 3 }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Combinatoric selections\n", "####Problem 53\n", "There are exactly ten ways of selecting three from five, $12345$:\n", "\n", "$123, 124, 125, 134, 135, 145, 234, 235, 245$, and $345$\n", "\n", "In combinatorics, we use the notation, $^5C_3=10$.\n", "\n", "In general,\n", "\n", "$^nC_r = \\frac {n!} {r!(n-r)!}$, where $r \u2264 n$, $n! = n\u00d7(n\u22121)\u00d7...\u00d73\u00d72\u00d71$, and $0! = 1$. It is not until $n = 23$, that a value exceeds one-million: $^{23}C_{10} = 1144066$.\n", "\n", "How many, not necessarily distinct, values of $^nC_r$, for $1 \u2264 n \u2264 100$, are greater than one-million?" ] }, { "cell_type": "code", "collapsed": false, "input": [ "open Euler\n", "\n", "let p53() =\n", " let lnFactorial = \n", " let f n = [1.0 .. float n] |> Seq.map log |> Seq.sum\n", " Map([1..100] |> List.map (fun k -> k, f k)) \n", " let isBigger n r = \n", " lnFactorial.[n] - lnFactorial.[r] - lnFactorial.[n-r] > log 1000000. \n", " let cnt = ref 0\n", " for n = 1 to 100 do\n", " for r = 1 to n-1 do\n", " if isBigger n r then\n", " incr cnt\n", " !cnt\n", " \n", "Euler.Timer(p53)" ], "language": "python", "metadata": {}, "outputs": [ { "metadata": {}, "output_type": "pyout", "prompt_number": 8, "text": [ "val it : int * float = (4075, 0.0055062)" ] } ], "prompt_number": 8 }, { "cell_type": "markdown", "metadata": {}, "source": [ "###Poker hands\n", "####Problem 54\n", "In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:\n", "\n", "* __High Card__: Highest value card.\n", "* __One Pair__: Two cards of the same value.\n", "* __Two Pairs__: Two different pairs.\n", "* __Three of a Kind__: Three cards of the same value.\n", "* __Straight__: All cards are consecutive values.\n", "* __Flush__: All cards of the same suit.\n", "* __Full House__: Three of a kind and a pair.\n", "* __Four of a Kind__: Four cards of the same value.\n", "* __Straight Flush__: All cards are consecutive values of same suit.\n", "* __Royal Flush__: Ten, Jack, Queen, King, Ace, in same suit. \n", "\n", "The cards are valued in the order: \n", "2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.\n", "\n", "If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.\n", "\n", "Consider the following five hands dealt to two players:\n", "\n", "
Hand | Player 1 | Player 2 | Winner | \n", "|||
1 | 5H 5C 6S 7S KD Pair of Fives | 2C 3S 8S 8D TD Pair of Eights | Player 2 | \n", "|||
2 | 5D 8C 9S JS AC Highest card Ace | 2C 5C 7D 8S QH Highest card Queen | Player 1 | \n", "|||
3 | 2D 9C AS AH AC Three Aces | 3D 6D 7D TD QD Flush with Diamonds | Player 2 | \n", "|||
4 | 4D 6S 9H QH QC Pair of Queens Highest card Nine | 3D 6D 7H QD QS Pair of Queens Highest card Seven | Player 1 | \n", "|||
5 | 2H 2D 4C 4D 4S Full House With Three Fours | 3C 3D 3S 9S 9D Full House with Three Threes | Player 1 | \n", "
37 36 35 34 33 32 31
\n",
"38 17 16 15 14 13 30
\n",
"39 18 5 4 3 12 29
\n",
"40 19 6 1 2 11 28
\n",
"41 20 7 8 9 10 27
\n",
"42 21 22 23 24 25 26
\n",
"43 44 45 46 47 48 49