cp's OEIS Frontend

A322743 Least composite such that complementing one bit in its binary representation at a time produces exactly n primes.

%I A322743 #52 Apr 25 2025 17:46:18
%S A322743 8,4,6,15,21,45,111,261,1605,1995,4935,8295,69825,268155,550725,
%T A322743 4574955,13996605,12024855,39867135,398467245,1698754365,16351800465,
%U A322743 72026408685,120554434875
%N A322743 Least composite such that complementing one bit in its binary representation at a time produces exactly n primes.
%F A322743 From _Chai Wah Wu_, Jan 03 2019: (Start)
%F A322743 a(n) >= 2^n+1, if it exists. a(n) is odd for n > 2, if it exists.
%F A322743 It is clear these are true for n <= 2. Suppose n > 2. If a(n) is even, then complementing any bits that is not LSB or MSB will result in an even nonprime number. If a(n) is odd, then complementing the LSB will result in an even nonprime number. So either case shows that a(n) has n+1 or more binary bits. It also shows that a(n) must be odd.
%F A322743 Conjecture: a(n) mod 10 == 5 for n > 7. (End)
%F A322743 a(24) <= 794688308295. - _Michael S. Branicky_, Apr 25 2025
%e A322743 a(1) = 4 because 4 in base 2 is 100 and 000 is 0, 110 is 6 and 101 is 5: hence only one prime.
%e A322743 a(2) = 6 because 6 in base 2 is 110 and 010 is 2, 100 is 4 and 111 is 7: hence two primes.
%p A322743 a:= proc(n) local k; for k from 2^n+1 while isprime(k) or n<>add(
%p A322743       `if`(isprime(Bits[Xor](k, 2^j)), 1, 0), j=0..ilog2(k)) do od; k
%p A322743     end:
%p A322743 seq(a(n), n=0..12);  # _Alois P. Heinz_, Jan 03 2019
%o A322743 (Python)
%o A322743 from sympy import isprime
%o A322743 def A322743(n):
%o A322743     i = 4 if n <= 1 else 2**n+1
%o A322743     j = 1 if n <= 2 else 2
%o A322743     while True:
%o A322743         if not isprime(i):
%o A322743             c = 0
%o A322743             for m in range(len(bin(i))-2):
%o A322743                 if isprime(i^(2**m)):
%o A322743                     c += 1
%o A322743                 if c > n:
%o A322743                     break
%o A322743             if c == n:
%o A322743                 return i
%o A322743         i += j # _Chai Wah Wu_, Jan 03 2019
%Y A322743 Cf. A002808, A137985.
%K A322743 nonn,base
%O A322743 0,1
%A A322743 _Paolo P. Lava_, Dec 24 2018
%E A322743 Definition clarified by _Chai Wah Wu_, Jan 03 2019
%E A322743 a(19) added and a(0) corrected by _Rémy Sigrist_, Jan 03 2019
%E A322743 a(20)-a(23) from _Giovanni Resta_, Jan 03 2019