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
<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)