A354718 - OEIS

%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