cp's OEIS Frontend

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

%I A370531 #43 Mar 24 2024 10:48:42
%S A370531 8,24,24,90,90,119,200,117,200,319,528,1131,1134,525,1328,1343,1332,
%T A370531 1330,1340,2478,7260,1334,5352,4300,5954,4833,13188,8468,10800,15686,
%U A370531 11744,19338,19618,22575,19620,15688,28234,19617,25480,31406,19614,40291,25476,31410
%N A370531 The smallest number in base n such that two digits (and no fewer) need to be changed to get a prime.
%C A370531 Any digit, including the most significant, can be changed to 0.
%C A370531 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.
%C A370531 Adding preceding 0's to be changed does not appear to change any of the entries given below.
%H A370531 Michael S. Branicky, <a href="/A370531/b370531.txt">Table of n, a(n) for n = 2..143</a>
%e A370531 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).
%e A370531 a(3) =  24 = 220_3 can be changed to 212_3 = 23. 24 is not prime and no single base-3 digit change works.
%e A370531 a(4) =  24 = 120_4 can be changed to 113_4 = 23.
%e A370531 a(5) =  90 = 330_5 -> 324_5 =  89.
%e A370531 a(6) =  90 = 230_6 -> 225_6 =  89.
%e A370531 a(7) = 119 = 230_7 -> 221_7 = 113.
%e A370531 a(8) = 200 = 310_8 -> 307_8 = 199.
%e A370531 a(9) = 117 = 140_9 -> 135_9 = 113.
%e A370531 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.
%o A370531 (Python)
%o A370531 from sympy import isprime
%o A370531 from sympy.ntheory import digits
%o A370531 from itertools import combinations, count, product
%o A370531 def fromdigits(d, b): return sum(di*b**i for i, di in enumerate(d[::-1]))
%o A370531 def PEN(base, k):
%o A370531     if isprime(k): return 0
%o A370531     d = digits(k, base)[1:]
%o A370531     for j in range(1, len(d)+1):
%o A370531         for c in combinations(range(len(d)), j):
%o A370531             for p in product(*[[i for i in range(base) if i!=d[c[m]]] for m in range(j)]):
%o A370531                 dd = d[:]
%o A370531                 for i in range(j): dd[c[i]] = p[i]
%o A370531                 if isprime(fromdigits(dd, base)): return j
%o A370531 def a(n): return next(k for k in count(n) if PEN(n, k) == 2)
%o A370531 print([a(n) for n in range(2, 32)]) # _Michael S. Branicky_, Feb 21 2024
%Y A370531 Cf. A133219, A186995, A322614.
%K A370531 nonn
%O A370531 2,1
%A A370531 _Don N. Page_, Feb 21 2024
%E A370531 a(11) and beyond from _Michael S. Branicky_, Feb 21 2024