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,1

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)

Links

Robert Israel, Table of n, a(n) for n = 0..2234

MathOverflow, Hamming Distance to Primes

Formula

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

Example

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

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}]

Prog

(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

Crossrefs

Cf. A067760, A076336.

Sequence in context: A276466 A289336 A324509 * A296512 A241558 A295422

Adjacent sequences: A335650 A335651 A335652 * A335654 A335655 A335656

Keyword

nonn,base,look

Author

Ross Dempsey, Jun 15 2020

Status

approved