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