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

47, 428, 1721, 6473, 14033, 35201, 58961, 58967, 465743, 530701, 530710, 1733741, 4250788, 4723108, 4776398, 25051529, 37327196, 42450640, 42986860, 42987589, 42996409, 225463817, 382055767, 382571822, 386888308, 386888419, 387356789

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} 9^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-9 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 3-digit base-9 number has at least 1 nonprime substring. Hence, each 3(n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 9^(3n+2) 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) = 47, since 47 = 52_9 (base-9) is the greatest number with zero nonprime substrings in base-9 representation.
a(1) = 428 = 525_9 has 1 nonprime substring in base-9 representation (= 525_9). All the other base-9 substrings (2, 5, 5, 25, 52) are prime substrings. 525_9 is the greatest number with 1 nonprime substring.
a(2) = 1721 = 2322_9 has 10 substrings in base-9 representation, exactly 2 of them are nonprime substrings (22_9 and 23_3=8), and there is no greater number with 2 nonprime substrings in base-9 representation.
a(7) = 58967= 88788_9 has 15 substrings in base-9 representation, exactly 7 of them are nonprime substrings (4-times 8, 2-times 88, and 8788), and there is no greater number with 7 nonprime substrings in base-9 representation.
		

Links

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

Crossrefs

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

Cf. A035244, A079397, A213300 - A213321.

Cf. A217102 - A217109, A217112 - A217118.

Cf. A217302 - A217309.

Formula

a(n) >= A217109(n).

a(n) >= A217309(A000217(num_digits_9(a(n)))-n), where num_digits_9(x)=floor(log_9(x))+1 is the number of digits of the base-9 representation of x.

a(n) <= 9^(n+2).

a(n) <= 9^min(n+2, 6*floor((n+7)/8)).

a(n) <= 9^((3/4)*(n + 3)).

a(n+m+1) >= 9*a(n), where m := floor(log_9(a(n))) + 1.