cp's OEIS Frontend

A217112 Greatest number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).

%I A217112 #5 Dec 29 2012 13:07:16
%S A217112 1,3,7,6,15,14,31,29,30,63,61,62,127,54,125,126,255,117,251,254,189,
%T A217112 511,479,509,510,379,502,1023,1021,1007,1022,958,1018,1014,2047,2045,
%U A217112 1791,2046,2042,2027,2037,4091,4095,4063,3069,4094,4090,4085,8159,8187,8191,8189,8127
%N A217112 Greatest number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).
%C A217112 There are no numbers with zero nonprime substrings in binary representation. For all bases > 2 there is always a number (=2) with zero nonprime substrings.
%C A217112 The set of numbers with n nonprime substrings is finite. Proof: Evidently, each 1-digit binary number represents 1 nonprime substring. Hence, each (n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 2^n, such that all numbers > b have more than n nonprime substrings.
%H A217112 Hieronymus Fischer, <a href="/A217112/b217112.txt">Table of n, a(n) for n = 1..1000</a>
%F A217112 a(n) >= A217102(n).
%F A217112 a(n) >= A217302(A000217(A070939(a(n)))-n).
%F A217112 Example: a(9)=30=11110_2, A000217(A070939(31))=15, hence, a(9)>=A217302(15-9)=27.
%F A217112 a(n) <= 2^n.
%F A217112 a(n) <= 2^min(6 + n/6, 20*floor((n+125)/126)).
%F A217112 a(n) <= 64*2^(n/6).
%F A217112 With m := floor(log_2(a(n))) + 1:
%F A217112 a(n+m+1) >= 2*a(n), if a(n) is even.
%F A217112 a(n+m) >= 2*a(n), if a(n) is odd.
%e A217112 (1) = 1, since 1 = 1_2 (binary) is the greatest number with 1 nonprime substring.
%e A217112 a(2) = 3 = 11_2 has 3 substrings in binary representation (1, 1 and 11), two of them are nonprime substrings (1 and 1), and 11_2 = 3 is the only prime substrings. 3 is the greatest number with 2 nonprime substrings.
%e A217112 a(8) = 29 = 11101_2 has 15 substrings in binary representation (0, 1, 1, 1, 1, 11, 11, 10, 01, 111, 110, 101, 1110, 1101, 11101), exactly 8 of them are nonprime substrings (0, 1, 1, 1, 1, 01, 110, 1110). There is no greater number with 8 nonprime substrings in binary representation.
%e A217112 a(14) = 54 = 110110_2 has 21 substrings in binary representation, only 7 of them are prime substrings (10, 10, 11, 11, 101, 1011, 1101), which implies that exactly 14 substrings must be nonprime. There is no greater number with 14 nonprime substrings in binary representation.
%Y A217112 Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.
%Y A217112 Cf. A035244, A079397, A213300 - A213321.
%Y A217112 Cf. A217102 - A217109, A217113 - A217119.
%Y A217112 Cf. A217302 - A217309.
%K A217112 nonn,base
%O A217112 1,2
%A A217112 _Hieronymus Fischer_, Dec 20 2012