 |
Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.3 |
|
|
Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.3 |
Abstract: Let the integer sequence A be constructed by the greedy algorithm as follows: Set a[0]=0 and, for n>0, choose a[n] to be the smallest integer greater than a[n-1] such that no member of s={a[0],...,a[n]} is the average of three other members of s. A simple alternative description of A is given in terms of its representation in base 4.
It is well known that some sequences which are difficult to calculate directly from their definition are quite easy to compute by an alternative method based on the form of their terms when written in a certain number base. An example, given in [1, Sec. E10], is the integer sequence S containing no 3-term arithmetic progression, constructed by the greedy algorithm as follows: Set a[0]=0. Each subsequent term a[n], for n>0, is chosen to be the least integer greater than a[n-1] so that a[0],a[1], ..., a[n] does not contain a 3-term arithmetic progression. This produces the sequence
0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, ...
which in base 3 is
0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1111, 10000, 10001, ... .
Thus it appears that S is the sequence of positive integers that do not contain 2 when written in base 3, and this can easily be shown to be the case.
No equally simple way seems to exist for describing the analogous greedy sequence constructed so as to contain no 4-term arithmetic progression. It turns out, however, that further progress in this direction can be made if we view the above sequence S not as one containing no 3-term arithmetic progression, but instead as one in which no term is the average of two others, an obviously equivalent condition. Additionally, we can restate the condition that an integer N contains no 2 when written in base 3 as the condition that N = M + r where M contains only 0's and 1's in base 3, and ends in 0, with r = 0 or 1. We pursue this idea in the next section.
Erdös and Straus [2] define a nonaveraging set A by the property that no member shall be the average of any subset of A with more than one element. (See also [1, Sec. C16]). It is straightforward to carry this concept over to integer sequences. Here we consider the less restrictive case of the integer sequence A defined by the greedy algorithm by a[0] = 0 and, for n>0, a[n] is the least integer such that no member of S = {a[0], a[1],..., a[n]} is the average of three other members of S. A computer program was written to calculate the terms of A, finding
0, 1, 2, 3, 4, 12, 13, 14, 15, 16, 48, 49, 50, 51, 52, 60, 61, 62, 63, 64, 192, 193, ... ,
which was found to be absent from N. J. A. Sloane's On-Line Encyclopedia of Integer Sequences (http://oeis.org). It has recently been added as sequence number A036779 (January 1999).
In an attempt to discover a simple alternative description of this sequence, it was written in base 4, giving
0, 1, 2, 3, 10, 30, 31, 32, 33, 100, 300, 301, 302, 303, 310, 330, 331, 332, 333, 1000, 3000, 3001, ... .
Each base 4 digit occurs in the terms of this sequence, so clearly no explanation will be as simple as the one in the previous section. However, just as in the terms shown, it was found that if N is any one of the first several hundred terms of A, then M and r exist such that N = M + r where M, when written in base 4, ends with 0, and contains only the digits 0 and 3, and where r is 0,1,2,3 or 4. In addition, each of the first several hundred integers which may be so written is found to be a term of the sequence. The general validity of this characterization will now be established.
We define two sequences as follows:
(D1) Let A be the integer sequence defined by the greedy algorithm,
with a[0] = 0 and a[n] chosen to be the smallest integer greater
than a[n-1] such that no member of {a[0], a[1],..., a[n]} is the average
of three other members.
(D2) Let B be the subsequence of the nonnegative integers N that
can be written as N = M + r, where the base 4 representation
of M ends with 0 and contains only the digits 0 and 3, and where r is 0,
1, 2, 3, or 4.
The following lemma shows that B has the nonaveraging property of A.
Lemma 1. There does not exist a term of B which is the average
of three other terms of B.
Proof (by contradiction). Suppose that there do exist four distinct
terms t, u, v, and w of B such that t is the average of u, v, and w, i.e.
3t=u+v+w. Write t in the base 4 form described in (D2) above, that is,
in the form
t = M1 + r1 = tk1tk1-1...t2t1 + r1
where the ti are the digits of M1 when written in base 4, with tk1=3, t1=0, all other ti=0 or 3, and r1 in [0...4]. Write each of u = M2 + r2, v = M3 + r3, and w = M4 + r4 in the corresponding form, i.e. u = uk2...u1 + r2, etc. We now write T = 3t, without reducing digits mod 4, to get
T = 3t = Tk1Tk1-1...T2T1 + R
where Tk1 = 9, T1 = 0, all other Ti = 0 or 9, and R is in [0, 4, 8, 12]. There are now two cases, according to whether R<12 or R=12. If R<12 or, equivalently, R<30(base 4) then, since T = u + v + w, we clearly must have k4 = k3 = k2 = k1 with uk1 = vk1 = wk1 = 3, u1 = v1 = w1 = 0, and for all other i, ui = vi = wi = 0 or 3. In other words, we must have M1, M2, M3, and M4 all equal to a common integer, say N, giving t=N+r1, u=N+r2, v=N+r3, and w=N+r4, where r1, r1, r3, and r4 all have values in 0...4, with r1=(r2+r3+r4)/3. But this is a contradiction, since it is easily verified that none of the integers 0...4 is the average of three others. On the other hand, if R=12 then either each of r2, r3, and r4 must be 4 thus giving u = v = w, contradicting the distinctness of the terms, or, since R=12=30(base 4), R can be carried into T to give Tj = 3 for some j>1, with all other Ti = 0 or 9 in Eq. (3.2). But this latter situation means that two of u2, v2, and w2 must be 0 or 3, thus requiring that two of u, v, and w must be equal, again contradicting the distinctness of the terms and completing the proof.
The next lemma shows that no additional terms can be inserted into B without violating the nonaveraging property, thus showing that B has the "greedy" property of A.
Lemma 2. Let n be an integer that is not a term of B.
Then there exist three distinct terms u, v, and w of B, each smaller than
n, such that u is the average of v, w, and n.
Proof. Write n in base 4: n = nknk-1...n2n1(base
4). If nk is 1 or 2 then "carry" that digit
to the right by adding 4*nk to nk-1. It is easy to
see that the maximum value of the excess of this sum over one of 3, 6,
or 9, is 2. Continue this process to the right on the digits ni
until i = 1, then set r = n1 followed by n1 = 0.
Clearly r lies in 0...11. We now have n expressed in the form
n = D + r = dkdk-1...d2d1(base
4) + r, where d1 = 0, all other di = 0, 3, 6, or
9, and r is in 0..11. Now, for each i = 2...k, choose vi
and wi to be 0 or 3 in such a way that di + vi
+ wi = 9. Direct calculation shows that rv and rw can
always be chosen so that r+rv+rw=3ru where ru, rv, and rw are distinct
and each in 0...4. Clearly v, w, and u=(v+w+n)/3 are terms of B,
and the proof is complete.
As an illustration of the constructive nature of the proof of Lemma 2, consider n = 2500 = 213010(base 4) = 93000(base 4) + 4. Choose v = 3000(base 4) + 1, w = 3000(base 4) + 4. Then u = (99000(base 4) + 9)/3 = 33000(base 4) + 3. Thus u, v, and w are distinct terms of B and u is the average of v, w, and n.
Lemmas (1) and (2), together with the fact that sequences A and B have the same initial terms, lead immediately to our main result, as follows:
Theorem. If sequences A and B are as defined above in (D1) and (D2), then A=B.
Another illustration. The theorem allows us to easily determine whether any given positive integer n is a term of the greedy integer sequence A with first term 0 and containing no term which is the average of three other terms. For example, n = 123456789(base 10) = 13112330310111(base 4) does not have the required form in base 4 and thus is not a term of A, whereas n = 217105166(base 10) = 30330030030030(base 4) + 2 does have the required form and thus is a term of A. The determination of these facts by computation directly from the definition of A would appear to be impossible for all practical purposes.
[1] Richard K. Guy, Unsolved Problems in Number Theory, Springer-Verlag,
NY, 2nd ed., 1994.
[2] P. Erdös & E. G. Straus, Nonaveraging sets II, Combinatorial Theory and its Applications II, in Colloq, Math. Soc. Janos Bolyai 4, North-Holland, 1970, pp. 405-411.
(Concerned with sequences A005836 and A036779 .)
Received Feb 25, 1999. Published in Journal of Integer Sequences March 14, 1999.