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
        else
            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

No comments:

Post a Comment