Friday, November 12, 2010

Problem 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

The difficult part of this problem was working around F#'s lack of break, continue, and return in for loops. hasForm would be most easily expressed using nested for loops but would require break, continue, and return to perform acceptably. Another desire is support for infinite range expressions, so that oddComposites could be written as {9..2..} |> Seq.filter (isPrime>>not).

let problem46b = 
    let form p s = p + 2*(s*s)

    //making sure to exclude 1    
    let oddComposites = 
        Seq.initInfinite id 
        |> Seq.filter (fun i -> i <> 1 && i%2=1 && isPrime i |> not)
    
    //cached for performance
    let primes = 
        Seq.initInfinite id 
        |> Seq.filter isPrime 
        |> Seq.cache

    //exclusive
    let primesUpto n = 
        primes 
        |> Seq.takeWhile ((>=) n)

    //think nested loops
    let hasForm n = 
        primesUpto n
        |> Seq.exists 
            (fun p ->
                ({1..n-1} 
                |> Seq.map (fun s -> form p s)
                |> Seq.find (fun r -> (r = n) || (r > n))) = n)

    oddComposites
    |> Seq.find (hasForm>>not)

No comments:

Post a Comment