Since the Quora Challenge is a question on intervals it seems some sort of sieve calculation would be most efficient, because sieving means you don't have do start from scratch for each number in the interval.
About 8 years ago, I designed and implemented a model of p: in Dyalog APL, coded completely in APL http://dfns.dyalog.com/n_pco.htm . The design is the same as p: except that there is a new computation for a left argument of 10, wherein: If b=. 10 pco m,n then b is a boolean vector of length n-m and m+I.b are all the primes between m and n (>:m but < n). That is, b is a prime sieve. (Hence the 10 left argument, get it? :-) Y'all can implement this extension to the p: in J. Anyway, with this extension, the Quora Challenge can be met as follows: pc←{ p← 4 pco ⍺-1 q←1+¯4 pco ⍵+1 j←d⍳⌈/d←-2-/i←⍸10 pco p,q (p+i[j]+1)+⍳d[j]-1 } Translating from APL to J: p : the smallest prime >:x q : the largest prime <:y 10 pco p,q : the sieve to select all the primes between p and q ⍸ : APL equivalent of I. 2 -/ i : APL equivalent of 2 -/\ i d⍳⌈/d : the index of the maximum value in d ⍳ : APL equivalent of i. blah[k] : indexing My previous teaser showed that 2001401814+i.185 is an interval of composites. Checking that it is the longest such interval between 1e6+2e9 and 2e6+2e9 is left as an exercise for the reader. :-) On Sun, Sep 17, 2017 at 2:12 PM, Roger Hui <rogerhui.can...@gmail.com> wrote: > > I have some thoughts on solving this Quora Challenge which I will post > in a bit. > > First, a teaser, computed completely in Dyalog APL with no additional C > coding. > > t←(1e6+2e9) pc 2e6+2e9 > ⍴t > 185 > 5↑t > 2001401814 2001401815 2001401816 2001401817 2001401818 > ¯5↑t > 2001401994 2001401995 2001401996 2001401997 2001401998 > > t ≡ (1↑t)+⍳185 > 1 > > +/ 1 pco t > 0 > ⍝ that is, all composite > > 1 pco ( 1↑t)-1 > 1 > 1 pco (¯1↑t)+1 > 1 > ⍝ that is, the interval is bracketed by primes > > 1 1 cmpx '(1e6+2e9) pc 2e6+2e9' > 0.074125 > > Takes 0.074 seconds on my machine. > > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
