Erdős-primes

Definitions

In mathematics, Erdős primes are prime numbers such that all p-k! for 1<=k!<p are composite.

Task

Write a program to determine (and show here) all Erdős primes less than 2500.

Optionally, show the number of Erdős primes.

Stretch goal

Show that the 7875th Erdős prime is 999721

Also see

the OEIS entry: A064152 Erdos primes.

Factor

Works with: Factor version 0.99 2021-02-05

<lang>USING: formatting io kernel lists lists.lazy math math.factorials math.primes math.primes.lists math.vectors prettyprint sequences tools.memory.private ;

facts ( -- list ) 1 lfrom [ n! ] lmap-lazy ;

n!< ( p -- seq ) [ facts ] dip [ < ] curry lwhile list>array ;

erdős? ( p -- ? ) dup n!< n-v [ prime? ] none? ;

erdős ( -- list ) lprimes [ erdős? ] lfilter ;

erdős [ 2500 < ] lwhile list>array dup length "Found %d Erdős primes < 2500:\n" printf [ bl ] [ pprint ] interleave nl nl

erdős 7874 [ cdr ] times car commas "The 7,875th Erdős prime is %s.\n" printf</lang>

Output:

Found  25  Erdős primes < 2500:
2 101 211 367 409 419 461 557 673 709 769 937 967 1009 1201 1259 1709 1831 1889 2141 2221 2309 2351 2411 2437

The 7,875th Erdős prime is 999,721.

Phix

<lang Phix>atom t0 = time() sequence facts = {1} function erdos(integer p)

while facts[$]

0 then if is_prime(pmk) then return false end if end if end for return true end function sequence res = filter(get_primes_le(2500),erdos) printf(1,"Found %d Erdos primes < 2,500:\n%s\n\n",{length(res),join(apply(res,sprint))}) res = filter(get_primes_le(1000000),erdos) integer l = length(res) printf(1,"The %,d%s Erdos prime is %,d (%s)\n",{l,ord(l),res[$],elapsed(time()-t0)})</lang>

Output:

Found 25 Erdos primes < 2,500:
2 101 211 367 409 419 461 557 673 709 769 937 967 1009 1201 1259 1709 1831 1889 2141 2221 2309 2351 2411 2437

The 7,875th Erdos prime is 999,721 (1.2s)