Erdős-primes: Difference between revisions

Content added Content deleted

Inline

Revision as of 15:05, 27 March 2021

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 7,875th Erdős prime is 999,721 (the highest below 1,000,000)

Also see

the OEIS entry: A064152 Erdos primes.

C++

Library: Primesieve

<lang cpp>#include <cstdint>

include <iomanip>
include <iostream>
include <set>
include <primesieve.hpp>

class erdos_prime_generator { public:

   erdos_prime_generator() {}
   uint64_t next();

private:

   bool erdos(uint64_t p) const;
   primesieve::iterator iter_;
   std::set<uint64_t> primes_;

};

uint64_t erdos_prime_generator::next() {

   uint64_t prime;
   for (;;) {
       prime = iter_.next_prime();
       primes_.insert(prime);
       if (erdos(prime))
           break;
   }
   return prime;

}

bool erdos_prime_generator::erdos(uint64_t p) const {

   for (uint64_t k = 1, f = 1; f < p; ++k, f *= k) {
       if (primes_.find(p - f) != primes_.end())
           return false;
   }
   return true;

}

int main() {

   std::wcout.imbue(std::locale(""));
   erdos_prime_generator epgen;
   const int max_print = 2500;
   const int max_count = 7875;
   uint64_t p;
   std::wcout << L"Erd\x151s primes less than " << max_print << L":\n";
   for (int count = 1; count <= max_count; ++count) {
       p = epgen.next();
       if (p < max_print)
           std::wcout << std::setw(6) << p << (count % 10 == 0 ? '\n' : ' ');
   }
   std::wcout << L"\n\nThe " << max_count << L"th Erd\x151s prime is " << p << L".\n";
   return 0;

}</lang>

Output:

Erdős primes less than 2,500:
     2    101    211    367    409    419    461    557    673    709
   769    937    967  1,009  1,201  1,259  1,709  1,831  1,889  2,141
 2,221  2,309  2,351  2,411  2,437 

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

