cp's OEIS Frontend

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

%I A335653 #33 Jan 22 2022 23:41:59
%S A335653 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,
%T A335653 23,41,43,29,31,67,3,5,7,89,11,13,71,17,19,1109,23,73,83,29,31,101,67,
%U A335653 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
%N A335653 Smallest prime whose binary expansion has Hamming distance 1 from 2n+1, or 0 if no such prime exists.
%C A335653 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.
%C A335653 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.
%C A335653 From _Robert Israel_, Jul 08 2020: (Start)
%C A335653 Every prime is in the sequence.
%C A335653   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)
%H A335653 Robert Israel, <a href="/A335653/b335653.txt">Table of n, a(n) for n = 0..2234</a>
%H A335653 MathOverflow, <a href="https://mathoverflow.net/questions/363083/hamming-distance-to-primes/">Hamming Distance to Primes</a>
%F A335653 a((p+2^k-1)/2) = p if p is an odd prime and 2^k > p-3. - _Robert Israel_, Jun 16 2020
%e A335653 For n = 4, 2n+1 = 1001_2, and the smallest prime with Hamming distance 1 is 1011_2 = 11.
%p A335653 f:= proc(n) local L, nL, k, v;
%p A335653     L:= convert(n, base, 2);
%p A335653     nL:= nops(L);
%p A335653     for k from nL to 1 by -1 do
%p A335653       if L[k] = 1 then
%p A335653         v:= n - 2^(k-1);
%p A335653         if isprime(v) then return v fi;
%p A335653       fi
%p A335653     od;
%p A335653     for k from 1 to nL do
%p A335653       if L[k] = 0 then
%p A335653         v:= n + 2^(k-1);
%p A335653         if isprime(v) then return v fi;
%p A335653       fi
%p A335653     od;
%p A335653     for k from nL+1 do
%p A335653       v:= n+2^(k-1);
%p A335653       if isprime(v) then return v fi;
%p A335653     od
%p A335653 end proc:
%p A335653 map(f, [seq(i, i=1..200, 2)]); # _Robert Israel_, Jun 15 2020
%t A335653 a[n_Integer] := a[IntegerDigits[2 n + 1, 2]];
%t A335653 a[bin_List] := Module[{flips, primes},
%t A335653    flips =
%t A335653     Sort[FromDigits[bin,
%t A335653        2] + (1 - 2 bin) Power[2, Length[bin] - Range[Length[bin]]]];
%t A335653    primes = Select[flips, PrimeQ];
%t A335653    If[Length[primes] >= 1, First[primes],
%t A335653     a[FromDigits[bin, 2], Length[bin]]]
%t A335653    ];
%t A335653 a[n_Integer, k_Integer] :=
%t A335653   Module[{test = n + Power[2, k]}, test /; PrimeQ[test]];
%t A335653 a[n_Integer, k_Integer] := a[n, k + 1];
%t A335653 Table[a[n],{n,0,50}]
%o A335653 (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
%Y A335653 Cf. A067760, A076336.
%K A335653 nonn,base,look
%O A335653 0,1
%A A335653 _Ross Dempsey_, Jun 15 2020