A335653 Smallest prime whose binary expansion has Hamming distance 1 from 2n+1, or 0 if no such prime exists.

3, 2, 7, 3, 11, 3, 5, 7, 19, 3, 5, 7, 17, 11, 13, 23, 37, 3, 5, 7, 43, 11, 13, 43, 17, 19, 37, 23, 41, 43, 29, 31, 67, 3, 5, 7, 89, 11, 13, 71, 17, 19, 1109, 23, 73, 83, 29, 31, 101, 67, 37, 71, 41, 43, 101, 47, 97, 83, 53, 103, 89, 59, 61, 383, 131, 3, 5, 7, 139, 11, 13, 139, 17, 19, 151, 23

Offset: 0

Author

Ross Dempsey, Jun 15 2020

Keywords

• nonn
• base
• look

Comments

If 2n+1 is a dual Sierpiński number, and if 2n+1 cannot be made prime by flipping any of the ones in its binary representation to zero, then a(n) = 0.

2131099 is Sierpiński, and it is conjectured that the Sierpiński numbers are the same as the dual Sierpiński numbers. Furthermore 2131099 is the smallest Sierpiński number whose binary representation has the property stated above. If the dual Sierpiński conjecture holds, and if A076336 is complete up to 2131099, then a(1065549) = 0 and this is likely the first 0 in the sequence.

From Robert Israel, Jul 08 2020: (Start)

Every prime is in the sequence.

Proof: Since 2 = a(1), we may assume prime p is odd. Take k so 2^k > p, and consider 2n+1 = p + 2^k. Then p has Hamming distance 1 from 2n+1. On the other hand, if q < p is prime, then q + 2^j < p + 2^k if j <= k while q + 2^j >= q + 2*2^k > p + 2^k if j > k, so q can't be at Hamming distance 1 from 2n+1. Thus p = a(n). (End)

Examples

			For n = 4, 2n+1 = 1001_2, and the smallest prime with Hamming distance 1 is 1011_2 = 11.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..2234
• MathOverflow, Hamming Distance to Primes

Crossrefs

Cf. A067760, A076336.

Programs

Maple

f:= proc(n) local L, nL, k, v;
    L:= convert(n, base, 2);
    nL:= nops(L);
    for k from nL to 1 by -1 do
      if L[k] = 1 then
        v:= n - 2^(k-1);
        if isprime(v) then return v fi;
      fi
    od;
    for k from 1 to nL do
      if L[k] = 0 then
        v:= n + 2^(k-1);
        if isprime(v) then return v fi;
      fi
    od;
    for k from nL+1 do
      v:= n+2^(k-1);
      if isprime(v) then return v fi;
    od
end proc:
map(f, [seq(i, i=1..200, 2)]); # Robert Israel, Jun 15 2020

Mathematica

a[n_Integer] := a[IntegerDigits[2 n + 1, 2]];
a[bin_List] := Module[{flips, primes},
   flips =
    Sort[FromDigits[bin,
       2] + (1 - 2 bin) Power[2, Length[bin] - Range[Length[bin]]]];
   primes = Select[flips, PrimeQ];
   If[Length[primes] >= 1, First[primes],
    a[FromDigits[bin, 2], Length[bin]]]
   ];
a[n_Integer, k_Integer] :=
  Module[{test = n + Power[2, k]}, test /; PrimeQ[test]];
a[n_Integer, k_Integer] := a[n, k + 1];
Table[a[n],{n,0,50}]

PARI

a(n) = my(p=2); while(norml2(binary(bitxor(p, 2*n+1))) != 1, p = nextprime(p+1)); p; \\ Michel Marcus, Jun 16 2020

Formula

a((p+2^k-1)/2) = p if p is an odd prime and 2^k > p-3. - Robert Israel, Jun 16 2020