Skip to content

Project Euler Problem 46

November 26, 2011

Project Euler Problem 46 solution:

open System

#nowarn "40"

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes 
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

let oddComposites =
    Seq.unfold (fun x -> Some(x, x+2)) 3 |> Seq.filter (isPrime >> not)

let squares =
    Seq.cache <| seq { yield 1;
                       yield! Seq.unfold (fun n -> Some(n*n + 2*n + 1, n+1)) 1 }
    
let falseConjecture n =
    let someSquares = primes |> Seq.skip 1 |> Seq.takeWhile ((>) n)
                      |> Seq.map (fun x -> (n - x) / 2) |> set
    let allSquares = squares
                     |> Seq.takeWhile ((>) (Set.maxElement someSquares)) |> set
    Set.intersect someSquares allSquares = Set.empty
 
let problem046 () =
    oddComposites |> Seq.find falseConjecture
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: