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.

Julia

<lang julia>using Primes, Memoize

const MASK = false

@memoize function PI(n)

   if n > length(first(MASK))
       empty!(MASK)
       push!(MASK, primesmask(2n))
   end
   return sum(@view first(MASK)[1:n])

end

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

</lang>

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

Phix

Translation of: Julia

Library: Phix/online

You can run this online here.

with javascript_semantics
atom t0 = time()
sequence picache = {}
function pi(integer n)
    if n=0 then return 0 end if
    if n>length(picache) then
        sequence primes = get_primes_le(n)
        for i=length(picache)+1 to n do
            integer k = binary_search(i,primes)
            if k<0 then k=-k-1 end if
            picache &= k
        end for
    end if
    return picache[n]
end function
 
function Ramanujan_prime(integer n)
    integer maxposs = floor(ceil(4*n*(log(4*n)/log(2))))
    for i=maxposs to 1 by -1 do
        if pi(i) - pi(floor(i/2)) < n then
            return i + 1
        end if
    end for
    return 0
end function
 
sequence r = apply(tagset(100),Ramanujan_prime)
printf(1,"%s\n",join_by(apply(true,sprintf,{{"%5d"},r}),1,20,""))
printf(1,"The 1000th Ramanujan prime is %d\n", Ramanujan_prime(1000))
printf(1,"The 10,000th Ramanujan prime is %d\n", Ramanujan_prime(10000))
?elapsed(time()-t0)

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.6s"

Wren

Library: Wren-math

Library: Wren-trait

Library: Wren-seq

Library: Wren-fmt

Stretch goal takes a while - just over 2 minutes on my machine compared to Julia's 36 seconds - but that's not too bad for the Wren interpreter. <lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt import "/sort" for Find

var primes = Int.primeSieve(700000) // say

var ramanujan = Fn.new { |n|

   var max = (4 * n * (4 * n).log / 2.log).floor
   var pi = Find.all(primes, max)[2].from // binary search
   while (true) {
       var delta = pi + 1 - Int.primeCount((primes[pi]/2).floor)
       if (delta <= n) return primes[pi]
       pi = pi - 1
   }

}

System.print("The first 100 Ramanujan primes are:") var rams = (1..100).map { |n| ramanujan.call(n) }.toList for (chunk in Lst.chunks(rams, 10)) Fmt.print("$,5d", chunk)

Fmt.print("\nThe 1,000th Ramanujan prime is $,6d", ramanujan.call(1000))

Fmt.print("\nThe 10,000th Ramanujan primes is $,7d", ramanujan.call(10000))</lang>

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