login
Minimum number of bit inversions to convert n into a prime.
2

%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