login
A267413
Dropping any binary digit gives a prime number.
1
6, 7, 11, 15, 35, 39, 63, 135, 255, 999, 2175, 8223, 16383, 57735, 131075, 131079, 262143, 524295, 1048575, 536870919, 1073735679, 2147483655, 4294967295, 17179770879, 4260641103903, 4611686018427387903, 4720069647059686260735, 1237940039285380274899124223
OFFSET
1,1
COMMENTS
This is the binary analog of A034895. The sequence contains mostly numbers with very few binary digit runs (BDR, A005811). Those with one BDR are of the type 2^k-1, such that 2^(k-1)-1 is a Mersenne prime (A000668). Vice versa, if M is any Mersenne prime, then 2*M+1 is a term. The number 6 is the only term with an even number of BDRs. There are many terms with 3 BDRs. The first term with 5 BDRs is 57735. The next terms with at least 5 BDRs (if they exist at all) are larger than 10^10. So far, I could test that a(24) > 10^10.
From Robert Israel, Jan 14 2016: (Start)
For n >= 2, a(n) == 3 (mod 4).
2^k+3 is in the sequence if 2^(k-1)+1 and 2^(k-1)+3 are primes, i.e., 2^(k-1)+1 is in the intersection of A019434 and A001359. The only known terms of the sequence in this class are 7, 11, 35, 131075.
2^k+7 is in the sequence if 2^(k-1)+3 and 2^(k-1)+7 are primes: thus 2^(k-1)+3 is in A057733 and 2^(k-1)+7 is in A104066. Terms of the sequence in this class include 15, 39, 135, 131079, 524295, 536870919, 2147483655 (but no more for k <= 2000).
(End)
a(25) > 2^38. - Giovanni Resta, Apr 10 2016
For n > 1, a(n) = 2p+1 for some prime p. - Chai Wah Wu, Aug 27 2021
From Bert Dobbelaere, Aug 07 2023: (Start)
There are no more terms with an odd number of binary digits: from any number having an odd number of binary digits, one can always drop a digit and obtain a multiple of 3. Numbers of the form 2^k+3 (k even and k > 2) cannot be terms because 2^(k-1)+1 is a multiple of 3.
(End)
EXAMPLE
Decimal and binary forms of the known terms:
1 6 110
2 7 111
3 11 1011
4 15 1111
5 35 100011
6 39 100111
7 63 111111
8 135 10000111
9 255 11111111
10 999 1111100111
11 2175 100001111111
12 8223 10000000011111
13 16383 11111111111111
14 57735 1110000110000111 <--- (a binary palindrome
15 131075 100000000000000011 with 5 digit runs)
16 131079 100000000000000111
17 262143 111111111111111111
18 524295 10000000000000000111
19 1048575 11111111111111111111
20 536870919 100000000000000000000000000111
21 1073735679 111111111111111110011111111111
22 2147483655 10000000000000000000000000000111
23 4294967295 11111111111111111111111111111111
24 17179770879 1111111111111111100111111111111111
MAPLE
filter:= proc(n) local B, k, y;
if not isprime(floor(n/2)) then return false fi;
B:= convert(n, base, 2);
for k from 2 to nops(B) do
if B[k] <> B[k-1] then
y:= n mod 2^(k-1);
if not isprime((y+n-B[k]*2^(k-1))/2) then return false fi
fi
od;
true
end proc:
select(filter, [6, seq(i, i=7..10^6, 4)]); # Robert Israel, Jan 14 2016
MATHEMATICA
Select[Range[2^20], AllTrue[Function[w, Map[FromDigits[#, 2] &@ Drop[w, {#}] &, Range@ Length@ w]]@ IntegerDigits[#, 2], PrimeQ] &] (* Michael De Vlieger, Jan 16 2016, Version 10 *)
PROG
(PARI) DroppingAnyDigitGivesAPrime(N, b) = {
\\ Property-testing function; returns 1 if true for N, 0 otherwise
\\ Works with any base b. Here used with b=2.
my(k=b, m); if(N<b, return(0));
while(N>=(k\b), m=(N\k)*(k\b)+(N%(k\b));
if ((m<2)||(!isprime(m)), return(0)); k*=b);
return(1);
}
(Python)
from sympy import isprime
def ok(n):
if n < 7 or n%4 != 3: return n == 6
b = bin(n)[2:]
return all(isprime(int(b[:i]+b[i+1:], 2)) for i in range(len(b)))
print(list(filter(ok, range(2, 2**20)))) # Michael S. Branicky, Jun 07 2021
CROSSREFS
KEYWORD
nonn,base,more,hard
AUTHOR
Stanislav Sykora, Jan 14 2016
EXTENSIONS
a(24) from Giovanni Resta, Apr 10 2016
a(25)-a(28) from Bert Dobbelaere, Aug 07 2023
STATUS
approved