Ramanujan primes/twins: Difference between revisions
Added FreeBASIC
(Added Sidef) |
(Added FreeBASIC) |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 2:
In a manner similar to twin primes, twin Ramanujan primes may be explored. The task is to determine how many of the first million Ramanujan primes are twins.
;Related Task: [[Twin primes]]
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>
int32_t ramanujan_maximum(const int32_t& number) {
return ceil(4 * number * log(4 * number));
}
std::vector<int32_t> initialise_prime_pi(const int32_t& limit) {
std::vector<int32_t> result(limit, 1);
result[0] = 0;
result[1] = 0;
for ( int32_t i = 4; i < limit; i += 2 ) {
result[i] = 0;
}
for ( int32_t p = 3, square = 9; square < limit; p += 2 ) {
if ( result[p] != 0 ) {
for ( int32_t q = square; q < limit; q += p << 1 ) {
result[q] = 0;
}
}
square += ( p + 1 ) << 2;
}
for ( uint64_t i = 1; i < result.size(); ++i ) {
result[i] += result[i - 1];
}
return result;
}
int32_t ramanujan_prime(const std::vector<int32_t>& prime_pi, const int32_t& number) {
int32_t maximum = ramanujan_maximum(number);
if ( ( maximum & 1) == 1 ) {
maximum -= 1;
}
int32_t index = maximum;
while ( prime_pi[index] - prime_pi[index / 2] >= number ) {
index -= 1;
}
return index + 1;
}
std::vector<int32_t> list_primes_less_than(const int32_t& limit) {
std::vector<bool> composite(limit, false);
int32_t n = 3;
int32_t nSquared = 9;
while ( nSquared <= limit ) {
if ( ! composite[n] ) {
for ( int32_t k = nSquared; k < limit; k += 2 * n ) {
composite[k] = true;
}
}
nSquared += ( n + 1 ) << 2;
n += 2;
}
std::vector<int32_t> result;
result.emplace_back(2);
for ( int32_t i = 3; i < limit; i += 2 ) {
if ( ! composite[i] ) {
result.emplace_back(i);
}
}
return result;
}
int main() {
const int32_t limit = 1'000'000;
const std::vector<int32_t> prime_pi = initialise_prime_pi(ramanujan_maximum(limit) + 1);
const int32_t millionth_ramanujan_prime = ramanujan_prime(prime_pi, limit);
std::cout << "The 1_000_000th Ramanujan prime is " << millionth_ramanujan_prime << std::endl;
std::vector<int32_t> primes = list_primes_less_than(millionth_ramanujan_prime);
std::vector<int32_t> ramanujan_prime_indexes(primes.size());
for ( uint64_t i = 0; i < ramanujan_prime_indexes.size(); ++i ) {
ramanujan_prime_indexes[i] = prime_pi[primes[i]] - prime_pi[primes[i] / 2];
}
int32_t lowerLimit = ramanujan_prime_indexes[ramanujan_prime_indexes.size() - 1];
for ( int32_t i = ramanujan_prime_indexes.size() - 2; i >= 0; --i ) {
if ( ramanujan_prime_indexes[i] < lowerLimit ) {
lowerLimit = ramanujan_prime_indexes[i];
} else {
ramanujan_prime_indexes[i] = 0;
}
}
std::vector<int32_t> ramanujan_primes;
for ( uint64_t i = 0; i < ramanujan_prime_indexes.size(); ++i ) {
if ( ramanujan_prime_indexes[i] != 0 ) {
ramanujan_primes.emplace_back(primes[i]);
}
}
int32_t twins_count = 0;
for ( uint64_t i = 0; i < ramanujan_primes.size() - 1; ++i ) {
if ( ramanujan_primes[i] + 2 == ramanujan_primes[i + 1] ) {
twins_count++;
}
}
std::cout << "There are " << twins_count << " twins in the first " << limit << " Ramanujan primes." << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
The 1_000_000th Ramanujan prime is 34072993
There are 74973 twins in the first 1000000 Ramanujan primes.
</pre>
=={{header|EasyLang}}==
<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_twins n .
i = ramamax n
i -= i mod 2
while i >= 2
if cnt[i] - cnt[i / 2] < n
p1 = p
p = i + 1
if p1 - p = 2
cnt += 1
.
n -= 1
.
i -= 2
.
return cnt
.
primcnt ramamax 1000000
print ramaprim_twins 1000000
</syntaxhighlight>
{{out}}
<pre>
74973
</pre>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Ramanujan_primes#F.23 Ramanujan primes (F#)]
Line 12 ⟶ 185:
There are 74973 twins in the first million Ramanujan primes
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vbnet">#define floor(x) ((x*2.0-0.5) Shr 1)
Dim Shared pi() As Integer
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 ramanujanPrimeTwins(n As Integer) As Integer
Dim As Integer maxposs, p1, p, cnt
maxposs = ramanujanMax(n)
maxposs -= maxposs Mod 2
While maxposs >= 2
If pi(maxposs) - pi(maxposs \ 2) < n Then
p1 = p
p = maxposs + 1
If p1 - p = 2 Then cnt += 1
n -= 1
End If
maxposs -= 2
Wend
Return cnt
End Function
Dim As Integer limit = 1e6
Dim As Double t0 = Timer
primeCounter ramanujanMax(limit)
Print Using "There are & twins in the first & Ramanujan primes"; ramanujanPrimeTwins(limit); limit
Print Using "##.##sec."; Timer - t0
Sleep</syntaxhighlight>
{{out}}
<pre>There are 74973 twins in the first 1000000 Ramanujan primes
1.53sec.</pre>
=={{header|Go}}==
Line 132 ⟶ 372:
There are 74,973 twins in the first 1,000,000 Ramanujan primes.
Took 699.967994ms
</pre>
=={{header|J}}==
<syntaxhighlight lang="j"> _2 +/@:= 2 -/\ (((] - _1&(33 b.)@:>:@[ { ]) _1&p:) i. 35e6) i: i. 1e6
74973</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public final class RamanujanPrimesTwins {
public static void main(String[] aArgs) {
final int limit = 1_000_000;
final int[] primePi = initialisePrimePi(ramanujanMaximum(limit) + 1);
final int millionthRamanujanPrime = ramanujanPrime(primePi, limit);
System.out.println("The 1_000_000th Ramanujan prime is " + millionthRamanujanPrime);
List<Integer> primes = listPrimesLessThan(millionthRamanujanPrime);
int[] ramanujanPrimeIndexes = new int[primes.size()];
for ( int i = 0; i < ramanujanPrimeIndexes.length; i++ ) {
ramanujanPrimeIndexes[i] = primePi[primes.get(i)] - primePi[primes.get(i) / 2];
}
int lowerLimit = ramanujanPrimeIndexes[ramanujanPrimeIndexes.length - 1];
for ( int i = ramanujanPrimeIndexes.length - 2; i >= 0; i-- ) {
if ( ramanujanPrimeIndexes[i] < lowerLimit ) {
lowerLimit = ramanujanPrimeIndexes[i];
} else {
ramanujanPrimeIndexes[i] = 0;
}
}
List<Integer> ramanujanPrimes = new ArrayList<Integer>();
for ( int i = 0; i < ramanujanPrimeIndexes.length; i++ ) {
if ( ramanujanPrimeIndexes[i] != 0 ) {
ramanujanPrimes.add(primes.get(i));
}
}
int twinsCount = 0;
for ( int i = 0; i < ramanujanPrimes.size() - 1; i++ ) {
if ( ramanujanPrimes.get(i) + 2 == ramanujanPrimes.get(i + 1) ) {
twinsCount += 1;
}
}
System.out.println("There are " + twinsCount + " twins in the first " + limit + " Ramanujan primes.");
}
private static List<Integer> listPrimesLessThan(int aLimit) {
boolean[] composite = new boolean[aLimit + 1];
int n = 3;
int nSquared = 9;
while ( nSquared <= aLimit ) {
if ( ! composite[n] ) {
for ( int k = nSquared; k < aLimit; k += 2 * n ) {
composite[k] = true;
}
}
nSquared += ( n + 1 ) << 2;
n += 2;
}
List<Integer> result = new ArrayList<Integer>();
result.add(2);
for ( int i = 3; i < aLimit; i += 2 ) {
if ( ! composite[i] ) {
result.add(i);
}
}
return result;
}
private static int ramanujanPrime(int[] aPrimePi, int aNumber) {
int maximum = ramanujanMaximum(aNumber);
if ( ( maximum & 1) == 1 ) {
maximum -= 1;
}
int index = maximum;
while ( aPrimePi[index] - aPrimePi[index / 2] >= aNumber ) {
index -= 1;
}
return index + 1;
}
private static int[] initialisePrimePi(int aLimit) {
int[] result = new int[aLimit];
Arrays.fill(result, 1);
result[0] = 0;
result[1] = 0;
for ( int i = 4; i < aLimit; i += 2 ) {
result[i] = 0;
}
for ( int p = 3, square = 9; square < aLimit; p += 2 ) {
if ( result[p] != 0 ) {
for ( int q = square; q < aLimit; q += p << 1 ) {
result[q] = 0;
}
}
square += ( p + 1 ) << 2;
}
Arrays.parallelPrefix(result, Integer::sum);
return result;
}
private static int ramanujanMaximum(int aNumber) {
return (int) Math.ceil(4 * aNumber * Math.log(4 * aNumber));
}
}
</syntaxhighlight>
{{ out }}
<pre>
The 1_000_000th Ramanujan prime is 34072993
There are 74973 twins in the first 1000000 Ramanujan primes.
</pre>
Line 388 ⟶ 745:
There are 74,973 twins in the first 1,000,000 Ramanujan primes.
2.529 seconds</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import java.util.{ArrayList, Arrays, List}
object RamanujanPrimesTwins {
def main(args: Array[String]): Unit = {
val limit = 1_000_000
val primePi = initialisePrimePi(ramanujanMaximum(limit) + 1)
val millionthRamanujanPrime = ramanujanPrime(primePi, limit)
println(s"The 1_000_000th Ramanujan prime is $millionthRamanujanPrime")
val primes = listPrimesLessThan(millionthRamanujanPrime)
val ramanujanPrimeIndexes = new Array[Int](primes.size)
for (i <- 0 until primes.size by 1) {
ramanujanPrimeIndexes(i) = primePi(primes.get(i)) - primePi(primes.get(i) / 2)
}
var lowerLimit = ramanujanPrimeIndexes(ramanujanPrimeIndexes.length - 1)
for (i <- ramanujanPrimeIndexes.length - 2 to 0 by -1) {
if (ramanujanPrimeIndexes(i) < lowerLimit) {
lowerLimit = ramanujanPrimeIndexes(i)
} else {
ramanujanPrimeIndexes(i) = 0
}
}
val ramanujanPrimes = new ArrayList[Integer]()
for (i <- 0 until ramanujanPrimeIndexes.size by 1) {
if (ramanujanPrimeIndexes(i) != 0) {
ramanujanPrimes.add(primes.get(i))
}
}
var twinsCount = 0
for (i <- 0 until ramanujanPrimes.size - 1) {
if (ramanujanPrimes.get(i) + 2 == ramanujanPrimes.get(i + 1)) {
twinsCount += 1
}
}
println(s"There are $twinsCount twins in the first $limit Ramanujan primes.")
}
private def listPrimesLessThan(limit: Int): List[Integer] = {
val composite = new Array[Boolean](limit + 1)
var n = 3
var nSquared = 9
while (nSquared <= limit) {
if (!composite(n)) {
for (k <- nSquared until limit by (2*n) ) {
composite(k) = true
}
}
nSquared += (n + 1) << 2
n += 2
}
var result = new ArrayList[Integer]()
result.add(2)
for (i <- 3 until limit by 2) {
if (!composite(i)) {
result.add(i)
}
}
result
}
private def ramanujanPrime(primePi: Array[Int], number: Int): Int = {
var maximum = ramanujanMaximum(number)
if ((maximum & 1) == 1) {
maximum -= 1
}
var index = maximum
while (primePi(index) - primePi(index / 2) >= number) {
index -= 1
}
index + 1
}
private def initialisePrimePi(aLimit : Int): Array[Int] = {
val result = new Array[Int](aLimit )
Arrays.fill(result, 1)
result(0) = 0
result(1) = 0
for (i <- 4 until aLimit by 2) {
result(i) = 0
}
var p = 3;var square = 9;
while(square < aLimit) {
if ( result(p) != 0 ) {
for ( q <- square until aLimit by (p << 1) ) {
result(q) = 0;
}
}
square += ( p + 1 ) << 2;
p += 2
}
for (i <- 1 until result.length) {
result(i) += result(i - 1)
}
result
}
private def ramanujanMaximum(number: Int): Int = {
Math.ceil(4 * number * Math.log(4 * number)).toInt
}
}
</syntaxhighlight>
{{out}}
<pre>
The 1_000_000th Ramanujan prime is 34072993
There are 74973 twins in the first 1000000 Ramanujan primes.
</pre>
=={{header|Sidef}}==
Line 413 ⟶ 888:
<br>
As calculating the first 1 million Ramanujan primes individually is out of the question, we follow the Phix entry's clever strategy here which brings this task comfortably within our ambit.
<syntaxhighlight lang="
import "./math" for Int, Math
import "./fmt" for Fmt
var count
Line 480 ⟶ 955:
}
Fmt.print("There are $,d twins in the first $,d Ramanujan primes.", twins, limit)
System.print("Took %(Math.toPlaces(System.clock - start, 2, 0)) seconds.\n")
}</syntaxhighlight>
| |||