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,1

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!

Links

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

Formula

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

Example

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.

Crossrefs

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

Cf. A035244, A079307, A213301 - A213321.

Sequence in context: A229499 A023313 A213301 * A219444 A134161 A168168

Adjacent sequences: A213297 A213298 A213299 * A213301 A213302 A213303

Keyword

nonn,base

Author

Hieronymus Fischer, Aug 26 2012

Status

approved