login
A217115
Greatest number (in decimal representation) with n nonprime substrings in base-5 representation (substrings with leading zeros are considered to be nonprime).
1
67, 88, 442, 567, 2213, 2837, 3067, 11068, 14713, 15337, 15338, 57943, 73568, 77213, 76697, 289717, 280338, 370443, 386068, 386587, 389713, 1852217, 1524067, 1898442, 1930342, 1932943, 1948568, 7242943, 9261088, 9664717, 9586567, 9654712, 9710942, 9742849, 46305443
OFFSET
0,1
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} 5^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-5 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 4-digit base-5 number has at least 2 nonprime substrings. Hence, each m := 4*floor((n+2)/2)-digit number has at least 2*(m/4) = 2*floor((n+2)/2) >= n+1 nonprime substrings. Consequently, there is a boundary b < 5^(m-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.
LINKS
Hieronymus Fischer, Table of n, a(n) for n = 0..70
FORMULA
a(n) >= A217105(n).
a(n) >= A217305(A000217(A110592(a(n)))-n).
a(n) <= 5^(n+3).
a(n) <= 5^(4*floor(n/2)), n>1.
a(n) <= 5^min((n + 6)/2, 9*floor((n+20)/21)).
a(n) <= 125*5^(n/2).
With m := floor(log_5(a(n))) + 1:
a(n+m+1) >= 5*a(n), if a(n)!=1 (mod 5).
a(n+m) >= 5*a(n), if a(n)=1 (mod 5).
EXAMPLE
a(0) = 67, since 67 = 232_5 (base-5) is the greatest number with zero nonprime substrings in base-5 representation.
a(1) = 88 = 323_5 has 6 substrings in base-5 representation (2, 2, 3, 23, 32, 323), the only nonprime substring is 323_5. 88 is the greatest number with 1 nonprime substring.
a(2) = 442 = 3232_5 has 10 substrings in base-5 representation (2, 2, 3, 3, 23, 32, 32, 232, 323 and 3232), exactly 2 of them are nonprime substrings (323_5=88 and 3232_5=442), and there is no greater number with 2 nonprime substrings in base-5 representation.
a(5) = 2837 = 42322_5 has 5 nonprime substrings in base-5 representation, these are 4, 22, 42, 322 and 4232, all the other substrings are prime. There is no greater number with 5 nonprime substrings in base-5 representation.
KEYWORD
nonn,base
AUTHOR
Hieronymus Fischer, Dec 20 2012
STATUS
approved