Smarandache prime-digital sequence: Difference between revisions

Content added Content deleted
m (Forth - minor edit)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,319: Line 1,319:
but because of the massive gaps (eg between 777,777,777 and 2,222,222,223) it proved much faster
but because of the massive gaps (eg between 777,777,777 and 2,222,222,223) it proved much faster
to test each candidate for primality individually. Timings below show just how much this improves things.
to test each candidate for primality individually. Timings below show just how much this improves things.
<lang Phix>atom t0 = time()
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence spds = {2,3,5,7}
<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>
atom nxt_candidate = 23
<span style="color: #004080;">sequence</span> <span style="color: #000000;">spds</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}</span>
sequence adj = {{4,-4},sq_mul({1,2,2,-5},10)},
<span style="color: #004080;">atom</span> <span style="color: #000000;">nxt_candidate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">23</span>
adjn = {1,1}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">adj</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)},</span>

<span style="color: #000000;">adjn</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
include mpfr.e
mpz zprime = mpz_init()
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
randstate state = gmp_randinit_mt()
<span style="color: #004080;">mpz</span> <span style="color: #000000;">zprime</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>

procedure populate_spds(integer n)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">populate_spds</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
while length(spds)<n do
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">spds</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
mpz_set_d(zprime,nxt_candidate)
<span style="color: #7060A8;">mpz_set_d</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zprime</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nxt_candidate</span><span style="color: #0000FF;">)</span>
if mpz_probable_prime_p(zprime,state) then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zprime</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
spds &= nxt_candidate
<span style="color: #000000;">spds</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">nxt_candidate</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=1 to length(adjn) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">adjn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
sequence adjs = adj[i]
<span style="color: #004080;">sequence</span> <span style="color: #000000;">adjs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">adj</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
integer adx = adjn[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">adx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">adjn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
nxt_candidate += adjs[adx]
<span style="color: #000000;">nxt_candidate</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">adjs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">adx</span><span style="color: #0000FF;">]</span>
adx += 1
<span style="color: #000000;">adx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
if adx<=length(adjs) then
<span style="color: #008080;">if</span> <span style="color: #000000;">adx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">adjs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
adjn[i] = adx
<span style="color: #000000;">adjn</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;">adx</span>
exit
end if
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
adjn[i] = 1
<span style="color: #000000;">adjn</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;">1</span>
if i=length(adjn) then
<span style="color: #008080;">if</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;">adjn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
-- (this is eg 777, by now 223 carry 1, -> 2223)
<span style="color: #000080;font-style:italic;">-- (this is eg 777, by now 223 carry 1, -&gt; 2223)</span>
adj = append(adj,sq_mul(adj[$],10))
<span style="color: #000000;">adj</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">adj</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">adj</span><span style="color: #0000FF;">[$],</span><span style="color: #000000;">10</span><span style="color: #0000FF;">))</span>
adjn = append(adjn, 1)
<span style="color: #000000;">adjn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">adjn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
nxt_candidate += adj[$][2]
<span style="color: #000000;">nxt_candidate</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">adj</span><span style="color: #0000FF;">[$][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
exit
end if
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

populate_spds(25)
<span style="color: #000000;">populate_spds</span><span style="color: #0000FF;">(</span><span style="color: #000000;">25</span><span style="color: #0000FF;">)</span>
printf(1,"spds[1..25]:%v\n",{spds[1..25]})
<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;">"spds[1..25]:%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">spds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">25</span><span style="color: #0000FF;">]})</span>
for n=2 to 5 do
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">do</span>
integer p = power(10,n)
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
populate_spds(p)
<span style="color: #000000;">populate_spds</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
printf(1,"spds[%d]:%d\n",{p,spds[p]})
<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;">"spds[%d]:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">spds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">]})</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for n=7 to 10 do
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">7</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
atom p = power(10,n),
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
dx = abs(binary_search(p,spds))-1
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">spds</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span>
printf(1,"largest spds prime less than %,15d:%,14d\n",{p,spds[dx]})
<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;">"largest spds prime less than %,15d:%,14d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">spds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">]})</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?elapsed(time()-t0)</lang>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
{{out}}
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Smarandache_prime-digital_sequence"