Jump to content

Ramanujan primes/twins: Difference between revisions

Ramanujan primes/twins (view source)

Revision as of 06:24, 10 September 2021

3,228 bytes added ,  2 years ago
→‎{{header|Phix}}: replaced with faster version
(Added Go)
(→‎{{header|Phix}}: replaced with faster version)
Line 135:
 
=={{header|Phix}}==
While finding the 1,000,000th Ramanujan prime is reasonably cheap (~70s2.6s), repeating that
trick to find all 1,000,000 of them individually is over 2a yearsmonths 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: #008080004080;">constantsequence</span> <span style="color: #000000;">limpi</span> <span style="color: #0000FF;">=</span> <span style="color: #0000000000FF;">1e5{}</span> <span style="color: #000080;font-style:italic;">-- 5.5s
--constant lim = 1e6 -- 1min 11s</span>▼
<span style="color: #004080008080;">atomprocedure</span> <span style="color: #000000;">t0primeCounter</span> <span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #7060A8000000;">timelimit</span><span style="color: #0000FF;">()</span>
<span style="color: #004080000000;">sequencepi</span> <span style="color: #0000000000FF;">picache=</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;">functionif</span> <span style="color: #000000;">pilimit</span> <span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n1</span> <span style="color: #0000FF008080;">)then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">npi</span><span style="color: #0000FF;">=[</span><span style="color: #000000;">01</span> <span style="color: #0080800000FF;">then]</span> <span style="color: #0080800000FF;">return=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">iffor</span> <span style="color: #000000;">ni</span><span style="color: #0000FF;">>=</span><span style="color: #7060A8000000;">length4</span> <span style="color: #0000FF008080;">(to</span> <span style="color: #000000;">picachelimit</span> <span style="color: #0000FF008080;">by</span> <span style="color: #000000;">)2</span> <span style="color: #008080;">thendo</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primespi</span> <span style="color: #0000FF;">=[</span> <span style="color: #7060A8000000;">get_primes_lei</span><span style="color: #0000FF;">(]</span> <span style="color: #0000000000FF;">n=</span> <span style="color: #0000FF000000;">)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;">kp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8000000;">binary_search3</span><span style="color: #0000FF;">(,</span> <span style="color: #000000;">isq</span> <span style="color: #0000FF;">,=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">)9</span>
<span style="color: #008080;">ifwhile</span> <span style="color: #000000;">ksq</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;">endlimit</span> <span style="color: #008080;">ifdo</span>
<span style="color: #000000008080;">picacheif</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;">k0</span> <span style="color: #008080;">then</span>
▲ <span style="color: #008080;">for</span> <span style="color: #000000;">iq</span><span style="color: #0000FF;">=</span><span style="color: #7060A8000000;">lengthsq</span> <span style="color: #0000FF008080;">(to</span> <span style="color: #000000;">picachelimit</span> <span style="color: #0000FF008080;">)+by</span> <span style="color: #000000;">1p</span> <span style="color: #0080800000FF;">to*</span> <span style="color: #000000;">n2</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;">returnend</span> <span style="color: #000000;">picache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF008080;">]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_primeramanujanPrime</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: #004080008080;">integerif</span> <span style="color: #000000;">maxpossn</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;">41</span><span style="color: #0000FF;">*</span><span style="color: #000000008080;">nthen</span><span style="color: #0000FF;">*(</span><span style="color: #7060A8008080;">logreturn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">42</span><span style="color: #0000FF;">*</span><span style="color: #000000008080;">nend</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: #0000FF008080;">))))if</span>
<span style="color: #008080004080;">forinteger</span> <span style="color: #000000;">imaxposs</span> <span style="color: #0000FF;">=</span><span style="color: #000000;">maxposs</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1ramanujanMax</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-(</span><span style="color: #000000;">1n</span> <span style="color: #0080800000FF;">do)</span>
<span style="color: #008080;">iffor</span> <span style="color: #000000;">pii</span><span style="color: #0000FF;">(=</span><span style="color: #000000;">imaxposs</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #0000007060A8;">piodd</span><span style="color: #0000FF;">(</span><span style="color: #7060A8000000;">floormaxposs</span><span style="color: #0000FF;">()</span> <span style="color: #000000008080;">ito</span><span style="color: #0000FF;">/</span><span style="color: #000000;">21</span> <span style="color: #0000FF008080;">))by</span> <span style="color: #0000FF;"><-</span> <span style="color: #000000;">n2</span> <span style="color: #008080;">thendo</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 ⟶ 183:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080008080;">integerconstant</span> <span style="color: #000000;">rplimlim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Ramanujan_prime1e5</span><span style="color: #0000FF;">(</span> <span style="color: #000000000080;">lim</span><span font-style="color: #0000FFitalic;">)</span>-- 0.6s
▲ --constant lim = 1e6 -- 1min4.7s 11s-- (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: #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 ⟶ 214:
The 100,000th Ramanujan prime is 2,916,539
There are 8,732 twins in the first 100,000 Ramanujan primes
"50.5s6s"
</pre>
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>
 
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/315830"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information