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 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
// from Jon Harrop http://stackoverflow.com/questions/1526046/f-permutations
let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let rec permute = function
| [] -> [[]]
| e::xs -> List.collect (distribute e) (permute xs)
let rec loop k =
permute [1 .. k]
|> List.map (fun lst -> lst |> List.map (string) |> String.Concat)
|> List.map int
|> List.filter isPrime
|> function
| [] -> loop (k-1)
| lst -> List.max lst
loop 9
val it : int = 7652413
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:
$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...$
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.
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?
open System.IO
open System.Text.RegularExpressions
let file = __SOURCE_DIRECTORY__ + "/txt/p042.txt"
let text = File.ReadAllText(file)
let score (s:string) =
s |> Seq.toArray
|> Array.sumBy (fun c -> int c - 64)
let triNumbers =
Seq.initInfinite (fun n -> n*(n+1)/2)
|> Seq.skip 1
let isTri n =
triNumbers
|> Seq.find (fun k -> k>=n)
|> (=) n
[for w in Regex.Matches(text, "[A-Z]+") -> w.Value]
|> List.map score
|> List.filter isTri
|> List.length
val it : int = 162
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.
Let $d_1$ be the 1st digit, $d_2$ be the 2nd digit, and so on. In this way, we note the following:
$d_2d_3d_4=406$ is divisible by 2
$d_3d_4d_5=063$ is divisible by 3
$d_4d_5d_6=635$ is divisible by 5
$d_5d_6d_7=357$ is divisible by 7
$d_6d_7d_8=572$ is divisible by 11
$d_7d_8d_9=728$ is divisible by 13
$d_8d_9d_{10}=289$ is divisible by 17
Find the sum of all $0$ to $9$ pandigital numbers with this property.
let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let rec permute = function
| [] -> [[]]
| e::xs -> List.collect (distribute e) (permute xs)
let test (n:string) =
n.[0] <> '0' &&
int (n.[1..3]) % 2 = 0 &&
int (n.[2..4]) % 3 = 0 &&
int (n.[3..5]) % 5 = 0 &&
int (n.[4..6]) % 7 = 0 &&
int (n.[5..7]) % 11 = 0 &&
int (n.[6..8]) % 13 = 0 &&
int (n.[7..9]) % 17 = 0
[ 0 .. 9 ]
|> List.map string
|> permute
|> List.map (String.Concat)
|> List.filter test
|> List.sumBy (int64)
val it : int64 = 16695334890L
Pentagonal numbers are generated by the formula, $P_n=n(3n−1)/2$. The first ten pentagonal numbers are:
$1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...$
It can be seen that $P_4 + P_7 = 22 + 70 = 92 = P_8$. However, their difference, $70 − 22 = 48$, is not pentagonal.
Find the pair of pentagonal numbers, $P_j$ and $P_k$, for which their sum and difference are pentagonal and $D = |Pk − Pj|$ is minimised; what is the value of $D$?
let pentagonals =
Seq.initInfinite (fun i -> int64 i*(3L*int64 i-1L)/2L)
|> Seq.skip 1
|> Seq.takeWhile (fun n -> n < 10000000L)
|> set
// assuming that pj and pk are under 10M
pentagonals
|> Seq.collect (fun j -> pentagonals |> Seq.map (fun k -> (j,k)))
|> Seq.filter (fun (j,k) -> pentagonals |> Set.contains (j+k))
|> Seq.filter (fun (j,k) -> pentagonals |> Set.contains (k-j))
|> Seq.map (fun (j,k) -> k-j)
|> Seq.min
val it : int64 = 5482660L
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle | $T_n=n(n+1)/2$ | 1, 3, 6, 10, 15, ... |
Pentagonal | $P_n=n(3n−1)/2$ | 1, 5, 12, 22, 35, ... |
Hexagonal | $H_n=n(2n−1)$ | 1, 6, 15, 28, 45, ... |
It can be verified that $T_{285} = P_{165} = H_{143} = 40755$.
Find the next triangle number that is also pentagonal and hexagonal.
let maxN = 10000000000L
let hexs =
Seq.initInfinite (fun i -> int64 i*(2L*int64 i-1L))
|> Seq.skipWhile (fun n -> n <= 40755L)
|> Seq.takeWhile (fun n -> n < maxN)
|> set
let pents =
Seq.initInfinite (fun i -> int64 i*(3L*int64 i-1L)/2L)
|> Seq.skipWhile (fun n -> n <= 40755L)
|> Seq.takeWhile (fun n -> n < maxN)
|> set
let tris =
Seq.initInfinite (fun i -> int64 i*(int64 i+1L)/2L)
|> Seq.skipWhile (fun n -> n <= 40755L)
|> Seq.takeWhile (fun n -> n < maxN)
|> set
hexs
|> Set.intersect pents
|> Set.intersect tris
|> Seq.head
val it : int64 = 1533776805L
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
$9 = 7 + 2×1^2$
$15 = 7 + 2×2^2$
$21 = 3 + 2×3^2$
$25 = 7 + 2×3^2$
$27 = 19 + 2×2^2$
$33 = 31 + 2×1^2$
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
let isSquare n =
let t = int (sqrt (float n))
n = t * t
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 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 valid n =
primes
|> Seq.takeWhile (fun k -> k < n)
|> Seq.tryFind (fun k -> (n - k) / 2 |> isSquare)
|> fun k -> k.IsSome
Seq.initInfinite (fun k -> k*2+9)
|> Seq.filter (fun k -> not(isPrime k))
|> Seq.find (fun k -> not (valid k))
val it : int = 5777
The first two consecutive numbers to have two distinct prime factors are:
$14 = 2 × 7$
$15 = 3 × 5$
The first three consecutive numbers to have three distinct prime factors are:
$644 = 2^2 × 7 × 23$
$645 = 3 × 5 × 43$
$646 = 2 × 17 × 19$.
Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?
let factors n = Euler.FactorInteger n |> List.length
let len = 4
let rec loop (n:int64) (prior: bool list) =
let r =
(factors n = len) :: prior
|> Seq.take len
if r |> Seq.forall (fun t -> t=true) then
n - int64 len + 1L
else
loop (n+1L) (r |> Seq.toList)
loop 644L (List.init len (fun _ -> false))
val it : int64 = 134043L
[ 1 .. 1000 ]
|> Seq.sumBy (fun i -> pown (bigint i) i)
|> fun n -> n%(pown 10I 10)
val it : Numerics.BigInteger = 9110846700 {IsEven = true; IsOne = false; IsPowerOfTwo = false; IsZero = false; Sign = 1;}
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.
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.
What 12-digit number do you form by concatenating the three terms in this sequence?
open System.Collections
let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let rec permute = function
| [] -> [[]]
| e::xs -> List.collect (distribute e) (permute xs)
let rec comb n l =
match n, l with
| 0, _ -> [[]]
| _, [] -> []
| k, (x::xs) -> List.map ((@) [x]) (comb (k-1) xs) @ comb k xs
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 primes = getPrimes 10000
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
// define function to get the 4-digit prime permutations of a number
let getPrimePermutations n =
let digitsStr = string n |> Seq.toArray |> Array.map string
Array.toList digitsStr
|> permute
|> Seq.distinct
|> Seq.map (fun chars -> int(chars |> List.reduce (+)))
|> Seq.filter (fun x -> x >= 1000 && isPrime x)
|> Seq.sort
|> Seq.toList
primeNumbers
|> List.map getPrimePermutations
|> List.filter (fun l -> l |> List.length >= 3)
|> Seq.distinct
|> Seq.toList
|> List.map (fun l -> comb 3 l |> List.filter (fun x -> x.[1] - x.[0] = x.[2] - x.[1]))
|> List.filter (fun l -> l |> List.length > 0)
|> Seq.nth 1 // skip the first result (known)
|> List.map (String.Concat)
|> Seq.nth 0
val it : string = "296962999629"
The prime $41$, can be written as the sum of six consecutive primes:
$41 = 2 + 3 + 5 + 7 + 11 + 13$
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains $21$ terms, and is equal to $953$.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
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 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 maxPrime skip =
primes
|> Seq.skip skip
|> Seq.scan (fun state n -> ((1 + fst state), (n + snd state))) (0,0)
|> Seq.takeWhile (fun n -> (snd n)<1000000)
|> Seq.filter (fun n -> isPrime(snd n))
|> Seq.maxBy fst
let rec loop k result =
let test =
primes
|> Seq.skip k
|> Seq.take (fst result)
|> Seq.sum
if test > 1000000 then
snd result
else
[ maxPrime k; result ]
|> List.maxBy fst
|> fun r -> loop (k+1) r
loop 1 (maxPrime 0)
val it : int = 997651