The Connell Sequence

Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.7

On Generalizing the Connell Sequence

Douglas E. Iannucci
and
Donna Mills-Taylor
The University of the Virgin Islands
2 John Brewers Bay
St. Thomas, VI 00802
Email addresses: diannuc@uvi.edu and mil1633@sttmail.uvi.edu

Abstract: We introduce a generalization of the Connell Sequence which relies on two parameters: the modulus m and the successive row length difference r. We show its relationship with polygonal numbers, examine its limiting behavior, and find an expression for the general term.

1. Introduction

In 1959 Ian Connell [1] introduced to the public a curious sequence which now bears his name

1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ...

(A001614 in the On-Line Encyclopedia of Integer Sequences), in which the first odd number is followed by the next two even numbers, which in turn are followed by the next three odd numbers, and so on.
Lakhtakia and Pickover [3] arranged this sequence as a concatenation of finite subsequences,

Subsequence Number :	Subsequence :
1	1
2	2, 4
3	5, 7, 9
4	10, 12, 14, 16
...	...

where the nth subsequence contains n elements, the last of which is n². So if we let c(n) denote the nth element of the Connell sequence then

c( T_n ) = n² ,

(1)

where T_n = n (n + 1)/ 2 denotes the nth triangular number. Lakhtakia and Pickover [3] used (1) to show that

lim _nc(n) / n = 2 ,

(2)

thus explaining the limiting behavior of the Connell sequence. The same authors remarked that (2) could have been obtained directly from the formula for c(n) given by Connell [1]

c(n) = 2n - Floor( ( 1 + Sqrt( 8n - 7 ) ) / 2 ) .

(3)

Stevens [4] defined a generalized Connell k-sequence C_kfor integers k >= 2 (whereby the classical Connell sequence becomes the special case C₂). In this paper we further generalize the Connell sequence by affixing another parameter onto Stevens's sequence C_k.

2.Generalized Connell Sequence with Parameters

For fixed integers m >= 2 and r >= 1 we construct a sequence as follows: take the first integer which is congruent to 1 (mod m) (that being 1 itself), followed by the next 1 + r integers which are congruent to 2 (mod m), followed by the next 1 + 2r integers which are congruent to 3 (mod m), and so on. If m = 2 and r = 1 (the smallest possible cases) we have the Connell sequence. Here is the formal definition.

Definition 1: Let m >= 2 and r >= 1 be integers. We denote by C_m,r(n) the nth term of the generalized Connell sequence with parameters m and r , or, simply, the Connell ( m , r )-sequence . The sequence is defined as follows:

1. The sequence is formed by concatenating subsequences S₁, S₂, ... , each of finite length.

2. The subsequence S₁consists of the element 1.

3. If the nth subsequence S_n ends with the element e , then the (n+1)th subsequence S_n+1 begins with the element e+1 .

4. If S_nconsists of t elements, then S_n+1consists of t + r elements.

5. Each subsequence is nondecreasing, and the difference between two consecutive elements in the same subsequence is m .

The sequence C_k of Stevens [4] is the sequence C _k,1. When (m , r) = ( 3 , 2 ) we obtain C_{3, 2} :

n	S_n
1	1
2	2, 5, 8
3	9, 12, 15, 18, 21
4	22, 25, 28, 31, 34, 37, 40
...	...

The final elements 1, 8, 21, 40, ... in the subsequences appear to be the octagonal numbers, E_n = n (3n-2 ). The nth subsequence S_n contains exactly 2n - 1 elements, and from the identity 1 + 3 + ... + (2n-1) = n² we obtain

C_3,2( n²) = E_n.

Just as the Connell sequence relates triangular numbers to squares (see (1)), the sequence C_3,2relates squares to octagonal numbers. Triangular numbers, squares, and octagonal numbers are all examples of polygonal numbers.

3. Relationships with Polygonal Numbers

Definition 2: For integers k >= 3, the nth k-gonal number is P_k(n) = n ( ( k -2 ) n - k + 4 ) / 2 .

We shall demonstrate the relationship between generalized Connell sequences and polygonal numbers. Consider the sequence C_m,r. By induction (see conditions 2 and 4 in Definition 1), S_n contains exactly ( n - 1 ) r + 1 elements. Therefore to reach the end of nth subsequence S_n , we must count exactly

| S₁| + | S₂| + ... + | S_n | = P_r₊₂( n )

