(phixonline)-->
with javascript_semantics
constant maxbase=36 -- or 62
function evalpoly(integer x, sequence p)
integer result = 0
for y=1 to length(p) do
result = result*x + p[y]
end for
return result
end function
function stringify(sequence digits)
string res = repeat('0',length(digits))
for i=1 to length(digits) do
integer di = digits[i]
res[i] = di + iff(di<=9?'0':iff(di<36?'A'-10:'a'-36))
end for
return res
end function
procedure max_prime_bases(integer ndig, maxbase)
atom t0 = time(),
t1 = time()+1
sequence maxprimebases = {},
digits = repeat(0,ndig)
integer maxlen = 0,
limit = power(10,ndig),
maxdigit = maxbase
if ndig>1 then digits[1] = 1 end if
while true do
for i=length(digits) to 1 by -1 do
integer di = digits[i]+1
if di<maxdigit then -- (or 9, see below)
digits[i] = di
exit
else
di = 0
digits[i] = 0
end if
end for
integer minbase = max(digits)+1,
maxposs = maxbase-minbase+1
if minbase=1 then exit end if -- (ie we just wrapped round to all 0s)
sequence bases = {}
for base=minbase to maxbase do
if is_prime(evalpoly(base,digits)) then
bases &= base
else
maxposs -= 1
if maxposs<maxlen then exit end if -- (a 5-fold speedup)
end if
end for
integer l = length(bases)
if l>maxlen then
maxlen = l
maxdigit = maxbase-maxlen -- (around 20-fold speedup)
maxprimebases = {}
end if
if l=maxlen then
maxprimebases &= {{stringify(digits), bases}}
end if
if platform()!=JS and time()>t1 then
progress("%V\r",{digits})
t1 = time()+1
end if
end while
string e = elapsed(time()-t0)
printf(1,"%d character numeric strings that are prime in %d bases (%s):\n",{ndig,maxlen,e})
for i=1 to length(maxprimebases) do
printf(1," %s => %V\n", maxprimebases[i])
end for
printf(1,"\n")
end procedure
for n=1 to iff(platform()=JS or maxbase>36?4:6) do
max_prime_bases(n, maxbase)
end for