Find largest left truncatable prime in a given base: Difference between revisions

← Older editNewer edit →
Content deleted Content added
PureFox (talk | contribs)
9,493 edits
Added Wren
Petelomax (talk | contribs)
7,833 edits
m →‎{{header|Phix}}: added syntax colouring the hard way
Line 1,342: Line 1,342:
{{trans|C}}
{{trans|C}}
Depth-first search uses 1% of the memory of width-first search, and as a result runs about 30% faster (while still doing exactly the same actual work).
Depth-first search uses 1% of the memory of width-first search, and as a result runs about 30% faster (while still doing exactly the same actual work).
<lang Phix>include mpfr.e
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
randstate state = gmp_randinit_mt()
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
sequence tens = mpz_inits(1,1),
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tens</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</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>
vals = mpz_inits(1),
<span style="color: #000000;">vals</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
digits = {0}
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
mpz answer = mpz_init(0)
<span style="color: #004080;">mpz</span> <span style="color: #000000;">answer</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
integer base, seen_depth
<span style="color: #004080;">integer</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">seen_depth</span>
procedure add_digit(integer i)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">add_digit</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
atom t1 = time()+1
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
if i>length(vals) 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;">vals</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
vals &= mpz_init_set(vals[i-1])
<span style="color: #000000;">vals</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
tens &= mpz_init_set(tens[i-1])
<span style="color: #000000;">tens</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tens</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
mpz_mul_si(tens[i],tens[i],base)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tens</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">tens</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
digits &= 0
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">0</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for d=1 to base-1 do
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
digits[i] = d
<span style="color: #000000;">digits</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;">d</span>
mpz_set(vals[i], vals[i-1])
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
mpz_addmul_ui(vals[i], tens[i], d)
<span style="color: #7060A8;">mpz_addmul_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">tens</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
if mpz_probable_prime_p(vals[i], state) then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
if i>seen_depth
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">seen_depth</span>
or (i==seen_depth and mpz_cmp(vals[i], answer)>0) then
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">==</span><span style="color: #000000;">seen_depth</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">answer</span><span style="color: #0000FF;">)></span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
mpz_set(answer, vals[i])
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">answer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
seen_depth = i
<span style="color: #000000;">seen_depth</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
add_digit(i+1)
<span style="color: #000000;">add_digit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if time()>t1 then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
printf(1,"\tbase %d: (%d) %v \r", {base, seen_depth, digits[1..i]})
<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;">" base %d: (%d) %v \r"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">seen_depth</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]})</span>
end if
<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 procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure do_base()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">do_base</span><span style="color: #0000FF;">()</span>
atom t0 = time()
<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>
seen_depth = 0
<span style="color: #000000;">seen_depth</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
mpz_set_si(answer, 0)
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">answer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
mpz_set_si(tens[1], 1)
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tens</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>
for i=2 to length(tens) do
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tens</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
mpz_mul_si(tens[i], tens[i-1], base)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tens</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">tens</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for i=1 to base 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: #000000;">base</span> <span style="color: #008080;">do</span>
integer pi = get_prime(i)
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
if pi>=base then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">base</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
mpz_set_si(vals[1], pi)
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vals</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span>
digits[1] = pi
<span style="color: #000000;">digits</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;">pi</span>
add_digit(2)
<span style="color: #000000;">add_digit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
string rd = mpz_get_str(answer),
<span style="color: #004080;">string</span> <span style="color: #000000;">rd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">answer</span><span style="color: #0000FF;">),</span>
rb = mpz_get_str(answer,base)
<span style="color: #000000;">rb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">answer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
t0 = time()-t0
<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;">t0</span>
string t = iff(t0>0.1?" ["&elapsed(t0)&"]":"")
<span style="color: #004080;">string</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">></span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" ["</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"]"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
printf(1,"%3d %-41s (%s, %d digits)%s\n", {base,rd,rb,length(rb),t})
<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;">"%3d %-41s (%s, %d digits)%s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rb</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rb</span><span style="color: #0000FF;">),</span><span style="color: #000000;">t</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
atom t0 = time()
<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>
for base=3 to 31 do
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">31</span> <span style="color: #008080;">do</span>
if base<=17 or remainder(base,2)=1 then
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">27</span><span style="color: #0000FF;">,</span><span style="color: #000000;">31</span><span style="color: #0000FF;">}))</span>
do_base()
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">17</span> <span style="color: #008080;">or</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span>
end for
<span style="color: #000000;">do_base</span><span style="color: #0000FF;">()</span>
?elapsed(time()-t0)</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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}}
Even (as in multiples of 2) bases above 18 omitted, so that it completes in a reasonable timeframe.<br>
Even (as in multiples of 2) bases above 18 omitted, so that it completes in a reasonable timeframe, although it does show progress.<br>
Likewise several further numbers are omitted under pwa/p2js so you can stare at a blank screen for about 6s instead of 4&frac12; mins.<br>
I once managed to get 18, but it took over 40 minutes, likewise 22 took 3 mins 46s, 33 over 8 mins, and 35 nearly 2 mins.
I once managed to get 18, but it took over 40 minutes, likewise 22 took 3 mins 46s, 33 over 8 mins, and 35 nearly 2 mins.
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base"