|
%I #46 Jan 04 2019 03:26:51
%S 0,0,1,0,1,0,2,1,1,0,1,0,2,1,1,0,1,0,2,1,1,0,2,1,2,1,1,0,1,0,2,1,1,1,
%T 1,0,2,1,1,0,1,0,2,1,1,0,2,1,2,1,1,0,2,1,2,1,1,0,1,0,2,1,2,1,1,0,2,1,
%U 1,0,1,0,2,1,2,1,1,0,2,1,1,0,3,2,2,1,1,0,2,1,2,1,2,1,1,0,2,1,1,0,1,0,2,1,1
%N Minimum number of bit inversions to convert n into a prime.
%C If n is already a prime, a(n) is defined to be 0. Every original bit of n's binary representation is allowed to be inverted, but no leading 0 bits may be. Every n > 1 is either a prime or can be converted to a prime by bit inversions (guaranteed because, say, 0...010 is the prime 2). The maximum value of the first 10^7 terms is 3.
%C This sequence was inspired by the linked "code golf" problem, which converts n to a square but (unlike this sequence) disallows inverting n's most significant bit.
%C The least n for which a(n) = 4 is n = 45812984490. - _Giovanni Resta_, Jan 03 2019
%H Robert Israel, <a href="/A305445/b305445.txt">Table of n, a(n) for n = 2..10000</a>
%H Programing Puzzles & Code Golf Stack Exchange, <a href="https://codegolf.stackexchange.com/questions/170281/toggle-some-bits-and-get-a-square">Toggle some bits and get a square</a>
%e For n = 8, the binary representation 1000 cannot be turned into a prime with only one bit inversion, but 0010, where both the first and third bits from the left are inverted, is the prime 2, so a(8) = 2. (There are other primes possible with two inversions in this case: 1011 (11 decimal) and 1101 (13 decimal).)
%p f:= proc(n) local m,d,x;
%p if isprime(n) then return 0 fi;
%p m:= ilog2(n);
%p for d from 1 do
%p for x in combinat:-choose([$0..m],d) do
%p if isprime(Bits:-Xor(n, add(2^i,i=x))) then return d fi
%p od od
%p end proc:
%p map(f, [$2..200]); # _Robert Israel_, Aug 20 2018
%o (PARI) {a(n) = my(b, L, N, s, v); if(n < 2, ,
%o if(isprime(n), 0, b = binary(n); L = #b; for(j = 1, L, v = vector(j, Y, [1, L]);
%o forvec(X = v, N = n + sum(k = 1, j, if(b[X[k]], s = -1, s = 1); s*2^(L - X[k])); if(isprime(N), return(j)), 2))))}
%K nonn,base
%O 2,7
%A _Rick L. Shepherd_, Aug 12 2018
|
