|
| |
|
|
A322743
|
|
Least composite such that complementing one bit in its binary representation at a time produces exactly n primes.
|
|
1
|
|
|
|
8, 4, 6, 15, 21, 45, 111, 261, 1605, 1995, 4935, 8295, 69825, 268155, 550725, 4574955, 13996605, 12024855, 39867135, 398467245, 1698754365, 16351800465, 72026408685, 120554434875
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) >= 2^n+1, if it exists. a(n) is odd for n > 2, if it exists.
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.
Conjecture: a(n) mod 10 == 5 for n > 7. (End)
|
|
|
EXAMPLE
|
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.
a(2) = 6 because 6 in base 2 is 110 and 010 is 2, 100 is 4 and 111 is 7: hence two primes.
|
|
|
MAPLE
|
a:= proc(n) local k; for k from 2^n+1 while isprime(k) or n<>add(
`if`(isprime(Bits[Xor](k, 2^j)), 1, 0), j=0..ilog2(k)) do od; k
end:
|
|
|
PROG
|
(Python)
from sympy import isprime
i = 4 if n <= 1 else 2**n+1
j = 1 if n <= 2 else 2
while True:
if not isprime(i):
c = 0
for m in range(len(bin(i))-2):
if isprime(i^(2**m)):
c += 1
if c > n:
break
if c == n:
return i
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
