79 lines
1.6 KiB
Python
79 lines
1.6 KiB
Python
import timeit
|
|
from collections import deque
|
|
|
|
from sympy import isprime
|
|
|
|
|
|
def digits(num: int):
|
|
digits = deque()
|
|
|
|
while num > 0:
|
|
digits.appendleft(num % 10)
|
|
num //= 10
|
|
|
|
return digits
|
|
|
|
|
|
def all_digits_are_less(dig: list[int], b: int):
|
|
for d in dig:
|
|
if d >= b:
|
|
return False
|
|
|
|
return True
|
|
|
|
|
|
def eval_poly(coeffs: list[int], x: int):
|
|
y = 0
|
|
|
|
for pv in coeffs:
|
|
y = y * x + pv
|
|
|
|
return y
|
|
|
|
|
|
def max_prime_bases(ndig: int, maxbase: int):
|
|
maxprimebases = [[]]
|
|
nwithbases = [0]
|
|
maxprime = 10 ** (ndig) - 1
|
|
|
|
for p in range(int((maxprime + 1) / 10), maxprime + 1):
|
|
dig = digits(p)
|
|
bases = [
|
|
b
|
|
for b in range(2, maxbase + 1)
|
|
if isprime(eval_poly(dig, b)) and all_digits_are_less(dig, b)
|
|
]
|
|
|
|
if len(bases) > len(maxprimebases[0]):
|
|
maxprimebases = [bases]
|
|
nwithbases = [p]
|
|
|
|
elif len(bases) == len(maxprimebases[0]):
|
|
maxprimebases.append(bases)
|
|
nwithbases.append(p)
|
|
|
|
alen, vlen = len(maxprimebases[0]), len(maxprimebases)
|
|
|
|
print(
|
|
"\nThe maximum number of prime valued bases for base 10 numeric strings of length",
|
|
ndig,
|
|
"is",
|
|
f"{alen}.",
|
|
"The base 10 value list of",
|
|
"these" if vlen > 1 else "this",
|
|
"is: ",
|
|
)
|
|
|
|
for i in range(len(maxprimebases)):
|
|
print(nwithbases[i], "=>", maxprimebases[i])
|
|
|
|
|
|
def main():
|
|
for n in range(1, 7):
|
|
max_prime_bases(n, 36)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
execution_time = timeit.timeit(main, number=1)
|
|
print(f"Execution time: {execution_time:.6f} seconds")
|