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

%I #12 Jul 16 2015 22:27:06

%S 37,331,317,2322,2389,15259,16260,16728,100291,113825,116101,117109,

%T 796777,796781,819719,823003,4753901,5577444,5738035,5738039,5761027,

%U 31150219,39041113,39336580,40166250,40326841,40336249,218051538,273271861

%N Greatest number (in decimal representation) with n nonprime substrings in base-7 representation (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 not empty and finite. Proof of existence: Define m(n):=2*sum_{j=i..k} 7^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-7 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-7 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 < 7^(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.

%H Hieronymus Fischer, <a href="/A217117/b217117.txt">Table of n, a(n) for n = 0..50</a>

%F a(n) >= A217107(n).

%F a(n) >= A217307(A000217(num_digits_7(a(n)))-n), where num_digits_7(x) is the number of digits of the base-7 representation of x.

%F a(n) <= 7^min(n+2, 5*floor((n+4)/5)).

%F a(n) <= 7^(n+2).

%F a(n) <= 7^min(3 + n/2, 8*floor((n+15)/16)).

%F a(n) <= 343*7^(n/2).

%F With m := floor(log_7(a(n))) + 1:

%F a(n+m+1) >= 7*a(n), if a(n)!=1 (mod 7).

%F a(n+m) >= 7*a(n), if a(n)=1 (mod 7).

%e a(0) = 37, since 37 = 52_7 (base-7) is the greatest number with zero nonprime substrings in base-7 representation.

%e a(1) = 331 = 652_7 has 1 nonprime substring in base-7 representation (= 6). All the other base-7 substrings (2, 5, 52_7=37, 65_7=47 and 652_7=331) are prime substrings. 331 is the greatest number with 1 nonprime substring.

%e a(2) = 317 = 632_7 has 6 substrings in base-7 representation (2, 3, 6, 32, 63 and 632), exactly 2 of them are nonprime substrings (6 and 32_6=20), and there is no greater number with 2 nonprime substrings in base-7 representation.

%e a(8) = 100291 = 565252_3 has 8 nonprime substrings in base-7 representation, these are 6, 252_7, 525_7, 565_7, 5252_7, 5652_7, 6525_7 and 65252_7. There is no greater number with 8 nonprime substrings in base-7 representation.

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

%Y Cf. A035244, A079397, A213300 - A213321.

%Y Cf. A217102 - A217109, A217112 - A217119.

%Y Cf. A217302 - A217309.

%K base,nonn

%O 0,1

%A _Hieronymus Fischer_, Dec 20 2012