|
%I #42 Aug 07 2023 05:40:31
%S 6,7,11,15,35,39,63,135,255,999,2175,8223,16383,57735,131075,131079,
%T 262143,524295,1048575,536870919,1073735679,2147483655,4294967295,
%U 17179770879,4260641103903,4611686018427387903,4720069647059686260735,1237940039285380274899124223
%N Dropping any binary digit gives a prime number.
%C 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.
%C From _Robert Israel_, Jan 14 2016: (Start)
%C For n >= 2, a(n) == 3 (mod 4).
%C 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.
%C 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).
%C (End)
%C a(25) > 2^38. - _Giovanni Resta_, Apr 10 2016
%C For n > 1, a(n) = 2p+1 for some prime p. - _Chai Wah Wu_, Aug 27 2021
%C From _Bert Dobbelaere_, Aug 07 2023: (Start)
%C 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.
%C (End)
%e Decimal and binary forms of the known terms:
%e 1 6 110
%e 2 7 111
%e 3 11 1011
%e 4 15 1111
%e 5 35 100011
%e 6 39 100111
%e 7 63 111111
%e 8 135 10000111
%e 9 255 11111111
%e 10 999 1111100111
%e 11 2175 100001111111
%e 12 8223 10000000011111
%e 13 16383 11111111111111
%e 14 57735 1110000110000111 <--- (a binary palindrome
%e 15 131075 100000000000000011 with 5 digit runs)
%e 16 131079 100000000000000111
%e 17 262143 111111111111111111
%e 18 524295 10000000000000000111
%e 19 1048575 11111111111111111111
%e 20 536870919 100000000000000000000000000111
%e 21 1073735679 111111111111111110011111111111
%e 22 2147483655 10000000000000000000000000000111
%e 23 4294967295 11111111111111111111111111111111
%e 24 17179770879 1111111111111111100111111111111111
%p filter:= proc(n) local B,k,y;
%p if not isprime(floor(n/2)) then return false fi;
%p B:= convert(n,base,2);
%p for k from 2 to nops(B) do
%p if B[k] <> B[k-1] then
%p y:= n mod 2^(k-1);
%p if not isprime((y+n-B[k]*2^(k-1))/2) then return false fi
%p fi
%p od;
%p true
%p end proc:
%p select(filter, [6, seq(i,i=7..10^6,4)]); # _Robert Israel_, Jan 14 2016
%t 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 *)
%o (PARI) DroppingAnyDigitGivesAPrime(N,b) = {
%o \\ Property-testing function; returns 1 if true for N, 0 otherwise
%o \\ Works with any base b. Here used with b=2.
%o my(k=b,m); if(N<b,return(0));
%o while(N>=(k\b), m=(N\k)*(k\b)+(N%(k\b));
%o if ((m<2)||(!isprime(m)),return(0)); k*=b);
%o return(1);
%o }
%o (Python)
%o from sympy import isprime
%o def ok(n):
%o if n < 7 or n%4 != 3: return n == 6
%o b = bin(n)[2:]
%o return all(isprime(int(b[:i]+b[i+1:], 2)) for i in range(len(b)))
%o print(list(filter(ok, range(2, 2**20)))) # _Michael S. Branicky_, Jun 07 2021
%Y Cf. A000668, A001359, A005811, A019434, A034895 (base 10), A051362, A057733, A104066.
%K nonn,base,more,hard
%O 1,1
%A _Stanislav Sykora_, Jan 14 2016
%E a(24) from _Giovanni Resta_, Apr 10 2016
%E a(25)-a(28) from _Bert Dobbelaere_, Aug 07 2023
| 