login
A335653
Smallest prime whose binary expansion has Hamming distance 1 from 2n+1, or 0 if no such prime exists.
1
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)
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
Sequence in context: A276466 A289336 A324509 * A296512 A241558 A295422
KEYWORD
nonn,base,look
AUTHOR
Ross Dempsey, Jun 15 2020
STATUS
approved