A352942 Let p = prime(n); a(n) = number of primes q with same number of binary digits as p that can be obtained from p by changing one binary digit.

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

Offset: 1

Author

Michael S. Branicky, May 11 2022

Keywords

• nonn
• base

Comments

a(n) is also the degree of prime(n) in the graph P(A070939(prime(n)), 2), defined in A145667.

Examples

			prime(1) = 2, in binary 10, has one neighbor 11 in P(2, 2), so a(1) = 1.
prime(14) = 43, in binary 101011, has neighbors 101001 (41), 101111 (47), 111011 (59), so a(14) = 3.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000

Crossrefs

Binary analog of A125002.

Cf. A000040, A004676, A070939, A104080, A014234, A137985, A145667, A353738.

Programs

Maple

a:= n-> (p-> nops(select(isprime, {seq(Bits[Xor]
        (p, 2^i), i=0..ilog2(p)-1)})))(ithprime(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, May 11 2022

Mathematica

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

Python

from sympy import isprime, sieve
def neighs(s):
    digs = "01"
    ham1 = (s[:i]+d+s[i+1:] for i in range(len(s)) for d in digs if d!=s[i])
    yield from (h for h in ham1 if h[0] != '0')
def a(n):
    return sum(1 for s in neighs(bin(sieve[n])[2:]) if isprime(int(s, 2)))
print([a(n) for n in range(1, 88)])

Formula

a(n) = deg(prime(n)) in P(A070939(prime(n)), 2) (see A145667).