This task uses Extensible Prime Generator (F#) <lang fsharp> // Erdős Primes. Nigel Galloway: March 22nd., 2021 let rec fN g=function 1->g |n->fN(g*n)(n-1) let rec fG n g=seq{let i=fN 1 n in if i<g then yield (isPrime>>not)(g-i); yield! fG(n+1) g} let eP()=primes32()|>Seq.filter(fG 1>>Seq.forall id) eP()|>Seq.takeWhile((>)2500)|>Seq.iter(printf "%d "); printfn "\n\n7875th Erdős prime is %d" (eP()|>Seq.item 7874) </lang>

Output:

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

7875th Erdos prime is 999721

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.

FreeBASIC

I won't bother reproducing a primality-testing function; use the one from Primality_by_trial_division#FreeBASIC. <lang freebasic>#include "isprime.bas"

function is_erdos_prime( p as uinteger ) as boolean

   if not isprime(p) then return false
   dim as uinteger kf=1, m=1
   while kf < p
       kf*=m : m+=1
       if isprime(p - kf) then return false
   wend
   return true

end function

dim as integer c = 0, i = 1 while c<7875

   i+=1
   if is_erdos_prime(i) then 
       c+=1
       if i<2500 or c=7875 then print c, i
   end if

wend</lang>

Output:

1 2

2 101 3 211 4 367 5 409 6 419 7 461 8 557 9 673 10 709 11 769 12 937 13 967 14 1009 15 1201 16 1259 17 1709 18 1831 19 1889 20 2141 21 2221 22 2309 23 2351 24 2411 25 2437 7875 999721

Forth

Works with: Gforth

<lang forth>: prime? ( n -- ? ) here + c@ 0= ;

notprime! ( n -- ) here + 1 swap c! ;

prime_sieve { n -- }

 here n erase
 0 notprime!
 1 notprime!
 n 4 > if
   n 4 do i notprime! 2 +loop
 then
 3
 begin
   dup dup * n <
 while
   dup prime? if
     n over dup * do
       i notprime!
     dup 2* +loop
   then
   2 +
 repeat
 drop ;

erdos_prime? { p -- ? }

 p prime? if
   1 1
   begin
     dup p <
   while
     p over - prime? if 2drop false exit then
     swap 1+ swap
     over *
   repeat
   2drop true
 else
   false
 then ;

print_erdos_primes { n -- }

 ." Erdos primes < " n 1 .r ." :" cr
 n prime_sieve
 0 0
 begin
   dup n <
 while
   dup erdos_prime? if
     dup 5 .r
     swap 1+ dup 10 mod 0= if cr then swap
   then
   1+
 repeat
 2drop ;

2500 print_erdos_primes cr bye</lang>

Output:

Erdos 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

Go

Translation of: Wren

<lang go>package main

import "fmt"

func sieve(limit int) []bool {

   limit++
   // True denotes composite, false denotes prime.
   c := make([]bool, limit) // all false by default
   c[0] = true
   c[1] = true
   for i := 4; i < limit; i += 2 {
       c[i] = true
   }
   p := 3 // Start from 3.
   for {
       p2 := p * p
       if p2 >= limit {
           break
       }
       for i := p2; i < limit; i += 2 * p {
           c[i] = true
       }
       for {
           p += 2
           if !c[p] {
               break
           }
       }
   }
   return c

}

func commatize(n int) string {

   s := fmt.Sprintf("%d", n)
   if n < 0 {
       s = s[1:]
   }
   le := len(s)
   for i := le - 3; i >= 1; i -= 3 {
       s = s[0:i] + "," + s[i:]
   }
   if n >= 0 {
       return s
   }
   return "-" + s

}

func main() {

   limit := int(1e6)
   c := sieve(limit - 1)
   var erdos []int
   for i := 2; i < limit; {
       if !c[i] {
           found := true
           for j, fact := 1, 1; fact < i; {
               if !c[i-fact] {
                   found = false
                   break
               }
               j++
               fact = fact * j
           }
           if found {
               erdos = append(erdos, i)
           }
       }
       if i > 2 {
           i += 2
       } else {
           i += 1
       }
   }
   lowerLimit := 2500
   var erdosLower []int
   for _, e := range erdos {
       if e < lowerLimit {
           erdosLower = append(erdosLower, e)
       } else {
           break
       }
   }
   fmt.Printf("The %d Erdős primes under %s are\n", len(erdosLower), commatize(lowerLimit))
   for i, e := range erdosLower {
       fmt.Printf("%6d", e)
       if (i+1)%10 == 0 {
           fmt.Println()
       }
   }
   show := 7875
   fmt.Printf("\n\nThe %s Erdős prime is %s.\n", commatize(show), commatize(erdos[show-1]))

}</lang>

Output:

The 25 Erdős primes under 2,500 are
     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,875 Erdős prime is 999,721.

Perl

Library: ntheory

<lang perl>use strict; use warnings; use feature 'say'; use utf8; binmode(STDOUT, ':utf8'); use List::AllUtils 'before'; use ntheory qw<is_prime factorial>;

sub is_erdos {

   my($n) = @_; my $k;
   return unless is_prime($n);
   while ($n > factorial($k++)) { return if is_prime $n-factorial($k) }
   'True'

}

my(@Erdős,$n); do { push @Erdős, $n if is_erdos(++$n) } until $n >= 1e6;

say 'Erdős primes < ' . (my $max = 2500) . ':'; say join ' ', before { $_ > 2500 } @Erdős; say "\nErdős prime #" . @Erdős . ' is ' . $Erdős[-1];</lang>

Output:

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

Erdős prime #7875 is 999721

Phix

atom t0 = time()
sequence facts = {1}
function erdos(integer p)
    while facts[$]<p do
        facts &= facts[$]*(length(facts)+1)
    end while
    for i=length(facts) to 1 by -1 do
        integer pmk = p-facts[i]
        if pmk>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)})

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)

