Erdős-primes

Erdős-primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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)

REXX

<lang rexx>/*REXX program counts/displays the number of Erdos primes under a specified number N. */ parse arg n test cols . /*get optional number of primes to find*/ if n== | n=="," then n= 2500 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /* " " " " " */ Ocols= cols; cols= abs(cols) /*Use the absolute value of cols. */ call genP n /*generate all primes under N. */ w= 10 /*width of a number in any column. */ say ' index │'center(" Erdos primes that are < " n, 1 + cols*(w+1) ) say '───────┼'center("" , 1 + cols*(w+1), '─') call facts /*generate a table of needed factorials*/ Eprimes= 0; idx= 1 /*initialize # of additive primes & idx*/ idx= 1 $= /*a list of additive primes (so far). */

      do j=2  until j>=n; if \!.j  then iterate /*Is  J  not a prime? No, then skip it.*/
         do k=1  until fact.k>j                 /*verify: J-K! for 1≤K!<J are composite*/
         z= j - fact.k                          /*subtract some factorial from a prime.*/
         if !.z  then iterate j                 /*Is   Z   is a prime?   Then skip it. */
         end   /*j*/

      Eprimes= Eprimes + 1                      /*bump the count of Erdos primes.      */
      if Ocols<1            then iterate        /*Build the list  (to be shown later)? */
      c= commas(j)
      $= $ right(c, max(w, length(c) ) )        /*add Erdos prime to list, allow big #.*/
      if Eprimes//cols\==0  then iterate        /*have we populated a line of output?  */
      say center(idx, 7)'│'  substr($, 2);  $=  /*display what we have so far  (cols). */
      idx= idx + cols                           /*bump the  index  count for the output*/
      end   /*j*/

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'found ' Eprimes " Erdos primes < " n exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? facts: arg x; fact.=1; do x=2 until fact.x>n; p= x-1; fact.x= x*fact.p; end; return /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg n; @.=.; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; #= 7

     w= length(n);  !.=0; !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1;  !.13=1;  !.17=1
           do j=@.7+2  by 2  while j<n          /*continue on with the next odd prime. */
           parse var  j    -1  _              /*obtain the last digit of the  J  var.*/
           if _      ==5  then iterate          /*is this integer a multiple of five?  */
           if j // 3 ==0  then iterate          /* "   "     "    "     "     " three? */
                                                /* [↓]  divide by the primes.   ___    */
                 do k=4  to #  while  k*k<=j    /*divide  J  by other primes ≤ √ J     */
                 if j//@.k == 0  then iterate j /*÷ by prev. prime?  ¬prime     ___    */
                 end   /*k*/                    /* [↑]   only divide up to     √ J     */
           #= # + 1;          @.#= j;  !.j= 1   /*bump prime count; assign prime & flag*/
           end   /*j*/
    return</lang>

output   when using the default inputs:

 index │                                         Erdos primes that are  <  2500
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2        101        211        367        409        419        461        557        673        709
  11   │        769        937        967      1,009      1,201      1,259      1,709      1,831      1,889      2,141
  21   │      2,221      2,309      2,351      2,411      2,437

found  25  Erdos primes  <  2500