|
%I #35 Sep 12 2023 12:29:34
%S -1,3,4,-1,6,-1,8,-1,-1,2,2,3,4,7,6,7,10,9,10,-1,3,-1,4,-1,6,-1,8,-1,
%T 10,-1,4,5,-1,5,6,-1,8,11,-1,-1,7,-1,5,-1,6,-1,9,-1,11,-1,6,7,8,11,-1,
%U 7,8,9,10,-1,7,-1,-1,-1,7,-1,9,-1,-1,-1,10,11,8,9
%N a(n) is the smallest number b such that n, written in base 10 and interpreted as a base-b number, is a prime (or -1 if no such base exists).
%C The minimum base considered is one greater than the greatest digit, i.e., max_digit(n) = d requires a base > d. E.g., a(17)=10, even though "base 4" 4*1 + 1*7 = 11 is prime.
%e a(14) = 7, because 14_7 = 7*1 + 1*4 = 11, which is prime, but both 14_6 = 10 and 14_5 = 9 are nonprime (and the digit 4 requires a base b > 4).
%e a(101) = 2, because 2^2*1 + 2*0 + 1*1 = 5, which is prime.
%e a(24) = -1, because the digits 2 and 4 share GCD 2, so there is no base b in which 24_b is prime (because 24_b is divisible by 2 in any base b).
%e a(100) = -1, because in any base b, 100_b = b^2, which cannot be prime.
%e a(112) = -1, because for any base b, b^2 + b + 2 is even (i.e., divisible by 2).
%o (Python)
%o # Self-explanatory
%o def is_prime(n):
%o return not (n < 2 or any(n % x == 0 for x in range(2, int(n ** 0.5) + 1)))
%o # Evaluate an intish string in a given base
%o def atoi_base(s, b):
%o out = 0
%o for i in range(len(s)):
%o d = s[-1-i]
%o out += (b**i)*int(d)
%o return out
%o # Constants
%o NUM_TERMS = 200 # Number of terms to generate
%o MAX_VALUE = 999 # Maximum base to consider before saying "no base will do this"
%o NUL_RESULT = -1 # Value returned when no valid base can be found
%o # Main func
%o def a(n):
%o assert(n > 0)
%o # Start with 1 ... 9
%o if n < 10:
%o return n+1 if is_prime(n) else NUL_RESULT
%o # Check all bases up to MAX_VALUE
%o base = int(max(str(n))) + 1
%o while True:
%o if base >= MAX_VALUE:
%o return NUL_RESULT
%o break
%o elif is_prime(atoi_base(str(n), base)):
%o return base
%o break
%o else:
%o base += 1
%o for n in range(1, NUM_TERMS):
%o print(a(n), end=', ')
%K sign,base
%O 1,2
%A _Charles Paul_, Jun 03 2022
|
