%I #18 Dec 13 2015 23:04:36
%S 373,3797,37337,73373,373379,831373,3733797,3733739,8313733,9973331,
%T 37337397,82337397,99733313,99733317,99793373,733133733,831373379,
%U 997333137,997337397,997933739,7331337337,8313733797,9733733797,9973331373,9979337397,9982337397
%N Largest number with n nonprime substrings (substrings with leading zeros are considered to be nonprime).
%C 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.
%C The following statements hold true:
%C For all n>=0 there are minimal numbers with n nonprime substrings (cf. A213302 - A213304).
%C For all n>=0 there are maximal numbers with n nonprime substrings (= A213300 = this sequence).
%C For all n>=0 there are minimal numbers with n prime substrings (cf. A035244).
%C 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.
%C Comment from _N. J. A. Sloane_, Sep 01 2012: it is a surprise that any number greater than 373 has a nonprime substring!
%H Hieronymus Fischer, <a href="/A213300/b213300.txt">Table of n, a(n) for n = 0..32</a>
%F a(n) >= A035244(A000217(A055642(a(n)))-n).
%e 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.
%e a(1)=3797, since the only nonprime substring of 3797 is 9 and all greater numbers have more than 1 nonprime substrings.
%e a(2)=37337, since the nonprime substrings of 37337 are 33 and 7337 and all greater numbers have > 2 nonprime substrings.
%Y Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.
%Y Cf. A035244, A079307, A213301 - A213321.
%K nonn,base
%O 0,1
%A _Hieronymus Fischer_, Aug 26 2012
|