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

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:

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

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

The resulting sequence (now A033291) is   

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 q^th triangular number, t_q.  Thus, if n is any subscript appearing in the section of the sequence using the multiplier q, then

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

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 ½ q².  To get the groupings of three, we can divide this by 3 and use the floor function to obtain Floor(q² / 6)  which produces the sequence 0, 0, 1, 2, 4, ..., which is not quite right.  A slight adjustment allows us to write 

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 v_q 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, q₁ = 1 and S_n = S₁ = 1 = 1·1 - 1·0 = q₁·1 - q₁· v_q(1) = q_n· n - q_n· v_q(n).
      Assume the theorem is true for n. If S_n and S_n+1 are from the same section, i.e. use the same multiplier, then q_n = q_n+1 = q and v_q(n) = v_q(n+1) = v_q
and so

as required.

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

Now

      q_n+1(n + 1) - q_n+1v_q+1 - S_n = (q + 1)(n + 1) - (q + 1)v_q+1 - (qn - qv_q)
          = (q + 1) - ((q + 1)v_q+1 - qv_q - n)
          = (q + 1) - ((q + 1)v_q+1 - qv_q - ½ (q(q + 1)))

This difference will thus be at most q + 1 if (q + 1)v_q+1 - qv_q - ½ (q(q + 1)) >= 0.
Let  f(q) = (q + 1)v_q+1 - qv_q - ½ (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:

In each case, since k >= 0, we find f(q) >= 0, so that the difference between S_n and the proposed expression for S_n+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 S_n, i.e. it gives S_n+1.  The induction is complete and the result proved. 

ADDENDUM.

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.

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 n^th 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 q^th 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

References.
[1]   American Mathematical Monthly, 66 (1959), 724.   Elementary Problem E1382.
[2]   American Mathematical Monthly, 67 (1960), 380. Solution to Elementary Problem E1382.
[3]   Lakhtakia, A., V. K. Varadan, & V. V. Varadan.  Connell arrays.  Archiv für Elektronik und
               Übertragungstechnik, 42, (3) (1988), 186-189.
[4]   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.