Quick correction: the answer given by Pascal is not 1019 but P(2166)-P(1019), and my email should use that instead of 1019 wherever it is mentioned.
Sorry for the noise, Louis > On 14 Jul 2019, at 01:58, Louis de Forcrand <[email protected]> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
