Jump to content

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

Find largest left truncatable prime in a given base (view source)

Revision as of 20:27, 22 March 2020

2,418 bytes added ,  4 years ago
→‎{{header|Phix}}: replaced with gmp version
(→‎{{header|Phix}}: replaced with gmp version)
Line 1,259:
 
=={{header|Phix}}==
{{libheader|mpfr}}
{{improve|Phix|use gmp instead}}
{{trans|SwiftC}}
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).
Using is_prime_mr() from [[Miller–Rabin_primality_test#Phix]], unfortunately glacially slow...<br>
<lang Phix>include mpfr.e
(also tried using using Miller_Rabin() from that same page, marginally even slower...)
randstate state = gmp_randinit_mt()
<lang Phix>function largestLeftTruncatablePrime(integer base)
sequence tens = mpz_inits(1,1),
integer radix = 0
vals = mpz_inits(1),
sequence candidates = {ba_new(0)}
digits = {0}
while true do
mpz answer = mpz_init(0)
bigatom multiplier = ba_power(base,radix)
integer base, seen_depth
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
procedure add_digit(integer i)
for i=3 to 17 do
atom t1 = time()+1
if i>length(vals) then
vals &= mpz_init_set(vals[i-1])
tens &= mpz_init_set(tens[i-1])
mpz_mul_si(tens[i],tens[i],base)
digits &= 0
end if
for d=1 to base-1 do
digits[i] = d
mpz_set(vals[i], vals[i-1])
mpz_addmul_ui(vals[i], tens[i], d)
if mpz_probable_prime_p(vals[i], state) then
if i>seen_depth
or (i==seen_depth and mpz_cmp(vals[i], answer)>0) then
if not mpz_probable_prime_p(vals[i], state) then continue end if
mpz_set(answer, vals[i])
seen_depth = i
end if
add_digit(i+1)
end if
if time()>t1 then
printf(1,"\tbase %d: (%d) %v \r", {base, seen_depth, digits[1..i]})
end if
end for
end procedure
procedure do_base()
atom t0 = time()
seen_depth = 0
string r = largestLeftTruncatablePrime(i),
mpz_set_si(answer, 0)
t = elapsed(time()-t0)
mpz_set_si(tens[1], 1)
printf(1,"base %d: %s (%s)\n",{i,r,t})
for i=2 to length(tens) do
end for</lang>
mpz_mul_si(tens[i], tens[i-1], base)
end for
for i=1 to base do
integer pi = get_prime(i)
if pi>=base then exit end if
mpz_set_si(vals[1], pi)
digits[1] = pi
add_digit(2)
end for
string rd = mpz_get_str(answer),
rb = mpz_get_str(answer,base)
t0 = time()-t0
string t = iff(t0>0.1?" ["&elapsed(t0)&"]":"")
printf(1,"%3d %-41s (%s, %d digits)%s\n", {base,rd,rb,length(rb),t})
end procedure
atom t0 = time()
for base=3 to 31 do
if base<=17 or remainder(base,2)=1 then
do_base()
end if
end for
?elapsed(time()-t0)</lang>
{{out}}
Even (as in multiples of 2) bases above 18 omitted, so that it completes in a reasonable timeframe.<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.
<pre>
3 23 (212, 3 digits)
base 3: 23 (0.0s)
4 4091 (333323, 6 digits)
base 4: 4091 (0.3s)
5 7817 (222232, 6 digits)
base 5: 7817 (0.2s)
base 6: 4836525320399 (1 minute and 34s (14141511414451435, 17 digits)
7 817337 (6642623, 7 digits)
base 7: 817337 (0.5s)
base 8: 14005650767869 (1 minute and 27s (313636165537775, 15 digits)
base 9: 1676456897 (11.7s4284484465, 10 digits)
base 10: 357686312646216567629137 (52 minutes and 30s (357686312646216567629137, 24 digits) [0.2s]
base 11: 2276005673 (5.5sa68822827, 9 digits)
12 13092430647736190817303130065827539 (471a34a164259ba16b324ab8a32b7817, 32 digits) [12.0s]
length 10 candidates: 14885
13 812751503 (cc4c8c65, 8 digits)
<killed>
14 615419590422100474355767356763 (d967ccd63388522619883a7d23, 26 digits) [2.3s]
15 34068645705927662447286191 (6c6c2ce2ceeea4826e642b, 22 digits) [0.6s]
16 1088303707153521644968345559987 (dbc7fba24fe6aec462abf63b3, 25 digits) [2.0s]
17 13563641583101 (6c66cc4cc83, 11 digits)
19 546207129080421139 (cieg86gcea2c6h, 14 digits)
21 391461911766647707547123429659688417 (g8agg2gca8cak4k68gea4g2k22h, 27 digits) [5.8s]
23 116516557991412919458949 (immgm6c6imci66a4h, 17 digits)
25 8211352191239976819943978913 (me6om6oecgcc24c6eg6d, 20 digits) [1s]
27 10681632250257028944950166363832301357693 (o2akk6ekg844kaia4mack6c2ecab, 28 digits) [12.0s]
29 4300289072819254369986567661 (kcg66agsckeiasmckkj, 19 digits) [0.4s]
31 645157007060845985903112107793191 (uuauikuc4ui6oceci642sd, 22 digits) [1.3s]
"38s"
</pre>
 
Petelomax
7,820

edits

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