Ramanujan primes/twins: Difference between revisions

Line 135:

=={{header|Phix}}==

While finding the 1,000,000th Ramanujan prime is reasonably cheap (~~~70s~~), repeating that

While finding the 1,000,000th Ramanujan prime is reasonably cheap (~2.6s), repeating that

trick to find all 1,000,000 of them individually is over 2 ~~years~~ worth of CPU time.

trick to find all 1,000,000 of them individually is over a months worth of CPU time.

Calculating pi(p) - pi(floor(pi/2) for all (normal) primes below that one millionth, and then

filtering them based on that list is significantly faster, and finally we can scan for twins.

with javascript_semantics

~~constant~~ ~~lim~~ = ~~1e5~~ ~~-- 5.5s~~

sequence pi = {}

⚫

--constant lim = 1e6 -- ~~1min~~ ~~11s~~

~~atom~~ t0 = ~~time~~()

procedure primeCounter(integer limit)

~~sequence~~ ~~picache~~ = {}

pi = repeat(1,limit)

~~function~~ pi~~(</span~~>~~integer~~ n)

if limit > 1 then

~~<span~~ ~~style="color:~~ ~~#008080;">if~~ n=0 ~~then~~ ~~return~~ 0~~ end if~~

pi[1] = 0

if n>~~length~~(~~picache~~) ~~then~~

for i=4 to limit by 2 do

~~<span~~ ~~style="color:~~ ~~#004080;">sequence~~ ~~primes~~ = ~~get_primes_le~~(n)

pi[i] = 0

end for

⚫

for i=~~length~~(~~picache~~)+1 to n do

integer k = ~~binary_search~~(i,~~primes)~~

integer p = 3, sq = 9

if k<~~0~~ ~~then~~ ~~k=-k-1 end~~ if

while sq<=limit do

~~picache~~ &= k

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

~~return~~ picache[n]

end procedure

function ramanujanMax(integer n)

return floor(4*n*log(4*n))

end function

function ~~Ramanujan_prime~~(integer n)

function ramanujanPrime(integer n)

~~integer~~ ~~maxposs~~ =~~ floor(ceil(~~4~~<span~~ ~~style="color: #0000FF;">*~~n~~<span~~ ~~style="color: #0000FF;">*(~~~~log~~~~<span~~ ~~style="color: #0000FF;">(~~4~~<span~~ ~~style="color: #0000FF;">*~~n~~<span~~ ~~style="color: #0000FF;">)/~~log(2~~))))~~

if n=1 then return 2 end if

~~for~~ i=~~maxposs to~~ 1 ~~by~~ -1 do

integer maxposs = ramanujanMax(n)

if pi(i~~)~~ - pi(~~floor~~(i~~<span~~ ~~style="color: #0000FF;">/~~2)) < n ~~then~~

for i=maxposs-odd(maxposs) to 1 by -2 do

if pi[i]-pi[floor(i/2)] < n then

return i + 1

end if

Line 168:

Line 183:

end function

~~integer~~ ~~rplim~~ = ~~Ramanujan_prime~~~~<span~~ ~~style="color:~~ ~~#0000FF;">(~~lim<span~~ style~~="color~~: ~~#0000FF~~;">~~)

constant lim = 1e5 -- 0.6s

⚫

--constant lim = 1e6 -- 4.7s -- (not pwa/p2js)

atom t0 = time()

primeCounter(ramanujanMax(lim))

integer rplim = ramanujanPrime(lim)

printf(1,"The %,dth Ramanujan prime is %,d\n", {lim,rplim})

function rpc(integer p) return pi(p)-pi(floor(p/2)) end function

function rpc(integer p) return pi[p]-pi[floor(p/2)] end function

sequence r = get_primes_le(rplim),

c = apply(r,rpc)

Line 195:

Line 214:

The 100,000th Ramanujan prime is 2,916,539

There are 8,732 twins in the first 100,000 Ramanujan primes

"5.5s"

"0.6s"

</pre>

with the higher limit:

with the higher limit (desktop/Phix only, alas not possible under pwa/p2js):

<pre>

The 1,000,000th Ramanujan prime is 34,072,993

There are 74,973 twins in the first 1,000,000 Ramanujan primes

"4.7s"

"1 minute and 11s"

</pre>

@@ Line 135: / Line 135: @@
 =={{header|Phix}}==
-While finding the 1,000,000th Ramanujan prime is reasonably cheap (~70s), repeating that
+While finding the 1,000,000th Ramanujan prime is reasonably cheap (~2.6s), repeating that
-trick to find all 1,000,000 of them individually is over 2 years worth of CPU time.
+trick to find all 1,000,000 of them individually is over a months worth of CPU time.
 Calculating pi(p) - pi(floor(pi/2) for all (normal) primes below that one millionth, and then
 filtering them based on that list is significantly faster, and finally we can scan for twins.
 <!--<lang Phix>(phixonline)-->
  <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
- <span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e5</span>      <span style="color: #000080;font-style:italic;">-- 5.5s
+ <span style="color: #004080;">sequence</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
- --constant lim = 1e6    -- 1min 11s</span>
- <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
+ <span style="color: #008080;">procedure</span> <span style="color: #000000;">primeCounter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
- <span style="color: #004080;">sequence</span> <span style="color: #000000;">picache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
+     <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
- <span style="color: #008080;">function</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
+     <span style="color: #008080;">if</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
-     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+         <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
-     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">picache</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
+         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
-         <span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
+             <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">picache</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
-             <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span>
+         <span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span>
-             <span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+         <span style="color: #008080;">while</span> <span style="color: #000000;">sq</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">limit</span> <span style="color: #008080;">do</span>
-             <span style="color: #000000;">picache</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">k</span>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+                 <span style="color: #008080;">for</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sq</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
+                     <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
+                 <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+             <span style="color: #000000;">sq</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span>
+             <span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
+         <span style="color: #004080;">atom</span> <span style="color: #000000;">total</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
+         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span>
+             <span style="color: #000000;">total</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
+             <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">total</span>
          <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
      <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-     <span style="color: #008080;">return</span> <span style="color: #000000;">picache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
+     <span style="color: #008080;">return</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
  <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
- <span style="color: #008080;">function</span> <span style="color: #000000;">Ramanujan_prime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
-     <span style="color: #004080;">integer</span> <span style="color: #000000;">maxposs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*(</span><span style="color: #7060A8;">log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)/</span><span style="color: #7060A8;">log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))))</span>
+     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">2</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxposs</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
+     <span style="color: #004080;">integer</span> <span style="color: #000000;">maxposs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
-         <span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
+     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxposs</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxposs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
+         <span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
              <span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
          <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
