Ramanujan primes: Difference between revisions
(Added Go) |
Didgeridoo52 (talk | contribs) (Added completed solution in python) |
||
(38 intermediate revisions by 16 users not shown) | |||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task|Prime Numbers}} |
||
As the integers get larger, the spacing between prime numbers slowly lengthens, but the spacing |
As the integers get larger, the spacing between prime numbers slowly lengthens, but the spacing |
||
Line 24: | Line 24: | ||
:* The Wikipedia entry: [https://en.wikipedia.org/wiki/Ramanujan_prime Ramanujan_prime]. |
:* The Wikipedia entry: [https://en.wikipedia.org/wiki/Ramanujan_prime Ramanujan_prime]. |
||
=={{header|ALGOL 68}}== |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # find some Ramanujan primes: the nth Ramanujan prime is the least n # |
|||
# such that there are at least n primes between x and x/2 for all x>=n # |
|||
PR read "primes.incl.a68" PR # include the prime utilities # |
|||
[]BOOL p = PRIMESIEVE 1 000 000; # generate a sieve of primes # |
|||
# find the highest numbers where the number of primes between x and x/2 # |
|||
# is at most n, store the list in hpx # |
|||
[ 0 : UPB p ]INT hpx; |
|||
BEGIN |
|||
# count the primes up to n # |
|||
[ 0 : UPB p ]INT pc; # pc[ n ]: count of primes up to n # |
|||
FOR i FROM LWB pc TO UPB pc DO pc[ i ] := 0 OD; |
|||
INT p count := 0; |
|||
FOR i TO UPB pc DO |
|||
IF p[ i ] THEN p count +:= 1 FI; |
|||
pc[ i ] := p count |
|||
OD; |
|||
# count the pimes between x and x/2 # |
|||
[ 0 : UPB p ]INT pc2; # pc2[ n ]: count of primes between n and n/2 # |
|||
FOR i FROM LWB pc2 TO UPB pc2 DO |
|||
pc2[ i ] := pc[ i ] - pc[ i OVER 2 ] |
|||
OD; |
|||
# find the highest x where the prime count between x and x/2 is x # |
|||
FOR i FROM LWB hpx TO UPB hpx DO hpx[ i ] := 0 OD; |
|||
FOR i FROM LWB hpx TO UPB hpx DO |
|||
hpx[ pc2[ i ] ] := i |
|||
OD |
|||
END; |
|||
# show the Ramanjan primes # |
|||
INT r count := 0; |
|||
INT power of 10 := 1 000; |
|||
FOR n FROM LWB hpx TO UPB hpx WHILE r count < 10 000 DO |
|||
# hpx[ n ] contains the highest number where the number of primes # |
|||
# between x and x/2 is at most n, so we need to find the next # |
|||
# prime >= n # |
|||
INT rp := hpx[ n ]; |
|||
WHILE NOT p[ rp ] DO rp +:= 1 OD; |
|||
IF ( r count +:= 1 ) <= 100 THEN |
|||
print( ( " ", whole( rp, -4 ) ) ); |
|||
IF r count MOD 20 = 0 THEN print( ( newline ) ) FI |
|||
ELIF r count = power of 10 THEN |
|||
print( ( "The ", whole( r count, -8 ), "th Ramanujan prime is: ", whole( rp, 0 ), newline ) ); |
|||
power of 10 *:= 10 |
|||
FI |
|||
OD |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1000th Ramanujan prime is: 19403 |
|||
The 10000th Ramanujan prime is: 242057 |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
==={{header|FreeBASIC}}=== |
|||
{{trans|Phix}} |
|||
<syntaxhighlight lang="vbnet">#define floor(x) ((x*2.0-0.5) Shr 1) |
|||
Dim Shared As Integer pi() |
|||
Sub primeCounter(limit As Integer) |
|||
Dim As Integer i, q, p, sq, total |
|||
Redim pi(limit) |
|||
pi(0) = 0 |
|||
pi(1) = 0 |
|||
For i = 2 To limit |
|||
pi(i) = 1 |
|||
Next |
|||
If limit > 2 Then |
|||
For i = 4 To limit Step 2 |
|||
pi(i) = 0 |
|||
Next i |
|||
p = 3 |
|||
sq = 9 |
|||
While sq <= limit |
|||
If pi(p) <> 0 Then |
|||
For q = sq To limit Step p*2 |
|||
pi(q) = 0 |
|||
Next q |
|||
End If |
|||
sq += (p + 1) * 4 |
|||
p += 2 |
|||
Wend |
|||
total = 0 |
|||
For i = 2 To limit |
|||
total += pi(i) |
|||
pi(i) = total |
|||
Next i |
|||
End If |
|||
End Sub |
|||
Function ramanujanMax(n As Integer) As Integer |
|||
Return floor(4 * n * Log(4*n)) |
|||
End Function |
|||
Function ramanujanPrime(n As Integer) As Integer |
|||
Dim As Integer i, maxposs |
|||
If n = 1 Then Return 2 |
|||
maxposs = ramanujanMax(n) |
|||
For i = maxposs - (maxposs Mod 2) To 1 Step -2 |
|||
If pi(i) - pi(i\2) < n Then Return i + 1 |
|||
Next i |
|||
Return 0 |
|||
End Function |
|||
Dim As Integer p, n, limit = 1e6 |
|||
Dim As Double t0 = Timer |
|||
primeCounter(ramanujanMax(limit)) |
|||
Print "The first 100 Ramanujan primes are:" |
|||
For p = 1 To 100 |
|||
Print Using " ####"; ramanujanPrime(p); |
|||
If p Mod 20 = 0 Then Print |
|||
Next p |
|||
Print |
|||
For p = 3 To 6 |
|||
n = 10 ^ p |
|||
Print Using "The &th Ramanujan prime is &"; n; ramanujanPrime(n) |
|||
Next p |
|||
Print Using "##.##sec."; Timer - t0 |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>The first 100 Ramanujan primes are: |
|||
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1000th Ramanujan prime is 19403 |
|||
The 10000th Ramanujan prime is 242057 |
|||
The 100000th Ramanujan prime is 2916539 |
|||
The 1000000th Ramanujan prime is 34072993 |
|||
1.53sec.</pre> |
|||
==={{header|Yabasic}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vbnet">dim cnt(1e6) |
|||
primeCounter(ramanujanMax((1e6))) |
|||
print "The first 100 Ramanujan primes are:" |
|||
for p = 1 to 100 |
|||
print ramanujanPrime(p) using ("#####"); |
|||
if mod(p, 20) = 0 print |
|||
next p |
|||
print |
|||
for p = 3 to 6 |
|||
n = 10 ^ p |
|||
print "The ", n, "th Ramanujan prime is ", ramanujanPrime(n) |
|||
next p |
|||
print peek("millisrunning") / 1000, "sec." |
|||
end |
|||
sub primeCounter(limit) |
|||
local i, q, p, sq, total |
|||
redim cnt(limit) |
|||
cnt(0) = 0 |
|||
cnt(1) = 0 |
|||
for i = 2 to limit |
|||
cnt(i) = 1 |
|||
next |
|||
if limit > 2 then |
|||
for i = 4 to limit step 2 |
|||
cnt(i) = 0 |
|||
next i |
|||
p = 3 |
|||
sq = 9 |
|||
while sq <= limit |
|||
if cnt(p) <> 0 then |
|||
for q = sq to limit step p*2 |
|||
cnt(q) = 0 |
|||
next q |
|||
fi |
|||
sq = sq + (p + 1) * 4 |
|||
p = p + 2 |
|||
wend |
|||
total = 0 |
|||
for i = 2 to limit |
|||
total = total + cnt(i) |
|||
cnt(i) = total |
|||
next i |
|||
fi |
|||
end sub |
|||
sub ramanujanMax(n) |
|||
return floor(4 * n * log(4*n)) |
|||
end sub |
|||
sub ramanujanPrime(n) |
|||
local i, maxposs |
|||
if n = 1 return 2 |
|||
maxposs = ramanujanMax(n) |
|||
for i = maxposs - mod(maxposs, 2) to 1 step -2 |
|||
if cnt(i) - cnt(floor(i/2)) < n return i + 1 |
|||
next i |
|||
return 0 |
|||
end sub</syntaxhighlight> |
|||
{{out}} |
|||
<pre>The first 100 Ramanujan primes are: |
|||
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1000th Ramanujan prime is 19403 |
|||
The 10000th Ramanujan prime is 242057 |
|||
The 100000th Ramanujan prime is 2916539 |
|||
The 1000000th Ramanujan prime is 34072993 |
|||
35.14sec.</pre> |
|||
=={{header|C++}}== |
|||
{{trans|Julia}} |
|||
<syntaxhighlight lang="cpp">#include <chrono> |
|||
#include <cmath> |
|||
#include <iomanip> |
|||
#include <iostream> |
|||
#include <numeric> |
|||
#include <vector> |
|||
class prime_counter { |
|||
public: |
|||
explicit prime_counter(int limit); |
|||
int prime_count(int n) const { return n < 1 ? 0 : count_.at(n); } |
|||
private: |
|||
std::vector<int> count_; |
|||
}; |
|||
prime_counter::prime_counter(int limit) : count_(limit, 1) { |
|||
if (limit > 0) |
|||
count_[0] = 0; |
|||
if (limit > 1) |
|||
count_[1] = 0; |
|||
for (int i = 4; i < limit; i += 2) |
|||
count_[i] = 0; |
|||
for (int p = 3, sq = 9; sq < limit; p += 2) { |
|||
if (count_[p]) { |
|||
for (int q = sq; q < limit; q += p << 1) |
|||
count_[q] = 0; |
|||
} |
|||
sq += (p + 1) << 2; |
|||
} |
|||
std::partial_sum(count_.begin(), count_.end(), count_.begin()); |
|||
} |
|||
int ramanujan_max(int n) { |
|||
return static_cast<int>(std::ceil(4 * n * std::log(4 * n))); |
|||
} |
|||
int ramanujan_prime(const prime_counter& pc, int n) { |
|||
int max = ramanujan_max(n); |
|||
for (int i = max; i >= 0; --i) { |
|||
if (pc.prime_count(i) - pc.prime_count(i / 2) < n) |
|||
return i + 1; |
|||
} |
|||
return 0; |
|||
} |
|||
int main() { |
|||
std::cout.imbue(std::locale("")); |
|||
auto start = std::chrono::high_resolution_clock::now(); |
|||
prime_counter pc(1 + ramanujan_max(100000)); |
|||
for (int i = 1; i <= 100; ++i) { |
|||
std::cout << std::setw(5) << ramanujan_prime(pc, i) |
|||
<< (i % 10 == 0 ? '\n' : ' '); |
|||
} |
|||
std::cout << '\n'; |
|||
for (int n = 1000; n <= 100000; n *= 10) { |
|||
std::cout << "The " << n << "th Ramanujan prime is " << ramanujan_prime(pc, n) |
|||
<< ".\n"; |
|||
} |
|||
auto end = std::chrono::high_resolution_clock::now(); |
|||
std::cout << "\nElapsed time: " |
|||
<< std::chrono::duration<double>(end - start).count() * 1000 |
|||
<< " milliseconds\n"; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 |
|||
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 |
|||
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 |
|||
The 1,000th Ramanujan prime is 19,403. |
|||
The 10,000th Ramanujan prime is 242,057. |
|||
The 100,000th Ramanujan prime is 2,916,539. |
|||
Elapsed time: 46.0828 milliseconds |
|||
</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
Uses the [[Extensible_prime_generator#Delphi|Delphi Prime-Generator Object]] |
|||
<syntaxhighlight lang="Delphi"> |
|||
procedure ShowRamanujanPrimes(Memo: TMemo); |
|||
var S: string; |
|||
var PrimeCounts: array of Integer; |
|||
var Sieve: TPrimeSieve; |
|||
var I,Cnt,P: integer; |
|||
const Size = 1000000; |
|||
function GetRamanujanMax(N: integer): integer; |
|||
{Get maximum possible Ramanujan for a particular N} |
|||
begin |
|||
Result:=Ceil(4 * N * (log(4 * N) / log(2))); |
|||
end; |
|||
function RamanujanPrime(N: integer): integer; |
|||
{Find largest I for Pi[I]-Pi[I/2]<N, Pi[I] is count primes less than I} |
|||
var I: integer; |
|||
begin |
|||
for I:=GetRamanujanMax(N) downto 0 do |
|||
if (PrimeCounts[I] - PrimeCounts[I div 2]) < N then |
|||
begin |
|||
Result:=I+1; |
|||
exit; |
|||
end; |
|||
Result:=0; |
|||
end; |
|||
begin |
|||
Sieve:=TPrimeSieve.Create; |
|||
try |
|||
{Get primes up to 1 million} |
|||
Sieve.Intialize(Size); |
|||
{Count total number of primes up to a specific number} |
|||
SetLength(PrimeCounts,Size); |
|||
Cnt:=0; |
|||
for I:=0 to Sieve.Count-1 do |
|||
begin |
|||
if Sieve.Flags[I] then Inc(Cnt); |
|||
PrimeCounts[I]:=Cnt; |
|||
end; |
|||
{display first 100 Ramanujan Prime} |
|||
S:=''; |
|||
for I:=1 to 100 do |
|||
begin |
|||
P:=RamanujanPrime(I); |
|||
S:=S+Format('%5d',[P]); |
|||
if (I mod 10)=0 then S:=S+CRLF; |
|||
end; |
|||
Memo.Lines.Add(S); |
|||
P:=RamanujanPrime(1000); |
|||
Memo.Lines.Add('1,000th Prime: '+IntToStr(P)); |
|||
P:=RamanujanPrime(10000); |
|||
Memo.Lines.Add('10,000th Prime: '+IntToStr(P)); |
|||
finally Sieve.Free; end; |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 |
|||
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
1,000th Prime: 19403 |
|||
10,000th Prime: 242057 |
|||
Elapsed Time: 19.269 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight> |
|||
global cnt[] . |
|||
proc primcnt limit . . |
|||
cnt[] = [ 0 1 1 ] |
|||
for i = 4 step 2 to limit |
|||
cnt[] &= 0 |
|||
cnt[] &= 1 |
|||
. |
|||
p = 3 |
|||
sq = 9 |
|||
while sq <= limit |
|||
if cnt[p] <> 0 |
|||
for q = sq step p * 2 to limit |
|||
cnt[q] = 0 |
|||
. |
|||
. |
|||
sq += (p + 1) * 4 |
|||
p += 2 |
|||
. |
|||
for i = 2 to limit |
|||
sum += cnt[i] |
|||
cnt[i] = sum |
|||
. |
|||
. |
|||
func log n . |
|||
e = 2.7182818284590452354 |
|||
return log10 n / log10 e |
|||
. |
|||
func ramamax n . |
|||
return floor (4 * n * log (4 * n)) |
|||
. |
|||
func ramaprim n . |
|||
if n = 1 |
|||
return 2 |
|||
. |
|||
for i = ramamax n downto 2 * n |
|||
if i mod 2 = 0 |
|||
if cnt[i] - cnt[i / 2] < n |
|||
return i + 1 |
|||
. |
|||
. |
|||
. |
|||
return 0 |
|||
. |
|||
primcnt (1 + ramamax 1000) |
|||
print "The first 100 Ramanujan primes are:" |
|||
for i = 1 to 100 |
|||
write ramaprim i & " " |
|||
. |
|||
print "" |
|||
print "" |
|||
print "The 1000th Ramanujan prime is " & ramaprim 1000 |
|||
</syntaxhighlight> |
|||
=={{header|F_Sharp|F#}}== |
|||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
|||
<syntaxhighlight lang="fsharp"> |
|||
// Ramanujan primes. Nigel Galloway: September 7th., 2021 |
|||
let fN g=if isPrime g then 1 else if g%2=1 then 0 else if isPrime(g/2) then -1 else 0 |
|||
let rP p=let N,G=Array.create p 0,(Seq.item(3*p-2)(primes32()))+1 in let rec fG n g=if g=G then N else(if n<p then N.[n]<-g); fG(n+(fN g))(g+1) in fG 0 1 |
|||
let n=rP 100000 |
|||
n.[0..99]|>Array.iter(printf "%d "); printfn "" |
|||
[1000;10000;100000]|>List.iter(fun g->printf $"The %d{g}th Ramanujan prime is %d{n.[g-1]}\n" ) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1000th Ramanujan prime is 19403 |
|||
The 10000th Ramanujan prime is 242057 |
|||
The 100000th Ramanujan prime is 2916539 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans| |
{{trans|C++}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
<br> |
|||
A decent time though not as quick as Phix. |
|||
This takes about 40 ms to find the 100,000th Ramanujan prime on my machine. The millionth takes about 520 ms. |
|||
<lang go>package main |
|||
<syntaxhighlight lang="go">package main |
|||
import ( |
import ( |
||
Line 35: | Line 506: | ||
"math" |
"math" |
||
"rcu" |
"rcu" |
||
"sort" |
|||
"time" |
"time" |
||
) |
) |
||
var |
var count []int |
||
func primeCounter(limit int) { |
|||
var primes = rcu.Primes(700000) // say |
|||
count = make([]int, limit) |
|||
for i := 0; i < limit; i++ { |
|||
count[i] = 1 |
|||
} |
|||
if limit > 0 { |
|||
count[0] = 0 |
|||
} |
|||
if limit > 1 { |
|||
count[1] = 0 |
|||
} |
|||
for i := 4; i < limit; i += 2 { |
|||
count[i] = 0 |
|||
} |
|||
for p, sq := 3, 9; sq < limit; p += 2 { |
|||
if count[p] != 0 { |
|||
for q := sq; q < limit; q += p << 1 { |
|||
count[q] = 0 |
|||
} |
|||
} |
|||
sq += (p + 1) << 2 |
|||
} |
|||
sum := 0 |
|||
for i := 0; i < limit; i++ { |
|||
sum += count[i] |
|||
count[i] = sum |
|||
} |
|||
} |
|||
func |
func primeCount(n int) int { |
||
if n < 1 { |
|||
return 0 |
|||
} |
|||
return count[n] |
|||
} |
|||
func ramanujanMax(n int) int { |
|||
fn := float64(n) |
fn := float64(n) |
||
return int(math.Ceil(4 * fn * math.Log(4*fn))) |
|||
} |
|||
pi := sort.SearchInts(primes[2*n:], max) // binary search from min of (2n)th prime |
|||
for { |
|||
func ramanujanPrime(n int) int { |
|||
if pi+1-rcu.PrimeCount(primes[pi]/2) <= n { |
|||
if n == 1 { |
|||
return 2 |
|||
} |
|||
for i := ramanujanMax(n); i >= 2*n; i-- { |
|||
if i%2 == 1 { |
|||
continue |
|||
} |
|||
if primeCount(i)-primeCount(i/2) < n { |
|||
return i + 1 |
|||
} |
} |
||
pi-- |
|||
} |
} |
||
return 0 |
return 0 |
||
Line 57: | Line 568: | ||
func main() { |
func main() { |
||
start := time.Now() |
|||
primeCounter(1 + ramanujanMax(1e6)) |
|||
fmt.Println("The first 100 Ramanujan primes are:") |
fmt.Println("The first 100 Ramanujan primes are:") |
||
rams := make([]int, 100) |
rams := make([]int, 100) |
||
for n := 0; n < 100; n++ { |
for n := 0; n < 100; n++ { |
||
rams[n] = |
rams[n] = ramanujanPrime(n + 1) |
||
} |
} |
||
for i, r := range rams { |
for i, r := range rams { |
||
Line 69: | Line 582: | ||
} |
} |
||
fmt.Printf("\nThe 1,000th Ramanujan prime is %6s\n", rcu.Commatize( |
fmt.Printf("\nThe 1,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujanPrime(1000))) |
||
fmt.Printf("\nThe 10,000th Ramanujan |
fmt.Printf("\nThe 10,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujanPrime(10000))) |
||
fmt.Printf("\nThe 100,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujanPrime(100000))) |
|||
fmt.Printf("\nThe 1,000,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujanPrime(1000000))) |
|||
fmt.Println("\nTook", time.Since(start)) |
fmt.Println("\nTook", time.Since(start)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 92: | Line 609: | ||
The 1,000th Ramanujan prime is 19,403 |
The 1,000th Ramanujan prime is 19,403 |
||
The 10,000th Ramanujan |
The 10,000th Ramanujan prime is 242,057 |
||
The 100,000th Ramanujan prime is 2,916,539 |
|||
Took 946.193311ms |
|||
The 1,000,000th Ramanujan prime is 34,072,993 |
|||
Took 519.655163ms |
|||
</pre> |
|||
=={{header|Java}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="java">import java.util.Arrays; |
|||
public class RamanujanPrimes { |
|||
public static void main(String[] args) { |
|||
long start = System.nanoTime(); |
|||
System.out.println("First 100 Ramanujan primes:"); |
|||
PrimeCounter pc = new PrimeCounter(1 + ramanujanMax(100000)); |
|||
for (int i = 1; i <= 100; ++i) { |
|||
int p = ramanujanPrime(pc, i); |
|||
System.out.printf("%,5d%c", p, i % 10 == 0 ? '\n' : ' '); |
|||
} |
|||
System.out.println(); |
|||
for (int i = 1000; i <= 100000; i *= 10) { |
|||
int p = ramanujanPrime(pc, i); |
|||
System.out.printf("The %,dth Ramanujan prime is %,d.\n", i, p); |
|||
} |
|||
long end = System.nanoTime(); |
|||
System.out.printf("\nElapsed time: %.1f milliseconds\n", (end - start) / 1e6); |
|||
} |
|||
private static int ramanujanMax(int n) { |
|||
return (int)Math.ceil(4 * n * Math.log(4 * n)); |
|||
} |
|||
private static int ramanujanPrime(PrimeCounter pc, int n) { |
|||
for (int i = ramanujanMax(n); i >= 0; --i) { |
|||
if (pc.primeCount(i) - pc.primeCount(i / 2) < n) |
|||
return i + 1; |
|||
} |
|||
return 0; |
|||
} |
|||
private static class PrimeCounter { |
|||
private PrimeCounter(int limit) { |
|||
count = new int[limit]; |
|||
Arrays.fill(count, 1); |
|||
if (limit > 0) |
|||
count[0] = 0; |
|||
if (limit > 1) |
|||
count[1] = 0; |
|||
for (int i = 4; i < limit; i += 2) |
|||
count[i] = 0; |
|||
for (int p = 3, sq = 9; sq < limit; p += 2) { |
|||
if (count[p] != 0) { |
|||
for (int q = sq; q < limit; q += p << 1) |
|||
count[q] = 0; |
|||
} |
|||
sq += (p + 1) << 2; |
|||
} |
|||
Arrays.parallelPrefix(count, (x, y) -> x + y); |
|||
} |
|||
private int primeCount(int n) { |
|||
return n < 1 ? 0 : count[n]; |
|||
} |
|||
private int[] count; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 100 Ramanujan primes: |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 |
|||
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 |
|||
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 |
|||
The 1,000th Ramanujan prime is 19,403. |
|||
The 10,000th Ramanujan prime is 242,057. |
|||
The 100,000th Ramanujan prime is 2,916,539. |
|||
Elapsed time: 187.2 milliseconds |
|||
</pre> |
|||
=={{header|J}}== |
|||
<syntaxhighlight lang=j> result=. (((] - _1&(33 b.)@:>:@[ { ]) _1&p:) i. 3e6) i: i. 1e5 |
|||
_10 ]\ 100 {. result |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 |
|||
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
(10 <:@^ 3 4 5) { result |
|||
19403 242057 2916539</syntaxhighlight> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
{{works with|jq}} |
|||
<syntaxhighlight lang=jq> |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .; |
|||
# tabular print |
|||
def tprint(columns; wide): |
|||
reduce _nwise(columns) as $row (""; |
|||
. + ($row|map(lpad(wide)) | join(" ")) + "\n" ); |
|||
# output: {count} |
|||
def primeCounter($limit): |
|||
{count: [range(0; $limit) | 1] } |
|||
| if ($limit > 0) then .count[0] = 0 else . end |
|||
| if ($limit > 1) then .count[1] = 0 else . end |
|||
| .count |= reduce range(4; $limit; 2) as $i (.; .[$i] = 0) |
|||
| .p = 3 |
|||
| .sq = 9 |
|||
| until(.sq >= $limit; |
|||
if (.count[.p] != 0) |
|||
then .q = .sq |
|||
| until (.q >= $limit; |
|||
.count[.q] = 0 |
|||
| .q += (.p * 2) ) |
|||
else . |
|||
end |
|||
| .sq += ((.p + 1) * 4) |
|||
| .p += 2 ) |
|||
| .sum = 0 |
|||
| reduce range(0; $limit) as $i (.; |
|||
.sum += .count[$i] |
|||
| .count[$i] = .sum ) ; |
|||
# input: {count} |
|||
def primeCount($n): if $n < 1 then 0 else .count[$n] end; |
|||
# 2n ln 2n < Rn < 4n ln 4n |
|||
def ramanujanMax(n): (4 * n * ((4*n)|log))|ceil; |
|||
# input: {count} |
|||
def ramanujanPrime($n): |
|||
if ($n == 1) then 2 |
|||
else first( foreach range(ramanujanMax($n); 1+2*$n; -1) as $i (.emit=null; |
|||
if ($i % 2 == 1) then . |
|||
elif (primeCount($i) - primeCount(($i/2)|floor) < $n) then .emit=$i + 1 |
|||
else . |
|||
end) |
|||
| select(.emit).emit ) // 0 |
|||
end ; |
|||
# The tasks |
|||
primeCounter(1 + ramanujanMax(1e6)) |
|||
| "The first 100 Ramanujan primes are:", |
|||
( [range(1;101) as $i | ramanujanPrime($i) ] |
|||
| tprint(10; 5) ), |
|||
"\nThe 1,000th Ramanujan prime is \(ramanujanPrime(1000))", |
|||
"\nThe 10,000th Ramanujan prime is \(ramanujanPrime(10000))", |
|||
"\nThe 100,000th Ramanujan prime is \(ramanujanPrime(100000))", |
|||
"\nThe 1,000,000th Ramanujan prime is \(ramanujanPrime(1000000))" |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
The first 100 Ramanujan primes are: |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 |
|||
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1,000th Ramanujan prime is 19403 |
|||
The 10,000th Ramanujan prime is 242057 |
|||
The 100,000th Ramanujan prime is 2916539 |
|||
The 1,000,000th Ramanujan prime is 34072993 |
|||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<lang |
<syntaxhighlight lang="julia">using Primes |
||
@time let |
|||
const MASK = [[false]] |
|||
MASK = primesmask(625000) |
|||
PIVEC = accumulate(+, MASK) |
|||
PI(n) = n < 1 ? 0 : PIVEC[n] |
|||
function Ramanujan_prime(n) |
|||
maxposs = Int(ceil(4n * (log(4n) / log(2)))) |
|||
if n > length(first(MASK)) |
|||
for i in maxposs:-1:1 |
|||
PI(i) - PI(i ÷ 2) < n && return i + 1 |
|||
end |
|||
return 0 |
|||
end |
end |
||
return sum(@view first(MASK)[1:n]) |
|||
end |
|||
for i in 1:100 |
|||
function Ramanujan_prime(n) |
|||
print(lpad(Ramanujan_prime(i), 5), i % 20 == 0 ? "\n" : "") |
|||
maxposs = Int(ceil(4n * (log(4n) / log(2)))) |
|||
for i in maxposs:-1:1 |
|||
PI(i) - PI(i ÷ 2) < n && return i + 1 |
|||
end |
end |
||
return 0 |
|||
end |
|||
println("\nThe 1000th Ramanujan prime is ", Ramanujan_prime(1000)) |
|||
for i in 1:100 |
|||
println("\nThe 10,000th Ramanujan prime is ", Ramanujan_prime(10000)) |
|||
print(lpad(Ramanujan_prime(i), 5), i % 20 == 0 ? "\n" : "") |
|||
end |
end |
||
</syntaxhighlight>{{out}} |
|||
println("\nThe 1000th Ramanujan prime is ", Ramanujan_prime(1000)) |
|||
println("\nThe 10,000th Ramanujan prime is ", Ramanujan_prime(10000)) |
|||
</lang>{{out}} |
|||
<pre> |
<pre> |
||
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
||
Line 136: | Line 841: | ||
The 10,000th Ramanujan prime is 242057 |
The 10,000th Ramanujan prime is 242057 |
||
0.272471 seconds (625.44 k allocations: 38.734 MiB, 33.07% compilation time) |
|||
</pre> |
</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">l = PrimePi[Range[10^6]] - PrimePi[Range[10^6]/2]; |
|||
Multicolumn[1 + Position[l, #][[-1, 1]] & /@ Range[0, 99], {Automatic, 10}, Appearance -> "Horizontal"] |
|||
1 + Position[l, 999][[-1, 1]] |
|||
1 + Position[l, 9999][[-1, 1]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 |
|||
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
19403 |
|||
242057</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|C++}} |
|||
I compiled using command <code>nim c -d:release -d:lto --gc:arc ramanujan_primes.nim</code>, i.e. with runtime checks on, link time optimization and using Arc garbage collector. To find the 100_000th Ramanujan prime, the program runs in about 100 ms on my laptop (i5-8250U CPU @ 1.60GHz, 8 GB Ram, Linux Manjaro). |
|||
<syntaxhighlight lang="nim">import math, sequtils, strutils, times |
|||
let t0 = now() |
|||
type PrimeCounter = seq[int] |
|||
proc initPrimeCounter(limit: Positive): PrimeCounter = |
|||
doAssert limit > 1 |
|||
result = repeat(1, limit) |
|||
result[0] = 0 |
|||
result[1] = 0 |
|||
for i in countup(4, limit - 1, 2): result[i] = 0 |
|||
var p = 3 |
|||
var p2 = 9 |
|||
while p2 < limit: |
|||
if result[p] != 0: |
|||
for q in countup(p2, limit - 1, p shl 1): |
|||
result[q] = 0 |
|||
p2 += (p + 1) shl 2 |
|||
if p2 >= limit: break |
|||
inc p, 2 |
|||
# Compute partial sums in place. |
|||
var sum = 0 |
|||
for item in result.mitems: |
|||
sum += item |
|||
item = sum |
|||
func ramanujanMax(n: int): int {.inline.} = int(ceil(4 * n.toFloat * ln(4 * n.toFloat))) |
|||
proc ramanujanPrime(pi: PrimeCounter; n: int): int = |
|||
if n == 1: return 2 |
|||
var max = ramanujanMax(n) |
|||
if (max and 1) == 1: dec max |
|||
for i in countdown(max, 2, 2): |
|||
if pi[i] - pi[i div 2] < n: |
|||
return i + 1 |
|||
let pi = initPrimeCounter(1 + ramanujanMax(100_000)) |
|||
for n in 1..100: |
|||
stdout.write ($ramanujanPrime(pi, n)).align(4), if n mod 20 == 0: '\n' else: ' ' |
|||
echo "\nThe 1000th Ramanujan prime is ", ramanujanPrime(pi, 1_000) |
|||
echo "The 10_000th Ramanujan prime is ", ramanujanPrime(pi, 10_000) |
|||
echo "The 100_000th Ramanujan prime is ", ramanujanPrime(pi, 100_000) |
|||
echo "\nElapsed time: ", (now() - t0).inMilliseconds, " ms"</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1000th Ramanujan prime is 19403 |
|||
The 10_000th Ramanujan prime is 242057 |
|||
The 100_000th Ramanujan prime is 2916539 |
|||
Elapsed time: 99 ms</pre> |
|||
=={{header|Perl}}== |
|||
{{trans|Raku}} |
|||
{{libheader|ntheory}} |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
use ntheory 'primes'; |
|||
sub count { |
|||
my($n,$p) = @_; |
|||
my $c = -1; |
|||
do { $c++ } until $$p[$c] > $n; |
|||
return $c; |
|||
} |
|||
my(@rp,@mem); |
|||
my $primes = primes( 100_000_000 ); |
|||
sub r_prime { |
|||
my $n = shift; |
|||
for my $x ( reverse 1 .. int 4*$n * log(4*$n) / log 2 ) { |
|||
my $y = int $x / 2; |
|||
return 1 + $x if ($mem[$x] //= count($x,$primes)) - ($mem[$y] //= count($y,$primes)) < $n |
|||
} |
|||
} |
|||
push @rp, r_prime($_) for 1..100; |
|||
print "First 100:\n" . (sprintf "@{['%5d' x 100]}", @rp) =~ s/(.{100})/$1\n/gr; |
|||
print "\n\n 1000th: " . r_prime( 1000) . "\n"; |
|||
print "\n10000th: " . r_prime(10000) . "\n"; # faster with 'ntheory' function 'ramanujan_primes'</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 100: |
|||
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
1000th: 19403 |
|||
10000th: 242057</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans| |
{{trans|Go}} |
||
{{libheader|Phix/online}} |
{{libheader|Phix/online}} |
||
You can run this online [http://phix.x10.mx/p2js/Ramanujan_primes.htm here]. |
You can run this online [http://phix.x10.mx/p2js/Ramanujan_primes.htm here]. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;"> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">picache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #008080;"> |
<span style="color: #008080;">procedure</span> <span style="color: #000000;">primeCounter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span> |
||
<span style="color: # |
<span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;"> |
<span style="color: #008080;">if</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
||
<span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: # |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
||
<span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;"> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span> |
||
<span style="color: #008080;">while</span> <span style="color: #000000;">sq</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sq</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">sq</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span> |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">total</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;"> |
<span style="color: #008080;">function</span> <span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
||
<span style="color: # |
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">2</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: # |
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxposs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxposs</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxposs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> |
<span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 169: | Line 1,019: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #004080;"> |
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">5</span><span style="color: #0000FF;">:</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">primeCounter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)))</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">),</span><span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%5d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%5d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">))</span> |
||
<span style="color: # |
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %,dth Ramanujan prime is %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</lang>--> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 183: | Line 1,037: | ||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
||
The |
The 1,000th Ramanujan prime is 19,403 |
||
The 10,000th Ramanujan prime is |
The 10,000th Ramanujan prime is 242,057 |
||
The 100,000th Ramanujan prime is 2,916,539 |
|||
"0.6s" |
|||
The 1,000,000th Ramanujan prime is 34,072,993 |
|||
"2.7s" |
|||
</pre> |
</pre> |
||
<small>The last line is omitted under pwa/p2js since the primeCounter array is too much for Javascript to handle.</small> |
|||
=={{header|Python}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="python"> |
|||
import time |
|||
import math |
|||
class PrimeCounter: |
|||
"""Generate a list 'count' where count[n] is the number of primes less than or equal to n""" |
|||
def __init__(self, limit): |
|||
self.count = [1] * limit |
|||
count = self.count |
|||
if limit > 0: |
|||
count[0] = 0 |
|||
if limit > 1: |
|||
count[1] = 0 |
|||
for i in range(4, limit, 2): |
|||
count[i] = 0 |
|||
p = 3 |
|||
while p**2 < limit: |
|||
if count[p] != 0: |
|||
q = p**2 |
|||
while q < limit: |
|||
count[q] = 0 |
|||
q += p * 2 |
|||
p += 2 |
|||
for i, j in enumerate(count): |
|||
if i == 0: |
|||
continue |
|||
count[i] += count[i - 1] |
|||
def prime_count(self, n): |
|||
"""Get the number of primes less than or equal to n""" |
|||
if n > 0: |
|||
return self.count[n] |
|||
return 0 |
|||
def ramanujan_prime_upper_bound(n): |
|||
"""Calculate the largest number the nth Ramanujan number could possibly be""" |
|||
return math.ceil(4 * n * math.log(4 * n)) |
|||
def ramanujan_prime(prime_counter_in, n): |
|||
"""Generate the nth Ramanujan prime by finding the largest number 'i' where less than n primes are in the |
|||
range i//2 and i - the Ramanujan prime is one more than i""" |
|||
pci = prime_counter_in |
|||
for i in range(ramanujan_prime_upper_bound(n), -1, -1): |
|||
pi_n = pci.prime_count(i) |
|||
pi_half_n = pci.prime_count(i // 2) |
|||
if pi_n - pi_half_n < n: |
|||
return i + 1 |
|||
return 0 |
|||
def print_ramanujan_primes_in_range(start_number, end_number, prime_counter_in): |
|||
"""Print all Ramanujan primes between start_number (inclusive) and end_number (exclusive)""" |
|||
for i in range(start_number, end_number): |
|||
p = ramanujan_prime(prime_counter_in, i) |
|||
print(f"{p : <4}", end=" ") |
|||
if i % 10 == 0: |
|||
print() |
|||
def solve(): |
|||
"""Return the first 100 Ramanujan primes and the 1000th, 10000th & 100000th Ramanujan primes""" |
|||
print("First 100 Ramanujan primes:\n") |
|||
largest_number_to_calculate = ramanujan_prime_upper_bound(100000) + 1 |
|||
prime_counter = PrimeCounter(largest_number_to_calculate) |
|||
print_ramanujan_primes_in_range(1, 101, prime_counter) |
|||
print() |
|||
for number in (1_000, 10_000, 100_000): |
|||
answer = ramanujan_prime(prime_counter, number) |
|||
print( |
|||
f"The {number : >6}th ramanujan prime is {answer : >7}" |
|||
) |
|||
start = time.perf_counter() |
|||
solve() |
|||
end = time.perf_counter() |
|||
time_taken_ms = int((end - start) * 1000) |
|||
print(f"\nElapsed time: {time_taken_ms}ms")</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 100 Ramanujan primes: |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1009 1019 1021 1031 1049 1051 1061 1063 |
|||
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 |
|||
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 |
|||
The 1000th ramanujan prime is 19403 |
|||
The 10000th ramanujan prime is 242057 |
|||
The 100000th ramanujan prime is 2916539 |
|||
Elapsed time: 1460ms |
|||
</pre> |
|||
=={{header|Raku}}== |
|||
All timings are purely informational. Will vary by system specs and load. |
|||
=== Pure Raku === |
|||
<syntaxhighlight lang="raku" line>use Math::Primesieve; |
|||
use Lingua::EN::Numbers; |
|||
my $primes = Math::Primesieve.new; |
|||
my @mem; |
|||
sub ramanujan-prime (\n) { |
|||
1 + (1..(4×n × (4×n).log / 2.log).floor).first: :end, -> \x { |
|||
my \y = x div 2; |
|||
((@mem[x] //= $primes.count(x)) - (@mem[y] //= $primes.count(y))) < n |
|||
} |
|||
} |
|||
say 'First 100:'; |
|||
say (1..100).map( &ramanujan-prime ).batch(10)».&comma».fmt("%6s").join: "\n"; |
|||
say "\n 1,000th: { comma 1000.&ramanujan-prime }"; |
|||
say "10,000th: { comma 10000.&ramanujan-prime }"; |
|||
say (now - INIT now).fmt('%.3f') ~ ' seconds';</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 100: |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 |
|||
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 |
|||
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 |
|||
1,000th: 19,403 |
|||
10,000th: 242,057 |
|||
18.405 seconds</pre> |
|||
=== ntheory library === |
|||
{{libheader|ntheory}} |
|||
<syntaxhighlight lang="raku" line>use ntheory:from<Perl5> <ramanujan_primes nth_ramanujan_prime>; |
|||
use Lingua::EN::Numbers; |
|||
say 'First 100:'; |
|||
say ramanujan_primes( nth_ramanujan_prime(100) ).batch(10)».&comma».fmt("%6s").join: "\n"; |
|||
for (2..12).map: {exp $_, 10} -> $limit { |
|||
say "\n{tc ordinal $limit}: { comma nth_ramanujan_prime($limit) }"; |
|||
} |
|||
say (now - INIT now).fmt('%.3f') ~ ' seconds';</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 100: |
|||
2 11 17 29 41 47 59 67 71 97 |
|||
101 107 127 149 151 167 179 181 227 229 |
|||
233 239 241 263 269 281 307 311 347 349 |
|||
367 373 401 409 419 431 433 439 461 487 |
|||
491 503 569 571 587 593 599 601 607 641 |
|||
643 647 653 659 677 719 727 739 751 769 |
|||
809 821 823 827 853 857 881 937 941 947 |
|||
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 |
|||
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 |
|||
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 |
|||
One hundredth: 1,439 |
|||
One thousandth: 19,403 |
|||
Ten thousandth: 242,057 |
|||
One hundred thousandth: 2,916,539 |
|||
One millionth: 34,072,993 |
|||
Ten millionth: 389,433,437 |
|||
One hundred millionth: 4,378,259,731 |
|||
One billionth: 48,597,112,639 |
|||
Ten billionth: 533,902,884,973 |
|||
One hundred billionth: 5,816,713,968,619 |
|||
One trillionth: 62,929,891,461,461 |
|||
15.572 seconds</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{ |
{{trans|C++}} |
||
{{libheader|Wren- |
{{libheader|Wren-iterate}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
<br> |
|||
{{libheader|Wren-sort}} |
|||
This takes about |
This takes about 1.1 seconds to find the 100,000th Ramanujan prime on my machine. The millionth takes 13.2 seconds. |
||
< |
<syntaxhighlight lang="wren">import "./iterate" for Stepped |
||
import "/ |
import "./fmt" for Fmt |
||
import "/fmt" for Fmt |
|||
import "/sort" for Find |
|||
var count |
|||
var primes = Int.primeSieve(700000) // say |
|||
var |
var primeCounter = Fn.new { |limit| |
||
count = List.filled(limit, 1) |
|||
var max = (4 * n * (4 * n).log / 2.log).floor |
|||
if (limit > 0) count[0] = 0 |
|||
var pi = Find.all(primes[2*n..-1], max)[2].from // binary search from min of (2n)th prime |
|||
if (limit > 1) count[1] = 0 |
|||
for (i in Stepped.new(4...limit, 2)) count[i] = 0 |
|||
var delta = pi + 1 - Int.primeCount((primes[pi]/2).floor) |
|||
var p = 3 |
|||
if (delta <= n) return primes[pi] |
|||
var sq = 9 |
|||
while (sq < limit) { |
|||
if (count[p] != 0) { |
|||
var q = sq |
|||
while (q < limit) { |
|||
count[q] = 0 |
|||
q = q + p * 2 |
|||
} |
|||
} |
|||
sq = sq + (p + 1) * 4 |
|||
p = p + 2 |
|||
} |
|||
var sum = 0 |
|||
for (i in 0...limit) { |
|||
sum = sum + count[i] |
|||
count[i] = sum |
|||
} |
} |
||
} |
} |
||
var primeCount = Fn.new { |n| (n < 1) ? 0 : count[n] } |
|||
var ramanujanMax = Fn.new { |n| (4 * n * (4*n).log).ceil } |
|||
var ramanujanPrime = Fn.new { |n| |
|||
if (n == 1) return 2 |
|||
for (i in ramanujanMax.call(n)..2*n) { |
|||
if (i % 2 == 1) continue |
|||
if (primeCount.call(i) - primeCount.call((i/2).floor) < n) return i + 1 |
|||
} |
|||
return 0 |
|||
} |
|||
primeCounter.call(1 + ramanujanMax.call(1e6)) |
|||
System.print("The first 100 Ramanujan primes are:") |
System.print("The first 100 Ramanujan primes are:") |
||
var rams = (1..100).map { |n| |
var rams = (1..100).map { |n| ramanujanPrime.call(n) } |
||
Fmt.tprint("$,5d", rams, 10) |
|||
Fmt.print("\nThe 1,000th Ramanujan prime is $,6d", ramanujanPrime.call(1000)) |
|||
Fmt.print("\nThe 10,000th Ramanujan prime is $,7d", ramanujanPrime.call(10000)) |
|||
Fmt.print("\nThe |
Fmt.print("\nThe 100,000th Ramanujan prime is $,9d", ramanujanPrime.call(100000)) |
||
Fmt.print("\nThe |
Fmt.print("\nThe 1,000,000th Ramanujan prime is $,10d", ramanujanPrime.call(1000000))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The first 100 Ramanujan primes are: |
The first 100 Ramanujan primes are: |
||
2 11 17 29 41 47 59 67 71 97 |
2 11 17 29 41 47 59 67 71 97 |
||
101 107 127 149 151 167 179 181 227 229 |
101 107 127 149 151 167 179 181 227 229 |
||
233 239 241 263 269 281 307 311 347 349 |
233 239 241 263 269 281 307 311 347 349 |
||
367 373 401 409 419 431 433 439 461 487 |
367 373 401 409 419 431 433 439 461 487 |
||
491 503 569 571 587 593 599 601 607 641 |
491 503 569 571 587 593 599 601 607 641 |
||
643 647 653 659 677 719 727 739 751 769 |
643 647 653 659 677 719 727 739 751 769 |
||
809 821 823 827 853 857 881 937 941 947 |
809 821 823 827 853 857 881 937 941 947 |
||
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 |
967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 |
||
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 |
1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 |
||
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 |
1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 |
||
The 1,000th Ramanujan prime is 19,403 |
The 1,000th Ramanujan prime is 19,403 |
||
The 10,000th Ramanujan prime is 242,057 |
The 10,000th Ramanujan prime is 242,057 |
||
The 100,000th Ramanujan prime is 2,916,539 |
|||
The 1,000,000th Ramanujan prime is 34,072,993 |
|||
</pre> |
</pre> |
Latest revision as of 19:48, 21 March 2024
As the integers get larger, the spacing between prime numbers slowly lengthens, but the spacing between primes increases at a slower rate than the numbers themselves increase. A consequence of this difference in rates of increase is the existence of special primes, called Ramanujan primes.
The `n`th Ramanujan prime is defined to be the least integer for which there are at least n primes between x and x/2 for all x greater or equal to n.
- Task
- Generate and show the first 100 Ramanujan prime numbers.
- Find and show the 1000th Ramanujan prime number.
- Stretch task
- Find and show the 10,000th Ramanujan prime number.
- See also
- The pi prime function, not to be confused with the transcendental number π
- The OEIS entry: OEIS entry
- The Wikipedia entry: Ramanujan_prime.
ALGOL 68
BEGIN # find some Ramanujan primes: the nth Ramanujan prime is the least n #
# such that there are at least n primes between x and x/2 for all x>=n #
PR read "primes.incl.a68" PR # include the prime utilities #
[]BOOL p = PRIMESIEVE 1 000 000; # generate a sieve of primes #
# find the highest numbers where the number of primes between x and x/2 #
# is at most n, store the list in hpx #
[ 0 : UPB p ]INT hpx;
BEGIN
# count the primes up to n #
[ 0 : UPB p ]INT pc; # pc[ n ]: count of primes up to n #
FOR i FROM LWB pc TO UPB pc DO pc[ i ] := 0 OD;
INT p count := 0;
FOR i TO UPB pc DO
IF p[ i ] THEN p count +:= 1 FI;
pc[ i ] := p count
OD;
# count the pimes between x and x/2 #
[ 0 : UPB p ]INT pc2; # pc2[ n ]: count of primes between n and n/2 #
FOR i FROM LWB pc2 TO UPB pc2 DO
pc2[ i ] := pc[ i ] - pc[ i OVER 2 ]
OD;
# find the highest x where the prime count between x and x/2 is x #
FOR i FROM LWB hpx TO UPB hpx DO hpx[ i ] := 0 OD;
FOR i FROM LWB hpx TO UPB hpx DO
hpx[ pc2[ i ] ] := i
OD
END;
# show the Ramanjan primes #
INT r count := 0;
INT power of 10 := 1 000;
FOR n FROM LWB hpx TO UPB hpx WHILE r count < 10 000 DO
# hpx[ n ] contains the highest number where the number of primes #
# between x and x/2 is at most n, so we need to find the next #
# prime >= n #
INT rp := hpx[ n ];
WHILE NOT p[ rp ] DO rp +:= 1 OD;
IF ( r count +:= 1 ) <= 100 THEN
print( ( " ", whole( rp, -4 ) ) );
IF r count MOD 20 = 0 THEN print( ( newline ) ) FI
ELIF r count = power of 10 THEN
print( ( "The ", whole( r count, -8 ), "th Ramanujan prime is: ", whole( rp, 0 ), newline ) );
power of 10 *:= 10
FI
OD
END
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th Ramanujan prime is: 19403 The 10000th Ramanujan prime is: 242057
BASIC
FreeBASIC
#define floor(x) ((x*2.0-0.5) Shr 1)
Dim Shared As Integer pi()
Sub primeCounter(limit As Integer)
Dim As Integer i, q, p, sq, total
Redim pi(limit)
pi(0) = 0
pi(1) = 0
For i = 2 To limit
pi(i) = 1
Next
If limit > 2 Then
For i = 4 To limit Step 2
pi(i) = 0
Next i
p = 3
sq = 9
While sq <= limit
If pi(p) <> 0 Then
For q = sq To limit Step p*2
pi(q) = 0
Next q
End If
sq += (p + 1) * 4
p += 2
Wend
total = 0
For i = 2 To limit
total += pi(i)
pi(i) = total
Next i
End If
End Sub
Function ramanujanMax(n As Integer) As Integer
Return floor(4 * n * Log(4*n))
End Function
Function ramanujanPrime(n As Integer) As Integer
Dim As Integer i, maxposs
If n = 1 Then Return 2
maxposs = ramanujanMax(n)
For i = maxposs - (maxposs Mod 2) To 1 Step -2
If pi(i) - pi(i\2) < n Then Return i + 1
Next i
Return 0
End Function
Dim As Integer p, n, limit = 1e6
Dim As Double t0 = Timer
primeCounter(ramanujanMax(limit))
Print "The first 100 Ramanujan primes are:"
For p = 1 To 100
Print Using " ####"; ramanujanPrime(p);
If p Mod 20 = 0 Then Print
Next p
Print
For p = 3 To 6
n = 10 ^ p
Print Using "The &th Ramanujan prime is &"; n; ramanujanPrime(n)
Next p
Print Using "##.##sec."; Timer - t0
Sleep
- Output:
The first 100 Ramanujan primes are: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th Ramanujan prime is 19403 The 10000th Ramanujan prime is 242057 The 100000th Ramanujan prime is 2916539 The 1000000th Ramanujan prime is 34072993 1.53sec.
Yabasic
dim cnt(1e6)
primeCounter(ramanujanMax((1e6)))
print "The first 100 Ramanujan primes are:"
for p = 1 to 100
print ramanujanPrime(p) using ("#####");
if mod(p, 20) = 0 print
next p
print
for p = 3 to 6
n = 10 ^ p
print "The ", n, "th Ramanujan prime is ", ramanujanPrime(n)
next p
print peek("millisrunning") / 1000, "sec."
end
sub primeCounter(limit)
local i, q, p, sq, total
redim cnt(limit)
cnt(0) = 0
cnt(1) = 0
for i = 2 to limit
cnt(i) = 1
next
if limit > 2 then
for i = 4 to limit step 2
cnt(i) = 0
next i
p = 3
sq = 9
while sq <= limit
if cnt(p) <> 0 then
for q = sq to limit step p*2
cnt(q) = 0
next q
fi
sq = sq + (p + 1) * 4
p = p + 2
wend
total = 0
for i = 2 to limit
total = total + cnt(i)
cnt(i) = total
next i
fi
end sub
sub ramanujanMax(n)
return floor(4 * n * log(4*n))
end sub
sub ramanujanPrime(n)
local i, maxposs
if n = 1 return 2
maxposs = ramanujanMax(n)
for i = maxposs - mod(maxposs, 2) to 1 step -2
if cnt(i) - cnt(floor(i/2)) < n return i + 1
next i
return 0
end sub
- Output:
The first 100 Ramanujan primes are: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th Ramanujan prime is 19403 The 10000th Ramanujan prime is 242057 The 100000th Ramanujan prime is 2916539 The 1000000th Ramanujan prime is 34072993 35.14sec.
C++
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
class prime_counter {
public:
explicit prime_counter(int limit);
int prime_count(int n) const { return n < 1 ? 0 : count_.at(n); }
private:
std::vector<int> count_;
};
prime_counter::prime_counter(int limit) : count_(limit, 1) {
if (limit > 0)
count_[0] = 0;
if (limit > 1)
count_[1] = 0;
for (int i = 4; i < limit; i += 2)
count_[i] = 0;
for (int p = 3, sq = 9; sq < limit; p += 2) {
if (count_[p]) {
for (int q = sq; q < limit; q += p << 1)
count_[q] = 0;
}
sq += (p + 1) << 2;
}
std::partial_sum(count_.begin(), count_.end(), count_.begin());
}
int ramanujan_max(int n) {
return static_cast<int>(std::ceil(4 * n * std::log(4 * n)));
}
int ramanujan_prime(const prime_counter& pc, int n) {
int max = ramanujan_max(n);
for (int i = max; i >= 0; --i) {
if (pc.prime_count(i) - pc.prime_count(i / 2) < n)
return i + 1;
}
return 0;
}
int main() {
std::cout.imbue(std::locale(""));
auto start = std::chrono::high_resolution_clock::now();
prime_counter pc(1 + ramanujan_max(100000));
for (int i = 1; i <= 100; ++i) {
std::cout << std::setw(5) << ramanujan_prime(pc, i)
<< (i % 10 == 0 ? '\n' : ' ');
}
std::cout << '\n';
for (int n = 1000; n <= 100000; n *= 10) {
std::cout << "The " << n << "th Ramanujan prime is " << ramanujan_prime(pc, n)
<< ".\n";
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << "\nElapsed time: "
<< std::chrono::duration<double>(end - start).count() * 1000
<< " milliseconds\n";
}
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 The 1,000th Ramanujan prime is 19,403. The 10,000th Ramanujan prime is 242,057. The 100,000th Ramanujan prime is 2,916,539. Elapsed time: 46.0828 milliseconds
Delphi
Uses the Delphi Prime-Generator Object
procedure ShowRamanujanPrimes(Memo: TMemo);
var S: string;
var PrimeCounts: array of Integer;
var Sieve: TPrimeSieve;
var I,Cnt,P: integer;
const Size = 1000000;
function GetRamanujanMax(N: integer): integer;
{Get maximum possible Ramanujan for a particular N}
begin
Result:=Ceil(4 * N * (log(4 * N) / log(2)));
end;
function RamanujanPrime(N: integer): integer;
{Find largest I for Pi[I]-Pi[I/2]<N, Pi[I] is count primes less than I}
var I: integer;
begin
for I:=GetRamanujanMax(N) downto 0 do
if (PrimeCounts[I] - PrimeCounts[I div 2]) < N then
begin
Result:=I+1;
exit;
end;
Result:=0;
end;
begin
Sieve:=TPrimeSieve.Create;
try
{Get primes up to 1 million}
Sieve.Intialize(Size);
{Count total number of primes up to a specific number}
SetLength(PrimeCounts,Size);
Cnt:=0;
for I:=0 to Sieve.Count-1 do
begin
if Sieve.Flags[I] then Inc(Cnt);
PrimeCounts[I]:=Cnt;
end;
{display first 100 Ramanujan Prime}
S:='';
for I:=1 to 100 do
begin
P:=RamanujanPrime(I);
S:=S+Format('%5d',[P]);
if (I mod 10)=0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
P:=RamanujanPrime(1000);
Memo.Lines.Add('1,000th Prime: '+IntToStr(P));
P:=RamanujanPrime(10000);
Memo.Lines.Add('10,000th Prime: '+IntToStr(P));
finally Sieve.Free; end;
end;
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 1,000th Prime: 19403 10,000th Prime: 242057 Elapsed Time: 19.269 ms.
EasyLang
global cnt[] .
proc primcnt limit . .
cnt[] = [ 0 1 1 ]
for i = 4 step 2 to limit
cnt[] &= 0
cnt[] &= 1
.
p = 3
sq = 9
while sq <= limit
if cnt[p] <> 0
for q = sq step p * 2 to limit
cnt[q] = 0
.
.
sq += (p + 1) * 4
p += 2
.
for i = 2 to limit
sum += cnt[i]
cnt[i] = sum
.
.
func log n .
e = 2.7182818284590452354
return log10 n / log10 e
.
func ramamax n .
return floor (4 * n * log (4 * n))
.
func ramaprim n .
if n = 1
return 2
.
for i = ramamax n downto 2 * n
if i mod 2 = 0
if cnt[i] - cnt[i / 2] < n
return i + 1
.
.
.
return 0
.
primcnt (1 + ramamax 1000)
print "The first 100 Ramanujan primes are:"
for i = 1 to 100
write ramaprim i & " "
.
print ""
print ""
print "The 1000th Ramanujan prime is " & ramaprim 1000
F#
This task uses Extensible Prime Generator (F#)
// Ramanujan primes. Nigel Galloway: September 7th., 2021
let fN g=if isPrime g then 1 else if g%2=1 then 0 else if isPrime(g/2) then -1 else 0
let rP p=let N,G=Array.create p 0,(Seq.item(3*p-2)(primes32()))+1 in let rec fG n g=if g=G then N else(if n<p then N.[n]<-g); fG(n+(fN g))(g+1) in fG 0 1
let n=rP 100000
n.[0..99]|>Array.iter(printf "%d "); printfn ""
[1000;10000;100000]|>List.iter(fun g->printf $"The %d{g}th Ramanujan prime is %d{n.[g-1]}\n" )
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th Ramanujan prime is 19403 The 10000th Ramanujan prime is 242057 The 100000th Ramanujan prime is 2916539
Go
This takes about 40 ms to find the 100,000th Ramanujan prime on my machine. The millionth takes about 520 ms.
package main
import (
"fmt"
"math"
"rcu"
"time"
)
var count []int
func primeCounter(limit int) {
count = make([]int, limit)
for i := 0; i < limit; i++ {
count[i] = 1
}
if limit > 0 {
count[0] = 0
}
if limit > 1 {
count[1] = 0
}
for i := 4; i < limit; i += 2 {
count[i] = 0
}
for p, sq := 3, 9; sq < limit; p += 2 {
if count[p] != 0 {
for q := sq; q < limit; q += p << 1 {
count[q] = 0
}
}
sq += (p + 1) << 2
}
sum := 0
for i := 0; i < limit; i++ {
sum += count[i]
count[i] = sum
}
}
func primeCount(n int) int {
if n < 1 {
return 0
}
return count[n]
}
func ramanujanMax(n int) int {
fn := float64(n)
return int(math.Ceil(4 * fn * math.Log(4*fn)))
}
func ramanujanPrime(n int) int {
if n == 1 {
return 2
}
for i := ramanujanMax(n); i >= 2*n; i-- {
if i%2 == 1 {
continue
}
if primeCount(i)-primeCount(i/2) < n {
return i + 1
}
}
return 0
}
func main() {
start := time.Now()
primeCounter(1 + ramanujanMax(1e6))
fmt.Println("The first 100 Ramanujan primes are:")
rams := make([]int, 100)
for n := 0; n < 100; n++ {
rams[n] = ramanujanPrime(n + 1)
}
for i, r := range rams {
fmt.Printf("%5s ", rcu.Commatize(r))
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Printf("\nThe 1,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujanPrime(1000)))
fmt.Printf("\nThe 10,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujanPrime(10000)))
fmt.Printf("\nThe 100,000th Ramanujan prime is %6s\n", rcu.Commatize(ramanujanPrime(100000)))
fmt.Printf("\nThe 1,000,000th Ramanujan prime is %7s\n", rcu.Commatize(ramanujanPrime(1000000)))
fmt.Println("\nTook", time.Since(start))
}
- Output:
The first 100 Ramanujan primes are: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 The 1,000th Ramanujan prime is 19,403 The 10,000th Ramanujan prime is 242,057 The 100,000th Ramanujan prime is 2,916,539 The 1,000,000th Ramanujan prime is 34,072,993 Took 519.655163ms
Java
import java.util.Arrays;
public class RamanujanPrimes {
public static void main(String[] args) {
long start = System.nanoTime();
System.out.println("First 100 Ramanujan primes:");
PrimeCounter pc = new PrimeCounter(1 + ramanujanMax(100000));
for (int i = 1; i <= 100; ++i) {
int p = ramanujanPrime(pc, i);
System.out.printf("%,5d%c", p, i % 10 == 0 ? '\n' : ' ');
}
System.out.println();
for (int i = 1000; i <= 100000; i *= 10) {
int p = ramanujanPrime(pc, i);
System.out.printf("The %,dth Ramanujan prime is %,d.\n", i, p);
}
long end = System.nanoTime();
System.out.printf("\nElapsed time: %.1f milliseconds\n", (end - start) / 1e6);
}
private static int ramanujanMax(int n) {
return (int)Math.ceil(4 * n * Math.log(4 * n));
}
private static int ramanujanPrime(PrimeCounter pc, int n) {
for (int i = ramanujanMax(n); i >= 0; --i) {
if (pc.primeCount(i) - pc.primeCount(i / 2) < n)
return i + 1;
}
return 0;
}
private static class PrimeCounter {
private PrimeCounter(int limit) {
count = new int[limit];
Arrays.fill(count, 1);
if (limit > 0)
count[0] = 0;
if (limit > 1)
count[1] = 0;
for (int i = 4; i < limit; i += 2)
count[i] = 0;
for (int p = 3, sq = 9; sq < limit; p += 2) {
if (count[p] != 0) {
for (int q = sq; q < limit; q += p << 1)
count[q] = 0;
}
sq += (p + 1) << 2;
}
Arrays.parallelPrefix(count, (x, y) -> x + y);
}
private int primeCount(int n) {
return n < 1 ? 0 : count[n];
}
private int[] count;
}
}
- Output:
First 100 Ramanujan primes: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 The 1,000th Ramanujan prime is 19,403. The 10,000th Ramanujan prime is 242,057. The 100,000th Ramanujan prime is 2,916,539. Elapsed time: 187.2 milliseconds
J
result=. (((] - _1&(33 b.)@:>:@[ { ]) _1&p:) i. 3e6) i: i. 1e5
_10 ]\ 100 {. result
2 11 17 29 41 47 59 67 71 97
101 107 127 149 151 167 179 181 227 229
233 239 241 263 269 281 307 311 347 349
367 373 401 409 419 431 433 439 461 487
491 503 569 571 587 593 599 601 607 641
643 647 653 659 677 719 727 739 751 769
809 821 823 827 853 857 881 937 941 947
967 983 1009 1019 1021 1031 1049 1051 1061 1063
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439
(10 <:@^ 3 4 5) { result
19403 242057 2916539
jq
Adapted from Wren
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
# tabular print
def tprint(columns; wide):
reduce _nwise(columns) as $row ("";
. + ($row|map(lpad(wide)) | join(" ")) + "\n" );
# output: {count}
def primeCounter($limit):
{count: [range(0; $limit) | 1] }
| if ($limit > 0) then .count[0] = 0 else . end
| if ($limit > 1) then .count[1] = 0 else . end
| .count |= reduce range(4; $limit; 2) as $i (.; .[$i] = 0)
| .p = 3
| .sq = 9
| until(.sq >= $limit;
if (.count[.p] != 0)
then .q = .sq
| until (.q >= $limit;
.count[.q] = 0
| .q += (.p * 2) )
else .
end
| .sq += ((.p + 1) * 4)
| .p += 2 )
| .sum = 0
| reduce range(0; $limit) as $i (.;
.sum += .count[$i]
| .count[$i] = .sum ) ;
# input: {count}
def primeCount($n): if $n < 1 then 0 else .count[$n] end;
# 2n ln 2n < Rn < 4n ln 4n
def ramanujanMax(n): (4 * n * ((4*n)|log))|ceil;
# input: {count}
def ramanujanPrime($n):
if ($n == 1) then 2
else first( foreach range(ramanujanMax($n); 1+2*$n; -1) as $i (.emit=null;
if ($i % 2 == 1) then .
elif (primeCount($i) - primeCount(($i/2)|floor) < $n) then .emit=$i + 1
else .
end)
| select(.emit).emit ) // 0
end ;
# The tasks
primeCounter(1 + ramanujanMax(1e6))
| "The first 100 Ramanujan primes are:",
( [range(1;101) as $i | ramanujanPrime($i) ]
| tprint(10; 5) ),
"\nThe 1,000th Ramanujan prime is \(ramanujanPrime(1000))",
"\nThe 10,000th Ramanujan prime is \(ramanujanPrime(10000))",
"\nThe 100,000th Ramanujan prime is \(ramanujanPrime(100000))",
"\nThe 1,000,000th Ramanujan prime is \(ramanujanPrime(1000000))"
- Output:
The first 100 Ramanujan primes are: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1,000th Ramanujan prime is 19403 The 10,000th Ramanujan prime is 242057 The 100,000th Ramanujan prime is 2916539 The 1,000,000th Ramanujan prime is 34072993
Julia
using Primes
@time let
MASK = primesmask(625000)
PIVEC = accumulate(+, MASK)
PI(n) = n < 1 ? 0 : PIVEC[n]
function Ramanujan_prime(n)
maxposs = Int(ceil(4n * (log(4n) / log(2))))
for i in maxposs:-1:1
PI(i) - PI(i ÷ 2) < n && return i + 1
end
return 0
end
for i in 1:100
print(lpad(Ramanujan_prime(i), 5), i % 20 == 0 ? "\n" : "")
end
println("\nThe 1000th Ramanujan prime is ", Ramanujan_prime(1000))
println("\nThe 10,000th Ramanujan prime is ", Ramanujan_prime(10000))
end
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th Ramanujan prime is 19403 The 10,000th Ramanujan prime is 242057 0.272471 seconds (625.44 k allocations: 38.734 MiB, 33.07% compilation time)
Mathematica/Wolfram Language
l = PrimePi[Range[10^6]] - PrimePi[Range[10^6]/2];
Multicolumn[1 + Position[l, #][[-1, 1]] & /@ Range[0, 99], {Automatic, 10}, Appearance -> "Horizontal"]
1 + Position[l, 999][[-1, 1]]
1 + Position[l, 9999][[-1, 1]]
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 19403 242057
Nim
I compiled using command nim c -d:release -d:lto --gc:arc ramanujan_primes.nim
, i.e. with runtime checks on, link time optimization and using Arc garbage collector. To find the 100_000th Ramanujan prime, the program runs in about 100 ms on my laptop (i5-8250U CPU @ 1.60GHz, 8 GB Ram, Linux Manjaro).
import math, sequtils, strutils, times
let t0 = now()
type PrimeCounter = seq[int]
proc initPrimeCounter(limit: Positive): PrimeCounter =
doAssert limit > 1
result = repeat(1, limit)
result[0] = 0
result[1] = 0
for i in countup(4, limit - 1, 2): result[i] = 0
var p = 3
var p2 = 9
while p2 < limit:
if result[p] != 0:
for q in countup(p2, limit - 1, p shl 1):
result[q] = 0
p2 += (p + 1) shl 2
if p2 >= limit: break
inc p, 2
# Compute partial sums in place.
var sum = 0
for item in result.mitems:
sum += item
item = sum
func ramanujanMax(n: int): int {.inline.} = int(ceil(4 * n.toFloat * ln(4 * n.toFloat)))
proc ramanujanPrime(pi: PrimeCounter; n: int): int =
if n == 1: return 2
var max = ramanujanMax(n)
if (max and 1) == 1: dec max
for i in countdown(max, 2, 2):
if pi[i] - pi[i div 2] < n:
return i + 1
let pi = initPrimeCounter(1 + ramanujanMax(100_000))
for n in 1..100:
stdout.write ($ramanujanPrime(pi, n)).align(4), if n mod 20 == 0: '\n' else: ' '
echo "\nThe 1000th Ramanujan prime is ", ramanujanPrime(pi, 1_000)
echo "The 10_000th Ramanujan prime is ", ramanujanPrime(pi, 10_000)
echo "The 100_000th Ramanujan prime is ", ramanujanPrime(pi, 100_000)
echo "\nElapsed time: ", (now() - t0).inMilliseconds, " ms"
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th Ramanujan prime is 19403 The 10_000th Ramanujan prime is 242057 The 100_000th Ramanujan prime is 2916539 Elapsed time: 99 ms
Perl
use strict;
use warnings;
use ntheory 'primes';
sub count {
my($n,$p) = @_;
my $c = -1;
do { $c++ } until $$p[$c] > $n;
return $c;
}
my(@rp,@mem);
my $primes = primes( 100_000_000 );
sub r_prime {
my $n = shift;
for my $x ( reverse 1 .. int 4*$n * log(4*$n) / log 2 ) {
my $y = int $x / 2;
return 1 + $x if ($mem[$x] //= count($x,$primes)) - ($mem[$y] //= count($y,$primes)) < $n
}
}
push @rp, r_prime($_) for 1..100;
print "First 100:\n" . (sprintf "@{['%5d' x 100]}", @rp) =~ s/(.{100})/$1\n/gr;
print "\n\n 1000th: " . r_prime( 1000) . "\n";
print "\n10000th: " . r_prime(10000) . "\n"; # faster with 'ntheory' function 'ramanujan_primes'
- Output:
First 100: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 1000th: 19403 10000th: 242057
Phix
You can run this online here.
with javascript_semantics sequence pi = {} procedure primeCounter(integer limit) pi = repeat(1,limit) if limit > 1 then pi[1] = 0 for i=4 to limit by 2 do pi[i] = 0 end for integer p = 3, sq = 9 while sq<=limit do if pi[p]!=0 then for q=sq to limit by p*2 do pi[q] = 0 end for end if sq += (p + 1)*4 p += 2 end while atom total = 0 for i=2 to limit do total += pi[i] pi[i] = total end for end if end procedure function ramanujanMax(integer n) return floor(4*n*log(4*n)) end function function ramanujanPrime(integer n) if n=1 then return 2 end if integer maxposs = ramanujanMax(n) for i=maxposs-odd(maxposs) to 1 by -2 do if pi[i]-pi[floor(i/2)] < n then return i + 1 end if end for return 0 end function atom t0 = time() integer lim = iff(platform()=JS?5:6) primeCounter(ramanujanMax(power(10,lim))) sequence r = apply(tagset(100),ramanujanPrime) printf(1,"%s\n",join_by(apply(true,sprintf,{{"%5d"},r}),1,20,"")) for p=3 to lim do integer n = power(10,p) printf(1,"The %,dth Ramanujan prime is %,d\n", {n,ramanujanPrime(n)}) end for
- Output:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1,000th Ramanujan prime is 19,403 The 10,000th Ramanujan prime is 242,057 The 100,000th Ramanujan prime is 2,916,539 The 1,000,000th Ramanujan prime is 34,072,993 "2.7s"
The last line is omitted under pwa/p2js since the primeCounter array is too much for Javascript to handle.
Python
import time
import math
class PrimeCounter:
"""Generate a list 'count' where count[n] is the number of primes less than or equal to n"""
def __init__(self, limit):
self.count = [1] * limit
count = self.count
if limit > 0:
count[0] = 0
if limit > 1:
count[1] = 0
for i in range(4, limit, 2):
count[i] = 0
p = 3
while p**2 < limit:
if count[p] != 0:
q = p**2
while q < limit:
count[q] = 0
q += p * 2
p += 2
for i, j in enumerate(count):
if i == 0:
continue
count[i] += count[i - 1]
def prime_count(self, n):
"""Get the number of primes less than or equal to n"""
if n > 0:
return self.count[n]
return 0
def ramanujan_prime_upper_bound(n):
"""Calculate the largest number the nth Ramanujan number could possibly be"""
return math.ceil(4 * n * math.log(4 * n))
def ramanujan_prime(prime_counter_in, n):
"""Generate the nth Ramanujan prime by finding the largest number 'i' where less than n primes are in the
range i//2 and i - the Ramanujan prime is one more than i"""
pci = prime_counter_in
for i in range(ramanujan_prime_upper_bound(n), -1, -1):
pi_n = pci.prime_count(i)
pi_half_n = pci.prime_count(i // 2)
if pi_n - pi_half_n < n:
return i + 1
return 0
def print_ramanujan_primes_in_range(start_number, end_number, prime_counter_in):
"""Print all Ramanujan primes between start_number (inclusive) and end_number (exclusive)"""
for i in range(start_number, end_number):
p = ramanujan_prime(prime_counter_in, i)
print(f"{p : <4}", end=" ")
if i % 10 == 0:
print()
def solve():
"""Return the first 100 Ramanujan primes and the 1000th, 10000th & 100000th Ramanujan primes"""
print("First 100 Ramanujan primes:\n")
largest_number_to_calculate = ramanujan_prime_upper_bound(100000) + 1
prime_counter = PrimeCounter(largest_number_to_calculate)
print_ramanujan_primes_in_range(1, 101, prime_counter)
print()
for number in (1_000, 10_000, 100_000):
answer = ramanujan_prime(prime_counter, number)
print(
f"The {number : >6}th ramanujan prime is {answer : >7}"
)
start = time.perf_counter()
solve()
end = time.perf_counter()
time_taken_ms = int((end - start) * 1000)
print(f"\nElapsed time: {time_taken_ms}ms")
- Output:
First 100 Ramanujan primes: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063 1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439 The 1000th ramanujan prime is 19403 The 10000th ramanujan prime is 242057 The 100000th ramanujan prime is 2916539 Elapsed time: 1460ms
Raku
All timings are purely informational. Will vary by system specs and load.
Pure Raku
use Math::Primesieve;
use Lingua::EN::Numbers;
my $primes = Math::Primesieve.new;
my @mem;
sub ramanujan-prime (\n) {
1 + (1..(4×n × (4×n).log / 2.log).floor).first: :end, -> \x {
my \y = x div 2;
((@mem[x] //= $primes.count(x)) - (@mem[y] //= $primes.count(y))) < n
}
}
say 'First 100:';
say (1..100).map( &ramanujan-prime ).batch(10)».&comma».fmt("%6s").join: "\n";
say "\n 1,000th: { comma 1000.&ramanujan-prime }";
say "10,000th: { comma 10000.&ramanujan-prime }";
say (now - INIT now).fmt('%.3f') ~ ' seconds';
- Output:
First 100: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 1,000th: 19,403 10,000th: 242,057 18.405 seconds
ntheory library
use ntheory:from<Perl5> <ramanujan_primes nth_ramanujan_prime>;
use Lingua::EN::Numbers;
say 'First 100:';
say ramanujan_primes( nth_ramanujan_prime(100) ).batch(10)».&comma».fmt("%6s").join: "\n";
for (2..12).map: {exp $_, 10} -> $limit {
say "\n{tc ordinal $limit}: { comma nth_ramanujan_prime($limit) }";
}
say (now - INIT now).fmt('%.3f') ~ ' seconds';
- Output:
First 100: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 One hundredth: 1,439 One thousandth: 19,403 Ten thousandth: 242,057 One hundred thousandth: 2,916,539 One millionth: 34,072,993 Ten millionth: 389,433,437 One hundred millionth: 4,378,259,731 One billionth: 48,597,112,639 Ten billionth: 533,902,884,973 One hundred billionth: 5,816,713,968,619 One trillionth: 62,929,891,461,461 15.572 seconds
Wren
This takes about 1.1 seconds to find the 100,000th Ramanujan prime on my machine. The millionth takes 13.2 seconds.
import "./iterate" for Stepped
import "./fmt" for Fmt
var count
var primeCounter = Fn.new { |limit|
count = List.filled(limit, 1)
if (limit > 0) count[0] = 0
if (limit > 1) count[1] = 0
for (i in Stepped.new(4...limit, 2)) count[i] = 0
var p = 3
var sq = 9
while (sq < limit) {
if (count[p] != 0) {
var q = sq
while (q < limit) {
count[q] = 0
q = q + p * 2
}
}
sq = sq + (p + 1) * 4
p = p + 2
}
var sum = 0
for (i in 0...limit) {
sum = sum + count[i]
count[i] = sum
}
}
var primeCount = Fn.new { |n| (n < 1) ? 0 : count[n] }
var ramanujanMax = Fn.new { |n| (4 * n * (4*n).log).ceil }
var ramanujanPrime = Fn.new { |n|
if (n == 1) return 2
for (i in ramanujanMax.call(n)..2*n) {
if (i % 2 == 1) continue
if (primeCount.call(i) - primeCount.call((i/2).floor) < n) return i + 1
}
return 0
}
primeCounter.call(1 + ramanujanMax.call(1e6))
System.print("The first 100 Ramanujan primes are:")
var rams = (1..100).map { |n| ramanujanPrime.call(n) }
Fmt.tprint("$,5d", rams, 10)
Fmt.print("\nThe 1,000th Ramanujan prime is $,6d", ramanujanPrime.call(1000))
Fmt.print("\nThe 10,000th Ramanujan prime is $,7d", ramanujanPrime.call(10000))
Fmt.print("\nThe 100,000th Ramanujan prime is $,9d", ramanujanPrime.call(100000))
Fmt.print("\nThe 1,000,000th Ramanujan prime is $,10d", ramanujanPrime.call(1000000))
- Output:
The first 100 Ramanujan primes are: 2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229 233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487 491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769 809 821 823 827 853 857 881 937 941 947 967 983 1,009 1,019 1,021 1,031 1,049 1,051 1,061 1,063 1,087 1,091 1,097 1,103 1,151 1,163 1,187 1,217 1,229 1,249 1,277 1,289 1,297 1,301 1,367 1,373 1,423 1,427 1,429 1,439 The 1,000th Ramanujan prime is 19,403 The 10,000th Ramanujan prime is 242,057 The 100,000th Ramanujan prime is 2,916,539 The 1,000,000th Ramanujan prime is 34,072,993