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