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 7,875th Erdős prime is 999,721 (the highest below 1,000,000)
- Also see
-
- the OEIS entry: A064152 Erdos primes.
C++
<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.
F#
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
<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.
Go
<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.
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)
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.
Wren
<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.