elements of the sequence C_m,r. Hence the last element of S_n is C_m,r( P_r₊₂( n ) ) . Thus S_n₊₁ begins (see condition 3 of Definition 1) with the element C_m,r( P_r₊₂( n ) ) + 1 , and, since | S_n₊₁ | = nr + 1, it ends (see condition 5 of Definition 1) with
the element C_m,r( P_r₊₂( n ) ) + 1 + m ( nr + 1 ) . But this last element is also expressible as C_m,r( P_r₊₂( n + 1 ) ) . Therefore, assuming the induction hypothesis C_m,r( P_r₊₂( n ) ) = P_mr₊₂( n ) , we obtain

C_m,r( P_r₊₂( n + 1 ) ) = P_mr₊₂( n ) + 1 + m ( nr + 1 ) = P_mr₊₂( n + 1 ) ,

and hence by induction we have for all positive integers n,

C_m,r( P_r₊₂( n ) ) = P_mr₊₂( n ) .

(4)

(1) is the special case of (4) when ( m , r ) = ( 2 , 1 ). As we remarked in Section 2, C_3,2( P₄( n ) ) = P₈( n) . Another example is given by C_3,1 (A033292) :

n	S_n
1	1
2	2, 5
3	6, 9, 12
4	13, 16, 19, 22
...	...

Here the pentagonal numbers P₅( n ) = n ( 3n - 1 ) / 2 at the end of each subsequence.

It is interesting to note that, since all elements of S_n are congruent to n ( mod m ), we obtain the following property of polygonal numbers: P_mr₊₂( n) is congruent to n ( mod m ).

4. Limiting Behavior

We will determine the behavior of C_m,r( n ) / n as n goes to infinity, following Lakhtakia and Pickover [3], by computing lim_n C_m,r( n ) / n from (4). Let n be a positive integer. There is a positive j , and a fixed i such that 1 <= i <= 1 + rj , for which n = P_r₊₂( j ) + i . Thus C_m,r( n ) belongs to the subsequence S_j₊₁ . As C_m,r( P_r₊₂( j ) ) is the last element of S_j , we have from Definition 1 and (4)

                                            C_m,r( n ) = C_m,r( P_r₊₂( j ) + i )
                                                           = C_m,r( P_r₊₂( j ) ) + 1 + ( i - 1 ) m
                                                           =   P_mr₊₂( j ) + 1 + ( i - 1 ) m.

Thus, since   1 <=   i <= 1 + rj   and   n = P_r₊₂( j ) + i , we have A <= C_m,r( n ) / n <= B , where
                                A = ( P_mr₊₂( j ) + 1 ) / ( P_r₊₂( j ) + 1 + rj ) ,

                                B = ( P_mr₊₂( j ) + 1 + jmr ) / ( P_r₊₂( j ) + 1 ) .

Recalling Definition 2, it is a simple matter to verify that A and B both converge to the limit m as j tends toward infinity. Therefore

lim_n C_m,r( n ) / n = m .

(5)

5. A Direct Formula

To find a formula for C_m,r( n) we modify Korsak's [2] proof of (3). Define the sequence T by

T( n ) = mn - C_m,r( n ) .

We assume n > 1 and write n = P_r₊₂( j ) + i exactly as in Section 4. Then after some algebra we find that T( n ) = ( j +1 )( m - 1 ), so j + 1 = T( n ) / ( m - 1 ). Since n >= P_r₊₂( j) + 1 ,

rj² - ( r - 2) j - ( 2n - 2 ) <= 0, a quadratic inequality in j which implies

j + 1 <= ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )² ) ) / 2k ,

and hence j + 1 = Floor( ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )² ) ) / 2k ) .

Thus
T( n ) = ( m - 1 ) Floor( ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )² ) ) / 2k ) ,

and so

C_m,r( n ) = nm - ( m - 1 ) Floor( ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )² ) ) / 2k ) .

(6)

References

[1] Amer. Math. Monthly, 66, no. 8 (October, 1959), 724. Elementary Problem E1382.

[2] Amer. Math. Monthly, 67, no. 4 (April, 1960), 380. Solution to Elementary Problem E1382.

[3] Lakhtakia, A. & Pickover, C. The Connell sequence, J. Recreational Math., v. 25, no. 2 (1993), 90-92.

[4] Stevens, G. A Connell-like sequence, J. of Integer Sequences, v.1, Article 98.1.4.

(Concerned with sequences A001614 , A033292 , A045928 , A045929 , A045930 .)

Received February 9 1999; published in Journal of Integer Sequences, March 16 1999.

Return to Journal of Integer Sequences home page