Problem #46 says

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?

Solution below uses the method of generating a list of primes and then using a set list of numbers to square and checking the combination’s to see if we can find one that makes the number we’re looking for.

Solution provided in f# and requires .net 4. runs in ~50 seconds. could be made much faster by rewriting the “Check” function to use a set of recursive functions instead of for loops so we could break out of them.

#light
open System
open System.Diagnostics
open System.Collections.Generic

//get some prime factors
//set the limit and bound
let UpperLimit = 10000.
let UpperBound = 10000
//generate numbers to check
let LNums = ref [2..(int UpperLimit)] in
// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to UpperBound do
  LNums := List.filter(fun num -> (num % div <> 0 || div >= num))
        !LNums
done;
let Primes:list<int> = !LNums

//numbers to check
let nums = [13 .. 6000]

let NonPrime =
     (Set.ofList nums) - (Set.ofList Primes) |> Set.toList |> List.filter (fun x -> x % 2 <> 0)

Console.WriteLine("Starting check")
let watch = new Stopwatch()
watch.Start()

let Check number =
    let mutable RetValue = true
    for n in Primes do
        for c in [1..100] do
            if (n + (2 * (c * c))) = number then
                RetValue <- false
    RetValue

let N =
    NonPrime
    |> Seq.filter Check
    |> Seq.toArray

watch.Stop()
Console.WriteLine(N.[0])
Console.WriteLine(watch.Elapsed)
Console.ReadKey()