In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
seq {
for p200 in 0..200..200 do
for p100 in 0..100..(200 - p200) do
for p50 in 0..50..(200 - p200 - p100) do
for p20 in 0..20..(200 - p200 - p100 - p50) do
for p10 in 0..10..(200 - p200 - p100 - p50 - p20) do
for p5 in 0..5..(200 - p200 - p100 - p50 - p20 - p10) do
for p2 in 0..2..(200 - p200 - p100 - p50 - p20 - p10 - p5) do
yield 1
}
|> Seq.length
val it : int = 73682
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.
The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
let isPandigital(n) =
{2 .. int <| sqrt (float n)}
|> Seq.filter (fun x -> n%x=0)
|> Seq.map (fun x -> (string x + string (n/x) + string n) |> Set.ofSeq)
|> Seq.exists ((=) (Set("123456789" |> Set.ofSeq)))
[1000 .. 9999]
|> List.filter isPandigital
|> List.sum
val it : int = 45228
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.
We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
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.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
/// greatest common divisor
let rec gcd a b = if b = 0L then a else gcd b (a%b)
let isCancelling a b =
let aStr, bStr = string a, string b
if aStr.[0] = bStr.[0] then
float(string aStr.[1]) / float(string bStr.[1]) = float a / float b
else if aStr.[0] = bStr.[1] then
float(string aStr.[1]) / float(string bStr.[0]) = float a / float b
else if aStr.[1] = bStr.[0] then
float(string aStr.[0]) / float(string bStr.[1]) = float a / float b
else if aStr.[1] = bStr.[1] then
float(string aStr.[0]) / float(string bStr.[0]) = float a / float b
else false
let numbers n = [n..99] |> List.filter (fun x -> x % 10 <> 0 && (x % 10 <> x/10))
let fraction =
numbers 10
|> List.collect (fun x -> numbers (x+1) |> List.map (fun y -> (x, y)))
|> List.filter (fun (x, y) -> isCancelling x y)
|> List.reduce (fun (num, denom) (x, y) -> (num*x, denom*y))
// then define the denominator by the greatest common divisor
(int64<| snd fraction) / gcd (int64 <| fst fraction) (int64 <| snd fraction)
val it : int64 = 100L
let factorial = function
|0|1 -> 1
|n -> {1 .. n} |> Seq.reduce ( * )
let factsum (n:int) =
string n
|> Seq.toArray
|> Array.sumBy (string >> int >> factorial)
let maxN =
Seq.initInfinite (id)
|> Seq.map (fun x -> ( x , x * (factorial 9) ))
|> Seq.find (fun (a,b) -> ( (pown 10 a) - 1 ) > b )
|> (fun (a,b) -> (a - 1) * (factorial 9) )
seq { for i in 3..maxN -> (i, factsum i) }
|> Seq.sumBy (fun (a,b) -> if a=b then a else 0)
val it : int = 40730
// primve sieve that generates primes under 'n'
let getPrimes n =
let p = Array.create (n+1) true
for i = 2 to int(sqrt(float n)) do
if p.[i] then
for k = 2 to n/i do
p.[k*i] <- false
[ for i = 2 to n do
if p.[i] then yield i ]
let containsEven (n : int) =
string n
|> Seq.toArray
|> Seq.map (string >> int)
|> Seq.exists (fun k -> (k%2=0)
let primes =
getPrimes 1000000
|> Seq.filter(fun n -> not <| containsEven n)
|> set
let nextP n = primes |> Seq.tryFind(fun m -> m > n)
let shift(n : int) =
let s = string n
s.[1 .. s.Length - 1] + string s.[0]
|> int
let circle n =
Seq.unfold (fun m ->
let nextM = shift m
if m = n then None
else Some(m, nextM)) (shift n)
|> Seq.append [ n ]
let mutable n = Some 2
while n.IsSome do
let a = circle(n.Value)
if not(a |> Seq.forall(fun n -> primes.Contains(n))) then
a |> Seq.iter(fun n -> primes.Remove(n) |> ignore)
n <- nextP(n.Value)
(primes |> Seq.length) + 1
val it : int = 3218
The decimal number, $585 = 1001001001_2$ (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
let decIsPalindrome (n:int) =
string n
|> Seq.toArray
|> Array.rev
|> String.Concat = string n
let binIsPalindrome (n:int) =
Seq.unfold (fun n -> if n = 0 then None else Some (n%2,n/2)) n
|> Seq.toList
|> fun l -> l = (List.rev l)
[1 .. 1000000]
|> List.filter decIsPalindrome
|> List.filter binIsPalindrome
|> List.sum
val it : int = 872187
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.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
// primve sieve that generates primes under 'n'
let getPrimes n =
let p = Array.create (n+1) true
for i = 2 to int(sqrt(float n)) do
if p.[i] then
for k = 2 to n/i do
p.[k*i] <- false
[ for i = 2 to n do
if p.[i] then yield i ]
/// assume that primes under 1M is enough
let primes = getPrimes 1000000
let isPrime n =
match n with
|1 -> false
|n ->
primes
|> Seq.takeWhile (fun k -> k*k <= n)
|> Seq.exists ( fun k -> n%k = 0 )
|> not
let isTPrime (v:int) =
let n = string v
[ for i = 0 to n.Length-2 do
yield n.[ 0 .. i ]
yield n.[ i+1 .. n.Length-1 ]]
|> Seq.exists (fun k -> not <| isPrime (int k))
|> not
primes
|> Seq.skipWhile (fun n -> n<10)
|> Seq.toList
|> List.filter isTPrime
|> Seq.sum
val it : int = 748317
Take the number 192 and multiply it by each of 1, 2, and 3:
192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 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)
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).
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?
let panProduct (n:int) =
let digits = [ 1 .. 9 ] |> List.collect (fun k -> Seq.toList (string k)) |> set
let rec loop k =
match ([ 1 .. k ] |> List.map ( fun i -> string (n*i) ) |> String.Concat) with
|s when s.Length > 9 -> None
|s when s.Length < 9 -> loop (k+1)
|s ->
Set.difference digits (s |> Seq.toList |> set)
|> Set.count = 0
|> function
|true -> Some (int s)
|false -> None
loop 2
// find max trial
let maxTrial =
let rec loop (n:int) =
match (string n) + (string (n*2)) with
| s when s.Length < 10 -> loop (n+1)
| s -> n-1
loop 1
[ 1 .. maxTrial ]
|> Seq.map panProduct
|> Seq.filter (fun n -> n.IsSome)
|> Seq.max
val it : int option = Some 932718654
let sols p =
seq { for a in 1 .. p-2 do
for b in a .. p-a-1 do
let c = p - a - b
if c*c = a*a + b*b then
yield 1 }
|> Seq.sum
{ 3 .. 1000}
|> Seq.maxBy sols
val it : int = 840
An irrational decimal fraction is created by concatenating the positive integers:
0.123456789101112131415161718192021...
It can be seen that the 12th digit of the fractional part is 1.
If $d_n$ represents the nth digit of the fractional part, find the value of the following expression.
$d_1 × d_{10} × d_{100} × d_{1000} × d_{10000} × d_{100000} × d_{1000000}$
let s =
[ 1 .. 500000 ]
|> List.map string
|> String.Concat
let d n = s.[n-1] |> string |> int
List.init 7 (fun i -> pown 10 i)
|> List.map d
|> List.reduce ( * )
val it : int = 210