A383271 Number of primes (excluding n) that may be generated by replacing any binary digit of n with a digit from 0 to 1.

0, 0, 1, 1, 1, 1, 2, 2, 0, 2, 2, 1, 1, 1, 0, 3, 1, 1, 2, 3, 0, 4, 1, 3, 0, 2, 0, 3, 1, 2, 1, 2, 0, 2, 1, 2, 1, 2, 0, 3, 1, 1, 1, 4, 0, 5, 1, 1, 0, 2, 0, 2, 1, 2, 0, 2, 0, 3, 1, 1, 1, 2, 0, 4, 0, 3, 2, 3, 0, 3, 1, 4, 1, 1, 0, 5, 0, 4, 1, 1, 0, 4, 1, 2, 0, 0, 0, 3, 1, 1

Offset

0,7

Comments

Also, the number of prime neighbors of n in H(A070939(n), 2), where H(k, b) is the Hamming graph whose vertices are the sequences of length k over the alphabet {0,1,...,b-1} with adjacency being defined by having Hamming distance 1 (see A145667).

Prepending 1 is not allowed.

Links

Michael S. Branicky, Table of n, a(n) for n = 0..10000

Example

a(3) = 1 since 3 = 11_2 can be changed to 10_2 = 2, which is prime.
a(5) = 1 since 5 = 101_2 can be changed to 001_2 = 1, 111_2 = 7 (prime), or 100_2 = 4.
a(6) = 2 since 6 = 110_2 can be changed to 010_2 = 2 (prime), 100_2 = 4, or 111_2 = 7 (prime).
a(7) = 2 since 7 = 111_2 can be changed to 011_2 = 3 (prime), 101_2 = 5 (prime), or 110_2 = 6.

Maple

a:= n-> nops(select(isprime, [seq(Bits[Xor](2^i, n), i=0..ilog2(n))])):
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 23 2025

Mathematica

A383271[n_] := Count[BitXor[n, 2^Range[0, BitLength[n] - 1]], _?PrimeQ];
Array[A383271, 100, 0] (* Paolo Xausa, Apr 23 2025 *)

Prog

(Python)
from gmpy2 import is_prime
def a(n):
    if n == 0:
        return 0
    if n&1 == 0:
        return int(is_prime(n + 1)) + int(1<<(n.bit_length()-1)^n == 2)
    mask, c = 1, 0
    for i in range(n.bit_length()):
        if is_prime(mask^n):
            c += 1
        mask <<= 1
    return c
print([a(n) for n in range(90)])

Crossrefs

Base-2 analog of A209252.

Cf. A070939, A145667, A352942.

Sequence in context: A035668 A307757 A215283 * A066518 A218491 A111165

Adjacent sequences: A383268 A383269 A383270 * A383272 A383273 A383274

Keyword

nonn,base

Author

Michael S. Branicky, Apr 21 2025

Status

approved