A370531 The smallest number in base n such that two digits (and no fewer) need to be changed to get a prime.

8, 24, 24, 90, 90, 119, 200, 117, 200, 319, 528, 1131, 1134, 525, 1328, 1343, 1332, 1330, 1340, 2478, 7260, 1334, 5352, 4300, 5954, 4833, 13188, 8468, 10800, 15686, 11744, 19338, 19618, 22575, 19620, 15688, 28234, 19617, 25480, 31406, 19614, 40291, 25476, 31410

Offset

2,1

Comments

Any digit, including the most significant, can be changed to 0.

If one defines the Prime-Erdős-Number PEN(n, k) in base n of a number k to be the minimum number of the base-n digits of k that must be changed to get a prime, then a(n) is the smallest number k such that PEN(n, k) = 2.

Adding preceding 0's to be changed does not appear to change any of the entries given below.

Links

Michael S. Branicky, Table of n, a(n) for n = 2..143

Example

a(2) = 8 = 1000_2 can be changed to the prime 1011_2 (11 in decimal) by changing the last two digits.  Although 4 = 100_2 can be changed to the prime 111_2 by changing two digits, it can also be changed to the prime 101_2 by only one base-2 digit, so 4 is not a(2).
a(3) =  24 = 220_3 can be changed to 212_3 = 23. 24 is not prime and no single base-3 digit change works.
a(4) =  24 = 120_4 can be changed to 113_4 = 23.
a(5) =  90 = 330_5 -> 324_5 =  89.
a(6) =  90 = 230_6 -> 225_6 =  89.
a(7) = 119 = 230_7 -> 221_7 = 113.
a(8) = 200 = 310_8 -> 307_8 = 199.
a(9) = 117 = 140_9 -> 135_9 = 113.
Often, there are alternative ways to change two digits to get alternative primes, but for each a(n), there is not any way to get a prime by changing 0 or 1 digits in base n.

Prog

(Python)
from sympy import isprime
from sympy.ntheory import digits
from itertools import combinations, count, product
def fromdigits(d, b): return sum(di*b**i for i, di in enumerate(d[::-1]))
def PEN(base, k):
    if isprime(k): return 0
    d = digits(k, base)[1:]
    for j in range(1, len(d)+1):
        for c in combinations(range(len(d)), j):
            for p in product(*[[i for i in range(base) if i!=d[c[m]]] for m in range(j)]):
                dd = d[:]
                for i in range(j): dd[c[i]] = p[i]
                if isprime(fromdigits(dd, base)): return j
def a(n): return next(k for k in count(n) if PEN(n, k) == 2)
print([a(n) for n in range(2, 32)]) # Michael S. Branicky, Feb 21 2024

Crossrefs

Cf. A133219, A186995, A322614.

Sequence in context: A005878 A128637 A280708 * A109272 A361998 A052349

Adjacent sequences: A370528 A370529 A370530 * A370532 A370533 A370534

Keyword

nonn

Author

Don N. Page, Feb 21 2024

Extensions

a(11) and beyond from Michael S. Branicky, Feb 21 2024

Status

approved