A217103 -id:A217103 - cp's OEIS frontend

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

1, 2, 7, 5, 4, 11, 10, 12, 8, 22, 21, 19, 17, 16, 60, 39, 37, 34, 36, 32, 83, 71, 74, 69, 67, 66, 64, 143, 139, 141, 135, 134, 131, 130, 128, 283, 271, 269, 263, 267, 262, 261, 257, 256, 541, 539, 527, 526, 523, 533, 519, 514, 516, 512, 1055, 1053, 1047, 1067

Offset: 1

Hieronymus Fischer, Dec 12 2012

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 (Cf. A217103-A217109, A213302).

If p is a number with k prime substrings and d digits (in binary representation), p even, m>=d, than b := p*2^(m-d) has m*(m+1)/2 - k nonprime substrings, and a(A000217(n)-k) <= b.

			a(1) = 1, since 1 = 1_2 is the least number with 1 nonprime substring in binary representation.
a(2) = 2, since 2 = 10_2 is the least number with 2 nonprime substrings in binary representation (0 and 1).
a(3) = 7, since 7 = 111_2 is the least number with 3 nonprime substrings in binary representation (3-times 1, the prime substrings are 2-times 11 and 111).
a(10) = 22, since 22 = 10110_2 is the least number with 10 nonprime substrings in binary representation, these are 0, 0, 1, 1, 1, 01, 011, 110, 0110 and 10110 (remember, that substrings with leading zeros are considered to be nonprime).

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

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685, A035244, A079397, A213300-A213321, A217103-A217109, A217302-A217309.

a(n) >= 2^floor((sqrt(8*n-7)-1)/2) for n>=1, equality holds if n=1 or n+1 is a triangular number (cf. A000217).
a(n) >= 2^floor((sqrt(8*n+1)-1)/2) for n>1, equality holds if n+1 is a triangular number.
a(A000217(n)-1) = 2^(n-1), n>1.
a(A000217(n)-k) >= 2^(n-1) + k-1, 1<=k<=n, n>1.
a(A000217(n)-k) = 2^(n-1) + p, where p is the minimal number >= 0 such that 2^(n-1) + p, has k prime substrings in binary representation, 1<=k<=n, n>1.

A217113 Greatest number (in decimal representation) with n nonprime substrings in base-3 representation (substrings with leading zeros are considered to be nonprime).

Original entry on oeis.org

2, 23, 71, 26, 77, 233, 239, 719, 701, 647, 725, 2159, 2177, 2158, 2157, 5822, 5741, 6551, 6476, 6532, 6531, 18944, 19436, 19655, 19601, 19673, 19653, 58310, 58309, 58316, 58967, 59021, 58964, 157211, 157217, 174950, 176408, 176407, 176903, 177065, 177064, 471653, 511511

Offset: 0

Hieronymus Fischer, Dec 20 2012

The sequence is well-defined in that for each n the set of numbers with n nonprime substrings is not empty and finite. Proof of existence: Define m(n):=2*sum_{j=i..k} 3^j, where k:=floor((sqrt(8n+1)-1)/2), i:= n-(k(k+1)/2). For n=0,1,2,3,... the m(n) in base-3 representation are 2, 22, 20, 222, 220, 200, 2222, 2220, 2200, 2000, 22222, 22220, .... m(n) has k+1 digits and (k-i+1) 2’s. Thus, the number of nonprime substrings of m(n) is ((k+1)(k+2)/2)-k-1+i=(k(k+1)/2)+i=n. This proves the statement of existence. Proof of finiteness: Each 2-digit base-3 number has at least 1 nonprime substring. Hence, each 2(n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 3^(2n+1) such that all numbers > b have more than n nonprime substrings. It follows, that the set of numbers with n nonprime substrings is finite.

			a(0) = 2, since 2 = 2_3 (base-3) is the greatest number with zero nonprime substrings in base-3 representation.
a(1) = 23 = 212_3 has 1 substring in base-3 representation (= 1). All the other base-3 substrings (2, 2, 21, 12, 212) are prime substrings. 23 is the greatest number with 1 nonprime substring.
a(2) = 71 = 2122_3 has 10 substrings in base-3 representation (1, 2, 2, 2, 12, 21, 22, 122, 212, 2122), exactly 2 of them are nonprime substrings (1 and 22_3=8), and there is no greater number with 2 nonprime substrings in base-3 representation.
a(3) = 26 = 222_3 has 6 substrings in base-3 representation, only 3 of them are prime substrings (2, 2, 2) which implies that exactly 3 substrings must be nonprime, and there is no greater number with 3 nonprime substrings in base-3 representation.

Hieronymus Fischer, Table of n, a(n) for n = 0..250

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.
Cf. A035244, A079397, A213300 - A213321.
Cf. A217102 - A217109, A217112 - A217119.
Cf. A217302 - A217309.

a(n) >= A217103(n).
a(n) >= A217303(A000217(A081604(a(n)))-n).
Example: a(12)=2177=2222122_3, A000217(A081604(2177))=28, hence a(12)>=A217303(28-12)=1934.
a(n) <= 3^min(n + 2, 5*floor((n+4)/5)).
a(n) <= 3^(n + 2).
a(n) <= 3^min((n + 11)/3, 11*floor((n+32)/33)).
a(n) <= 3^((1/3)*(n + 11)).
With m := floor(log_3(a(n))) + 1:
a(n+m+1) >= 3*a(n), if a(n)!=1 (mod 3).
a(n+m) >= 3*a(n), if a(n)=1 (mod 3).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula