A217108 Minimal number (in decimal representation) with n nonprime substrings in base-8 representation (substrings with leading zeros are considered to be nonprime).

2, 1, 10, 8, 67, 66, 64, 523, 525, 514, 512, 4127, 4115, 4099, 4098, 4096, 32797, 32799, 32779, 32771, 32770, 32768, 262237, 262239, 262173, 262163, 262147, 262146, 262144, 2097391, 2097259, 2097211, 2097181, 2097169, 2097163, 2097154, 2097152, 16777695

Offset: 0

Author

Hieronymus Fischer, Dec 12 2012

Keywords

• nonn
• base

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} 8^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-8 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-8 representation), m>=d, than b := p*8^(m-d) has m*(m+1)/2 - k nonprime substrings, and a(A000217(n)-k) <= b.

Examples

			a(0) = 2, since 2 = 2_8 is the least number with zero nonprime substrings in base-8 representation.
a(1) = 1, since 1 = 1_8 is the least number with 1 nonprime substring in base-8 representation.
a(2) = 10, since 10 = 12_8 is the least number with 2 nonprime substrings in base-8 representation (1 and 12).
a(3) = 8, since 8 = 10_8 is the least number with 3 nonprime substrings in base-8 representation (0, 1 and 10).
a(4) = 67, since 67 = 103_8 is the least number with 4 nonprime substrings in base-8 representation, these are 0, 1, 10, and 03 (remember, that substrings with leading zeros are considered to be nonprime).
		

Links

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

Crossrefs

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

Cf. A035244, A079397, A213300-A213321.

Cf. A217102-A217109.

Cf. A217302-A217309.

Formula

a(n) >= 8^floor((sqrt(8*n-7)-1)/2) for n>0, equality holds if n is a triangular number (cf. A000217).

a(A000217(n)) = 8^(n-1), n>0.

a(A000217(n)-k) >= 8^(n-1) + k, 0<=k0.

a(A000217(n)-k) = 8^(n-1) + p, where p is the minimal number >= 0 such that 8^(n-1) + p, has k prime substrings in base-8 representation, 0<=k0.