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

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

Author

Hieronymus Fischer, Dec 20 2012

Keywords

• nonn
• base

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

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

Cf. A035244, A079397, A213300 - A213321.

Cf. A217102 - A217109, A217112 - A217119.

Cf. A217302 - A217309.

Formula

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