Ramanujan primes

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

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

Translation of: Phix

#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

Translation of: FreeBASIC

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

Translation of: Julia

#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

Works with: Delphi version 6.0

Library: SysUtils,StdCtrls

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

Translation of: Go

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

Forth

Works with: Gforth

variable prime-count

: prime-count-free ( -- )
  prime-count @ free abort" free failed"
  0 prime-count ! ;

: prime-count-allocate ( n -- )
  prime-count-free
  cells dup allocate abort" out of memory"
  tuck prime-count ! erase ;

: get-prime-count ( n -- n )
  cells prime-count @ + @ ;

: set-prime-count ( n1 n2 -- )
  cells prime-count @ + ! ;

: prime-count-init { n -- }
  n prime-count-allocate
  prime-count @ n cells +
  prime-count @ 2 cells +
  2dup > if 1 over ! then
  cell+
  begin
    2dup >
  while
    1 over !
    2 cells +
  repeat
  2drop
  3 begin
    dup dup * n <
  while
    dup get-prime-count 0<> if
      n over dup * do
        0 i set-prime-count
      dup 2* +loop
    then
    2 +
  repeat
  drop
  prime-count @ 0
  n 0 +do
    over @ + 2dup swap !
    swap cell+ swap
  loop
  2drop ;

: ceil ( r -- r )
  fnegate floor fnegate ;

: ramanujan-max ( n -- n )
  4 * s>f fdup fln f* ceil f>s ;

: ramanujan-prime { n -- n }
  n ramanujan-max
  begin
    dup 0 >=
  while
    dup get-prime-count
    over 2/ get-prime-count
    - n < if 1+ exit then
    1-
  repeat
  drop 0 ;

: main ( -- )
  1000000 ramanujan-max 1+ prime-count-init
  ." First 100 Ramanujan primes: " cr
  101 1 do
    i ramanujan-prime 4 .r
    i 10 mod 0= if cr else space then
  loop
  cr
  1000000 1000
  begin
    2dup >=
  while
    ." The " dup 1 .r ." th Ramanujan prime is "
    dup ramanujan-prime 1 .r ." ." cr
    10 *
  repeat
  2drop prime-count-free ;

main
bye

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.
The 1000000th Ramanujan prime is 34072993.

Go

Translation of: C++

Library: Go-rcu

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

Translation of: C++

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

Works with: 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))"

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

Translation of: C++

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

Translation of: Raku

Library: ntheory

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

Translation of: Go

Library: Phix/online

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

Translation of: Java

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

Library: ntheory

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

Translation of: C++

Library: Wren-iterate

Library: Wren-fmt

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