login
A217103
Minimal number (in decimal representation) with n nonprime substrings in base-3 representation (substrings with leading zeros are considered to be nonprime).
3
2, 1, 3, 4, 14, 9, 34, 29, 30, 27, 89, 88, 83, 84, 81, 268, 251, 250, 248, 245, 243, 752, 754, 746, 740, 734, 731, 729, 2237, 2239, 2210, 2203, 2198, 2192, 2189, 2187, 6632, 6611, 6614, 6584, 6577, 6569, 6563, 6564, 6561, 19814, 19754, 19733, 19736, 19706
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. Proof: Define m(n):=2*sum_{j=i..k} 3^j, where k:=floor((sqrt(8*n+1)-1)/2), i:= n-A000217(k). For n=0,1,2,3,… the m(n) in base-3 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, which proves the statement.
If p is a number with k prime substrings and d digits (in base-3 representation), p != 1 (mod 3), m>=d, than b := p*3^(m-d) has m*(m+1)/2 - k nonprime substrings, and a(A000217(n)-k) <= b.
LINKS
FORMULA
a(n) >= 3^floor((sqrt(8*n-7)-1)/2) for n>0, equality holds if n=1 or n+1 is a triangular number (cf. A000217).
a(n) >= 3^floor((sqrt(8*n+1)-1)/2) for n>3, equality holds if n+1 is a triangular number.
a(A000217(n)-1) = 3^(n-1), n>1.
a(A000217(n)-k) >= 3^(n-1) + k-1, 1<=k<=n, n>1.
a(A000217(n)-k) = 3^(n-1) + p, where p is the minimal number >= 0 such that 3^(n-1) + p, has k prime substrings in base-3 representation, 1<=k<=n, n>1.
EXAMPLE
a(0) = 2, since 2 = 2_3 is the least number with zero nonprime substrings in base-3 representation.
a(1) = 1, since 1 = 1_3 is the least number with 1 nonprime substring in base-3 representation.
a(2) = 3, since 3 = 10_3 is the least number with 2 nonprime substrings in base-3 representation (0 and 1).
a(3) = 4, since 4 = 11_3 is the least number with 3 nonprime substrings in base-3 representation (1, 1 and 11).
a(4) = 14, since 14 = 112_3 is the least number with 4 nonprime substrings in base-3 representation, these are 1, 1, 11 and 112 (remember, that substrings with leading zeros are considered to be nonprime).
a(7) = 29, since 29 = 1002_3 is the least number with 7 nonprime substrings in base-3 representation, these are 0, 0, 1, 00, 02, 002 and 100 (remember, that substrings with leading zeros are considered to be nonprime, 2_3 = 2, 10_3 = 3 and 1002_3 = 29 are base-3 prime substrings).
KEYWORD
nonn,base
AUTHOR
Hieronymus Fischer, Dec 12 2012
STATUS
approved