Project Euler — Problem 46 Solution

Problem

It was pro­posed by Chris­t­ian Gold­bach that every odd com­pos­ite num­ber can be writ­ten as the sum of a prime and twice a square.

9 = 7 + 2x12

15 = 7 + 2x22

21 = 3 + 2x32

25 = 7 + 2x32

27 = 19 + 2x22

33 = 31 + 2x12

It turns out that the con­jec­ture was false.

What is the small­est odd com­pos­ite that can­not be writ­ten as the sum of a prime and twice a square?

Solution

let hasDivisor(n) =
    let upperBound = int64(sqrt(double(n)))
    [2L..upperBound] |> Seq.exists (fun x -> n % x = 0L)

// need to consider negative values
let isPrime(n) = if n <= 1L then false else not(hasDivisor(n))

// generate the sequence of odd composite numbers
let oddCompositeNumbers = 
    Seq.unfold (fun state -> Some(state, state+2L)) 9L 
    |> Seq.filter (fun n -> not(isPrime n))

// generate the sequence of prime numbers
let primeNumbers = Seq.unfold (fun state -> Some(state, state+2L)) 1L |> Seq.filter isPrime

// function to check if a number can be written as the sum of a prime and twice a square
let isSum(number) =
    primeNumbers
    |> Seq.takeWhile (fun n -> n < number)
    |> Seq.exists (fun n -> sqrt(double((number-n)/2L)) % 1.0 = 0.0)

let answer = oddCompositeNumbers |> Seq.filter (fun n -> not(isSum(n))) |> Seq.head

All pret­ty straight for­ward here, the only slight­ly con­fus­ing part of this solu­tion is how to deter­mine if a num­ber can be writ­ten as the sum of a prime and twice a square:

Odd Com­pos­ite Num­ber = Prime + 2 x n2 => n = sqrt((Odd Com­pos­ite Num­ber – Prime) / 2)

As you know Math.Sqrt works with a dou­ble and returns a dou­ble, hence to find out if n above is a whole num­ber I had to check whether it divides by 1 even­ly