A213300 Largest number with n nonprime substrings (substrings with leading zeros are considered to be nonprime).

373, 3797, 37337, 73373, 373379, 831373, 3733797, 3733739, 8313733, 9973331, 37337397, 82337397, 99733313, 99733317, 99793373, 733133733, 831373379, 997333137, 997337397, 997933739, 7331337337, 8313733797, 9733733797, 9973331373, 9979337397, 9982337397

Offset: 0

Author

Hieronymus Fischer, Aug 26 2012

Keywords

• nonn
• base

Comments

The sequence is well-defined in that for each n the set of numbers with n nonprime substrings is nonempty and finite. Proof of existence: Define m(n):=2*sum_{j=i..k} 10^j, where k:=floor((sqrt(8n+1)-1)/2), i:= n - k(k+1)/2. For n=0,1,2,3,... the m(n) 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 existence. Proof of finiteness: Each 4-digit number has at least 1 nonprime substring. Hence each 4*(n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 10^(4n+3) such that all numbers > b have more than n nonprime substrings. It follows that the set of numbers with n nonprime substrings is finite.

The following statements hold true:

For all n>=0 there are minimal numbers with n nonprime substrings (cf. A213302 - A213304).

For all n>=0 there are maximal numbers with n nonprime substrings (= A213300 = this sequence).

For all n>=0 there are minimal numbers with n prime substrings (cf. A035244).

The greatest number with n prime substrings does not exist. Proof: If p is a number with n prime substrings, than 10*p is a greater number with n prime substrings.

Comment from N. J. A. Sloane, Sep 01 2012: it is a surprise that any number greater than 373 has a nonprime substring!

Examples

			a(0)=373, since 373 is the greatest number such that all substrings are primes, hence it is the maximal number with 0 nonprime substrings.
a(1)=3797, since the only nonprime substring of 3797 is 9 and all greater numbers have more than 1 nonprime substrings.
a(2)=37337, since the nonprime substrings of 37337 are 33 and 7337 and all greater numbers have > 2 nonprime substrings.
		

Links

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

Crossrefs

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

Cf. A035244, A079307, A213301 - A213321.

Formula

a(n) >= A035244(A000217(A055642(a(n)))-n).