A267413 Dropping any binary digit gives a prime number.

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

Author

Stanislav Sykora, Jan 14 2016

Keywords

• nonn
• base
• more
• hard

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)

Examples

			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
		

Crossrefs

Cf. A000668, A001359, A005811, A019434, A034895 (base 10), A051362, A057733, A104066.

Programs

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

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=(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

Extensions

a(24) from Giovanni Resta, Apr 10 2016

a(25)-a(28) from Bert Dobbelaere, Aug 07 2023