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

=={{header|Phix}}==

{{trans|Swift}}

Using is_prime_mr() from [[Miller–Rabin_primality_test#Phix]], unfortunately glacially slow...<br>

(also tried using using Miller_Rabin() from that same page, marginally even slower...)

<lang Phix>function largestLeftTruncatablePrime(integer base)

integer radix = 0

sequence candidates = {ba_new(0)}

while true do

bigatom multiplier = ba_power(base,radix)

sequence newCandidates = {}

for i=1 to base-1 do

bigatom mi = ba_multiply(i,multiplier)

for j=1 to length(candidates) do

bigatom cj = candidates[j],

cm = ba_add(cj,mi)

if is_prime_mr(cm) then

newCandidates = append(newCandidates,cm)

end if

end for

end for

if newCandidates={} then exit end if

candidates = newCandidates

radix += 1

printf(1,"length %d candidates: %d \r",{radix,length(candidates)})

end while

printf(1," \r")

return ba_sprint(candidates[$])

end function

for i=3 to 17 do

atom t0 = time()

string r = largestLeftTruncatablePrime(i),

t = elapsed(time()-t0)

printf(1,"base %d: %s (%s)\n",{i,r,t})

end for</lang>

{{out}}

<pre>

base 3: 23 (0.0s)

base 4: 4091 (0.3s)

base 5: 7817 (0.2s)

base 6: 4836525320399 (1 minute and 34s)

base 7: 817337 (0.5s)

base 8: 14005650767869 (1 minute and 27s)

base 9: 1676456897 (11.7s)

base 10: 357686312646216567629137 (52 minutes and 30s)

base 11: 2276005673 (5.5s)

length 10 candidates: 14885

<killed>

</pre>