login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A305445 Minimum number of bit inversions to convert n into a prime. 2
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,7

COMMENTS

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.

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.

The least n for which a(n) = 4 is n = 45812984490. - Giovanni Resta, Jan 03 2019

LINKS

Robert Israel, Table of n, a(n) for n = 2..10000

Programing Puzzles & Code Golf Stack Exchange, Toggle some bits and get a square

EXAMPLE

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).)

MAPLE

f:= proc(n) local m, d, x;

  if isprime(n) then return 0 fi;

  m:= ilog2(n);

  for d from 1 do

    for x in combinat:-choose([$0..m], d) do

      if isprime(Bits:-Xor(n, add(2^i, i=x))) then return d fi

  od od

end proc:

map(f, [$2..200]); # Robert Israel, Aug 20 2018

PROG

(PARI) {a(n) = my(b, L, N, s, v); if(n < 2, ,

if(isprime(n), 0, b = binary(n); L = #b; for(j = 1, L, v = vector(j, Y, [1, L]);

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))))}

CROSSREFS

Sequence in context: A079690 A328620 A257510 * A225721 A040076 A019269

Adjacent sequences:  A305442 A305443 A305444 * A305446 A305447 A305448

KEYWORD

nonn,base

AUTHOR

Rick L. Shepherd, Aug 12 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 15 18:26 EDT 2021. Contains 343920 sequences. (Running on oeis4.)