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

2, 1, 5, 4, 19, 17, 16, 75, 67, 66, 64, 269, 263, 266, 257, 256, 1053, 1031, 1035, 1029, 1026, 1024, 4125, 4119, 4123, 4107, 4099, 4098, 4096, 16479, 16427, 16431, 16407, 16395, 16391, 16386, 16384, 65709, 65629, 65579, 65581, 65559, 65543, 65539, 65537, 65536

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

Links

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

Formula

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

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

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

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

Example

a(0) = 2, since 2 = 2_4 is the least number with zero nonprime substrings in base-4 representation.
a(1) = 1, since 1 = 1_4 is the least number with 1 nonprime substring in base-4 representation.
a(2) = 5, since 5 = 11_4 is the least number with 2 nonprime substrings in base-4 representation (these are 2-times 1).
a(3) = 4, since 4 = 10_4 is the least number with 3 nonprime substrings in base-4 representation (these are 0, 1 and 10).
a(4) = 19, since 19 = 103_4 is the least number with 4 nonprime substrings in base-4 representation, these are 0, 1, 10, and 03 (remember, that substrings with leading zeros are considered to be nonprime).
a(7) = 75, since 75 = 1023_4 is the least number with 7 nonprime substrings in base-4 representation, these are 0, 1, 10, 02, 023, 102 and 1023 (remember, that substrings with leading zeros are considered to be nonprime: 2_4 = 2, 3_4 = 3 and 23_4 = 11 are the only base-4 prime substrings of 75).

Crossrefs

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

Cf. A035244, A079397, A213300-A213321.

Cf. A217102-A217109.

Cf. A217302-A217309.

Sequence in context: A257516 A346800 A124660 * A141485 A005605 A300661

Adjacent sequences: A217101 A217102 A217103 * A217105 A217106 A217107

Keyword

nonn,base

Author

Hieronymus Fischer, Dec 12 2012

Status

approved