 Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.4

## A Connell-Like Sequence

### Gary E. Stevens Department of Mathematics Hartwick College, Oneonta, NY  13820 Email address: StevensG@Hartwick.edu

ABSTRACT

We introduce a generalization of the Connell Sequence, generated by using groups of q terms each a multiple of q (rather than just being even or odd as q is), and find an expression for the general term.

INTRODUCTION.

The Connell Sequence 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, ... (A001614 in the On-Line Encyclopedia of Integer Sequences) is generated as follows:

take the first odd integer, the next two even integers, the next three odd integers, the next four even integers, etc.

In 1959 Ian Connell  posed the problem of proving that this sequence has general term:

un = 2n - Floor(1 + Sqrt(8n - 7)))
where Floor(x) is the largest integer less than or equal to x.  A solution appeared in .  The sequence has some practical applications in antenna theory  and some of its properties have also been studied in .

In this article we consider the following generalization of the Connell Sequence.

 Definition:  Let {Sn} be the Connell-like sequence generated as follows: Take the first multiple of one, the next two multiples of two, the next three multiples of three, the next four multiples of four, ..., the next q multiples of q, etc.

The resulting sequence (now A033291) is

1, 2, 4, 6, 9, 12, 16, 20, 24, 28, 30, 35, 40, 45, 50, 54, 60, . . . .

THE DISCOVERY.

Let q denote the multipliers used in the sections of the general sequence so that q runs through all positive integer values and is used as a multiplier q times. Note that the subscript of the last term of the section which uses the multiplier q will be the qth triangular number, tq.  Thus, if n is any subscript appearing in the section of the sequence using the multiplier q, then

tq-1 < n <= tq = ½ (q(q + 1)).
Solving for q in terms of n, we find q must be the smallest (non-negative) integer satisfying the quadratic equation
q2 + q - 2n = 0.  Using Ceiling(x) to indicate the least integer greater than or equal to x, we can write
qn = q(n) = Ceiling (½ (-1 + sqrt(1 + 8n)))
to express the multiplier used for the nth term of the sequence.        To begin developing an expression for the general term, we consider the expression (nqn - Sn) / qn which is constant for elements of the same section (using the same q).  This is easy to see since if Sn and Sn+1 are in the same section of multiples of q, i.e. q = qn = qn+1, then Sn+1 = Sn + q, so that
((n + 1)q - Sn+1) / q = (nq + q - (Sn + q)) / q = (nq - Sn) / q.

Thus we can define a sequence related to Sn by  vq = (nqn - Sn) / qn, where n is any subscript from the section of the sequence Sn which uses multiplier q.  This sequence (A001840) looks like:

0, 1, 2, 3, 5, 7, 9, 12, 15, 18, 22, 26, 30, 35, 40, 45, 51, 57, 63, 70, . . . .

This sequence uses an increment of 1 for three terms, then 2 for three terms, then 3 for three terms, and so forth.  If we ignore the three term groupings and think about a sequence that increments by 1, then by 2, then by 3, etc., it would have to look basically like ½ q2.  To get the groupings of three, we can divide this by 3 and use the floor function to obtain Floor(q2 / 6)  which produces the sequence 0, 0, 1, 2, 4, ..., which is not quite right.  A slight adjustment allows us to write

vq = Floor(q(q + 1) / 6).
Equating this with the expression defining vq and solving for Sn  gives
Sn      =      qnn - qnvq(n)      =      qnn - qn Floor(qn(qn + 1) / 6)
where
qn = Ceiling (½ (-1 + sqrt(1 + 8n))).

This result, however, has been obtained by observing the first few terms of some infinite sequences.  It is conceivable that the pattern displayed by the first twenty terms of the sequence vq might change at some point.  (Using a computer program to check up to a q-value of 500,500 revealed no change in the pattern, though.)  We still need to prove that the sequences always behave this way so that the formula discovered above gives the correct value for all n.

THE PROOF.

 Theorem.  Let {Sn} be the sequence defined above and let qn = q(n) = Ceiling (½ (-1 + sqrt(1 + 8n))) so that qn is the multiplier used in the section of the sequence containing the term Sn.   Let vq = Floor(q(q + 1) / 6) for q >= 1.  Then Sn = qnn - qnvq(n)  for all n >= 1.

Proof (by induction on n). For n = 1, q1 = 1 and Sn = S1 = 1 = 1·1 - 1·0 = q1·1 - q1· vq(1) = qn· n - qn· vq(n).
Assume the theorem is true for n. If Sn and Sn+1 are from the same section, i.e. use the same multiplier, then qn = qn+1 = q and vq(n) = vq(n+1) = vq
and so

