Ramanujan primes

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

Wren

Library: Wren-math

Library: Wren-trait

Library: Wren-seq

Library: Wren-fmt

Stretch goal takes a while - just over 6 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 "/trait" for Indexed import "/seq" for Lst import "/fmt" for Fmt

var primes = Int.primeSieve(1e6) // say

var ramanujan = Fn.new { |n|

   var i = (4 * n * (4 * n).log / 2.log).floor
   var pi = 0
   for (se in Indexed.new(primes)) {
       if (se.value > i) {
           pi = se.index - 1
           break
       }
   }
   while (true) {
       var delta = Int.primeCount(primes[pi]) - 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 primes is 242,057