Raku

<lang perl6>use Lingua::EN::Numbers;

my @factorial = 1, |[\*] 1..*; my @Erdős = ^Inf .grep: { .is-prime and none($_ «-« @factorial[^(@factorial.first: * > $_, :k)]).is-prime }

put 'Erdős primes < 2500:'; put @Erdős[^(@Erdős.first: * > 2500, :k)]»., put "\nThe 7,875th Erdős prime is: " ~ @Erdős[7874].,</lang>

Output:

Erdős primes < 2500:
2 101 211 367 409 419 461 557 673 709 769 937 967 1,009 1,201 1,259 1,709 1,831 1,889 2,141 2,221 2,309 2,351 2,411 2,437

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

REXX

<lang rexx>/*REXX program counts/displays the number of Erdos primes under a specified number N. */ parse arg n 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 /* " " " " " */ nn= n; n= abs(n) /*N<0: shows highest Erdos prime< │N│ */ call genP n /*generate all primes under N. */ w= 10 /*width of a number in any column. */ if cols>0 then say ' index │'center(" Erdos primes that are < " n, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') call facts /*generate a table of needed factorials*/ Eprimes= 0; idx= 1 /*initialize # of additive primes & idx*/ $= /*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;      EprimeL= j       /*bump the count of Erdos primes.      */
    if cols==0            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 ' commas(Eprimes) " Erdos primes < " commas(n) say if nn<0 then say commas(EprimeL) ' is the ' commas(Eprimes)th(Eprimes) " Erdos prime." 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>1e9; p= x-1; fact.x= x*fact.p; end; return th: parse arg th; return word('th st nd rd', 1+(th//10) *(th//100%10\==1) *(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ 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

output when using the inputs of: 1000000 0

found  7,875  Erdos primes  <  1,000,000

999,721  is the  7,875th  Erdos prime.

Rust

<lang rust>// [dependencies] // primal = "0.3"

use std::collections::HashSet;

fn erdos_primes() -> impl std::iter::Iterator<Item = usize> {

   let mut primes = HashSet::new();
   let mut all_primes = primal::Primes::all();
   std::iter::from_fn(move || {
       'all_primes: for p in all_primes.by_ref() {
           primes.insert(p);
           let mut k = 1;
           let mut f = 1;
           while f < p {
               if primes.contains(&(p - f)) {
                   continue 'all_primes;
               }
               k += 1;
               f *= k;
           }
           return Some(p);
       }
       None
   })

}

fn main() {

   let mut count = 0;
   println!("Erd\u{151}s primes less than 2500:");
   for p in erdos_primes().take_while(|x| *x < 2500) {
       count += 1;
       if count % 10 == 0 {
           println!("{:4}", p);
       } else {
           print!("{:4} ", p);
       }
   }
   println!();
   if let Some(p) = erdos_primes().nth(7874) {
       println!("\nThe 7875th Erd\u{151}s prime is {}.", p);
   }

}</lang>

Output:

Erdős primes less than 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 7875th Erdős prime is 999721.

Wren

Library: Wren-math

Library: Wren-seq

Library: Wren-fmt

<lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt

var limit = 1e6 var primes = Int.primeSieve(limit - 1, true) var erdos = [] for (p in primes) {

   var i = 1
   var fact = 1
   var found = true
   while (fact < p) {
       if (Int.isPrime(p - fact)) {
           found = false
           break
       }
       i = i + 1
       fact = fact * i
   }
   if (found) erdos.add(p)

} var lowerLimit = 2500 var erdosLower = erdos.where { |e| e < lowerLimit}.toList Fmt.print("The $,d Erdős primes under $,d are:", erdosLower.count, lowerLimit) for (chunk in Lst.chunks(erdosLower, 10)) Fmt.print("$6d", chunk) var show = 7875 Fmt.print("\nThe $,r Erdős prime is $,d.", show, erdos[show-1])</lang>

Output:

The 25 Erdős primes under 2,500 are:
     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.