A354718 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).

-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, 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, 7, 8, 9, 10, -1, 7, -1, -1, -1, 7, -1, 9, -1, -1, -1, 10, 11, 8, 9

Offset: 1

Author

Charles Paul, Jun 03 2022

Keywords

• sign
• base

Comments

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.

Examples

			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).
a(101) = 2, because 2^2*1 + 2*0 + 1*1 = 5, which is prime.
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).
a(100) = -1, because in any base b, 100_b = b^2, which cannot be prime.
a(112) = -1, because for any base b, b^2 + b + 2 is even (i.e., divisible by 2).
		

Programs

Python

# Self-explanatory
def is_prime(n):
     return not (n < 2 or any(n % x == 0 for x in range(2, int(n ** 0.5) + 1)))
# Evaluate an intish string in a given base
def atoi_base(s, b):
    out = 0
    for i in range(len(s)):
        d = s[-1-i]
        out += (b**i)*int(d)
    return out
# Constants
NUM_TERMS = 200 # Number of terms to generate
MAX_VALUE = 999 # Maximum base to consider before saying "no base will do this"
NUL_RESULT = -1 # Value returned when no valid base can be found
# Main func
def a(n):
    assert(n > 0)
    # Start with 1 ... 9
    if n < 10:
        return n+1 if is_prime(n) else NUL_RESULT
    # Check all bases up to MAX_VALUE
    base = int(max(str(n))) + 1
    while True:
        if base >= MAX_VALUE:
            return NUL_RESULT
            break
        elif is_prime(atoi_base(str(n), base)):
            return base
            break
        else:
            base += 1
for n in range(1, NUM_TERMS):
    print(a(n), end=', ')