I’m with Skip here: how do y’all guarantee that your brute-force answers (which search through a list of the first few pentagonal numbers) actually return the pair with the smallest _difference_? How do you know there isn’t a pair outside your search range, where each number in the pair is much larger than any you searched but whose difference is smaller?
One possibility is to find a lower bound B as a function of k for the difference P(n)-P(m), where n>m>k. If B(k) is larger than 1019 (the answer Pascal Jasmin gave) for k outside your search range, then 1019 is indeed the answer. A possibility for B is B(k) = P(k+1)-P(k). Another idea I had is that since the sum and the difference must both be pentagonal, we can instead search in the same way for them and make sure their half-sum and half-difference (which equal the original numbers) are indeed pentagonal. The first pair we find will be the one we want since by then we’ll have checked all pairs with a smaller difference. Do you have a better justification? Thanks! Louis > On 13 Jul 2019, at 01:31, Skip Cave <[email protected]> wrote: > > Another approach to Euler 44: > NB. make a pentagonal number generator verb: > *pn=.3 :'y*(1-~3*y)%2'* > > NB. Generate the first 5000 pentagonal numbers and store them in p. Then > find all possible pair combinations of the first 5000 pentagonal numbers > and store the pairs in p2. Then store the two integers in each pair in the > vectors a & b respectively: > * 'a b'=.|:p2=.(2 comb 5000){p=:pn>:i.5000x* > > NB. Find and mark all pairs where a+b and a-b are both pentagonal numbers. > Store that mark vector in m. Also sum the marks in m to see how many > solution pairs we have: > * +/m=.(p e. ~a+b) *. p e. ~|a-b* > > *1* > > NB. So there is only one solution pair in the first 5000 pentagonal > numbers. Now use the mark vector to extract that one pair of pentagonal > numbers we found that meets all the criteria, store the pair in n, and > display them. > * ]n=.m#p2* > > *1560090 7042750* > > > NB. List a, b, a+b, & a-b of the discovered pair in n=a,b: > > * (,n),(+/"1 n),(|-/"1 n) * > > *1560090 7042750 8602840 5482660* > > > NB. Are the four integers a, b, a+b, & a-b all pentagonal numbers? > > *p e.~(,n),(+/"1 n),(|-/"1 n) * > > *1 1 1 1* > > > NB. Yes. So what is "D" (the difference between the pair) which is required > to get the final answer in the euler question? > > > *]D=.|-/"1 n* > > *5482660* > > > However the Euler 44 question wants to find a pentagonal pair where D is > minimised, so we will need to expand our search so see if there are > pentagonal pairs with a smaller D. Unfortunately, I run into memory limits > when I try to examine a larger range of pentagonal numbers. So I'll need to > break the one-shot approach into a loop and segment the array of pentagonal > numbers (sigh). I'll leave that exercise for the reader... > > > Skip Cave > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