Sn+1 = Sn + q = qn - qvq + q = q(n + 1) - qvq = qn+1(n + 1) - qn+1vq+1 ,

as required.

If Sn and Sn+1 are from sections with different multipliers, then  qn+1 = qn+ 1 = q + 1 and Sn was the last term in the section using multiplier q so n = ½ (q(q + 1)) and q = ½ (-1 + sqrt(1 + 8n)).  Sn+1 will be the first term larger than Sn which is divisible by q+1.  The proposed expression for Sn+1, qn+1(n + 1) - qn+1vq+1 , is obviously divisible by qn+1 so we only need to show it is the first such number larger than Sn.  We consider the difference between this expression and Sn and show it is at most q + 1 which will guarantee that our expression gives us Sn+1.

Now

qn+1(n + 1) - qn+1vq+1 - Sn = (q + 1)(n + 1) - (q + 1)vq+1 - (qn - qvq)
= (q + 1) - ((q + 1)vq+1 - qvq - n)
= (q + 1) - ((q + 1)vq+1 - qvq - ½ (q(q + 1)))

This difference will thus be at most q + 1 if (q + 1)vq+1 - qvq - ½ (q(q + 1)) >= 0.
Let  f(q) = (q + 1)vq+1 - qvq - ½ (q(q + 1))     = (q + 1) Floor((q + 1)(q + 2) / 6) - q Floor(q(q + 1) / 6) - ½ (q(q + 1)) .

We consider six cases, the possibilities for q mod 6, and compute (omitting the arithmetic details) the exact value of  f(q) in each case:

f(6k) = 0,                 f(6k + 1) = 4k + 1,             f(6k + 2) = 2k + 1,
f(6k + 3) = 0,           f(6k + 4) = 4k + 3,             f(6k + 5) = 2k + 2.

In each case, since k >= 0, we find f(q) >= 0, so that the difference between Sn and the proposed expression for Sn+1 at most q + 1.  Thus, this expression, since it is divisible by q + 1, does give the first multiple of q + 1 which is larger than Sn, i.e. it gives Sn+1.  The induction is complete and the result proved. 

After reading an initial version of this paper, a colleague, Gerry Hunsberger, suggested another way of generalizing the Connell Sequence. Instead of thinking of the original seqence in terms of even and odd numbers, it is also possible to think of it as "one integer congruent to 1 mod 2, the next two integers congruent to 2 mod 2, the next three integers congruent to 3 mod 2, the next four integers congruent to 4 mod 2, and so forth. This still produces the Connell Sequence but allows for a nice generalization by changing the modulus.

 Definition. The Connell k-Sequence, Ck, is defined by taking one integer congruent to 1 mod k, the next two integers congruent to 2 mod k, the next three integers congruent to 3 mod k, the next four integers congruent to 4 mod k, and so forth.

For example, the Connell 3-Sequence would be 1, 2, 5, 6, 9, 12, 13, 16, 19, 22, 23, 26,... (now A033292) and the 8-Sequence would be 1, 2, 10, 11, 19, 27, 28, 36, 44, 52, 53, 61, ... (now A033293).

Within each grouping of terms, the terms increase by an amount k, and when changing from one grouping to the next, the increment is 1. The groupings change after each trianular number. Thus we can consider the nth term as being obtained by adding k for n terms and then subtracting (k-1) for each triangular number less than n. If n is the qth triangular number then q = ½ (-1+sqrt(8n+1)). Since we want to count the number of triangular numbers less than this we replace n by (n-1) and apply the floor function. Thus we find that we can write the general term of the Connell k-Sequence as

 Ck(n) = kn - (k - 1)Floor(½ (-1+sqrt(8n+1))).

References.
   American Mathematical Monthly, 66 (1959), 724.   Elementary Problem E1382.
   American Mathematical Monthly, 67 (1960), 380. Solution to Elementary Problem E1382.
   Lakhtakia, A., V. K. Varadan, & V. V. Varadan.  Connell arrays.  Archiv für Elektronik und
Übertragungstechnik, 42, (3) (1988), 186-189.
   Lakhtakia, A. & Clifford Pickover.  The Connell sequence.  J. Recreational Math., 25 (1993), 90-92.

Received Jan. 30, 1998; published in Journal of Integer Sequences, April 26, 1998.