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