@@ Line 168: / Line 183: @@
  <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
- <span style="color: #004080;">integer</span> <span style="color: #000000;">rplim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Ramanujan_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span>
+ <span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e5</span>      <span style="color: #000080;font-style:italic;">-- 0.6s
+ --constant lim = 1e6    -- 4.7s -- (not pwa/p2js)</span>
+ <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
+ <span style="color: #000000;">primeCounter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ramanujanMax</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">))</span>
+ <span style="color: #004080;">integer</span> <span style="color: #000000;">rplim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ramanujanPrime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span>
  <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %,dth Ramanujan prime is %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rplim</span><span style="color: #0000FF;">})</span>
- <span style="color: #008080;">function</span> <span style="color: #000000;">rpc</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">rpc</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  <span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rplim</span><span style="color: #0000FF;">),</span>
           <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rpc</span><span style="color: #0000FF;">)</span>
@@ Line 195: / Line 214: @@
 The 100,000th Ramanujan prime is 2,916,539
 There are 8,732 twins in the first 100,000 Ramanujan primes
-"5.5s"
+"0.6s"
 </pre>
-with the higher limit:
+with the higher limit (desktop/Phix only, alas not possible under pwa/p2js):
 <pre>
 The 1,000,000th Ramanujan prime is 34,072,993
 There are 74,973 twins in the first 1,000,000 Ramanujan primes
+"4.7s"
-"1 minute and 11s"
 </pre>