Sunday, July 18, 2010

Problem 45: After 40755, what is the next triangle number that is also pentagonal and hexagonal?

Here we reused the technique from Problem 44 for quickly asserting that a number is in the range of a function by verifying that n = f (f-1(n)).  We could also have tested that f-1(n) is integral.

let problem45a =
    let pent n = n*(3L*n-1L)/2L
    let pentInv n = (1L + sqrtL(24L*n + 1L))/6L
    let isPent n = (n = (pent (pentInv n)))
    let hex n = n*(2L*n-1L)
    let hexInv n = (1L + sqrtL(8L*n + 1L))/4L
    let isHex n = (n = (hex (hexInv n)))
    let tri n = n*(n+1L)/2L
    let rec triSeq n = seq {yield tri n; yield! triSeq (n+1L)}
    triSeq 286L
    |> Seq.find (fun n -> isPent n && isHex n)

Saturday, July 17, 2010

Problem 44: Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk - Pj| is minimised; what is the value of D?

This problem was a big disappointment.  It turns out that the first pair you find for which their sum and difference is pentagonal is the solution.  The interesting yet difficult minimization of D is a complete waste of time.  More than that, the running time of the solution I came up with is beyond reach and to keep from overflows big numbers would be required.  Looking at the Project Euler forum, most users totally glossed over the requirement for the minimization of D, though a couple others did protest.  What follows is the theory and implementation for the true solution of this problem (which as I’ve pointed out, actually won’t ever produce the result because 1) integer overflow, and 2) unreachable running time even when we do use big numbers).

The derivative of p is linear (p' = (3n^s - n)/2), so p is strickly increasing. Therefore, if p(i-1) - p(i) > min {p(s) - p(t) where i > s > t and p(s) and p(t) are pentagonal numbers for which their sum and difference is pentaganol} then the right-hand side is the minimization D.

let problem44a =
    let p n = n*(3*n-1)/2 //p = (3n^2-n)/2
    let pinv n = (1 + sqrtn(24*n + 1))/6 //inverse for positive range of p
    let isPentagonal t = t = (p (pinv t))
    let testPair p1 p2 = 
        (isPentagonal (p1-p2)) && (isPentagonal (p1+p2))
    let rec loop n minDiff =
        let pn = p n
        if ((p (n+1)) - pn) > minDiff then minDiff
            let rec find m = 
                let pm = p m
                if m = 0 then None
                elif testPair pn pm then Some(pm)
                else find (m-1)
            match find (n-1) with
            | Some(pm) -> loop (n+1) (min (pn-pm) minDiff) //take the first pair
            | None -> loop (n+1) minDiff
    loop 2 System.Int32.MaxValue

Sunday, July 4, 2010

Problem 43: Find the sum of all 0 to 9 pandigital numbers with the given property.

Combining our Digits and permutations implementations with F#’s built-in Seq functions, we really see how functional programming shines in describing complex algorithms simply.

let problem43a =  
    let hasProperty p = 
        let ddd = p |> Seq.skip 1
                    |> Seq.windowed 3
                    |> Digits.toInt 
        ddd [2;3;5;7;11;13;17]
        |> Seq.forall (fun (a,b) -> a % b = 0)
    permutationsAsc [0;1;2;3;4;5;6;7;8;9]
    |> Seq.filter hasProperty
    |> Seq.sumBy Digits.toInt64