login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A217112 Greatest number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime). 9
1, 3, 7, 6, 15, 14, 31, 29, 30, 63, 61, 62, 127, 54, 125, 126, 255, 117, 251, 254, 189, 511, 479, 509, 510, 379, 502, 1023, 1021, 1007, 1022, 958, 1018, 1014, 2047, 2045, 1791, 2046, 2042, 2027, 2037, 4091, 4095, 4063, 3069, 4094, 4090, 4085, 8159, 8187, 8191, 8189, 8127 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

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.

LINKS

Hieronymus Fischer, Table of n, a(n) for n = 1..1000

FORMULA

a(n) >= A217102(n).

a(n) >= A217302(A000217(A070939(a(n)))-n).

Example: a(9)=30=11110_2, A000217(A070939(31))=15, hence, a(9)>=A217302(15-9)=27.

a(n) <= 2^n.

a(n) <= 2^min(6 + n/6, 20*floor((n+125)/126)).

a(n) <= 64*2^(n/6).

With m := floor(log_2(a(n))) + 1:

a(n+m+1) >= 2*a(n), if a(n) is even.

a(n+m) >= 2*a(n), if a(n) is odd.

EXAMPLE

(1) = 1, since 1 = 1_2 (binary) is the greatest number with 1 nonprime substring.

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.

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.

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.

CROSSREFS

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.

Cf. A035244, A079397, A213300 - A213321.

Cf. A217102 - A217109, A217113 - A217119.

Cf. A217302 - A217309.

Sequence in context: A175142 A318466 A324819 * A241016 A245602 A060924

Adjacent sequences:  A217109 A217110 A217111 * A217113 A217114 A217115

KEYWORD

nonn,base

AUTHOR

Hieronymus Fischer, Dec 20 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 00:40 EST 2020. Contains 331030 sequences. (Running on oeis4.)