The Connell Sequence

<HTML> <HEAD> <TITLE>The Connell Sequence</TITLE> </HEAD> <BODY BACKGROUND="../www_tile.gif"> <center> <TABLE border="0" width="75%"> <tr><td> <IMG SRC="../neil.RED15.gif"></td> <td> <a href="../index.html">Journal of Integer Sequences,</a> Vol. 2 (1999), Article 99.1.7</td> </tr> </TABLE> </center> <CENTER> <H2>On Generalizing the Connell Sequence</H2></CENTER> <CENTER> <H3> Douglas E. Iannucci and Donna Mills-Taylor The University of the Virgin Islands 2 John Brewers Bay St. Thomas, VI 00802 Email addresses: <A HREF="mailto:diannuc@uvi.edu">diannuc@uvi.edu</A> and <A HREF="mailto:mil1633@sttmail.uvi.edu">mil1633@sttmail.uvi.edu</A></H3></center> <BLOCKQUOTE> 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. </BLOCKQUOTE> <H2>1. Introduction</H2> In 1959 Ian Connell <a href="#R1">[1]</a> introduced to the public a curious sequence which now bears his name <CENTER> 1, 2, 4, 5, 7, 9, 10, 12, 14, 16,  17,   ...</CENTER> (<A HREF="http://oeis.org/A001614">A001614</A> in the <A HREF="http://oeis.org">On-Line Encyclopedia of Integer Sequences</A>), 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 <a href="#R3">[3]</a> arranged this sequence as a concatenation of finite subsequences,   <CENTER><TABLE BORDER WIDTH="70%" > <TR> <TD>  Subsequence Number :</TD> <TD>   Subsequence :</TD> </TR> <TR> <TD>           1</TD> <TD>   1</TD> </TR> <TR> <TD>           2</TD> <TD>   2, 4</TD> </TR> <TR> <TD>           3</TD> <TD>   5, 7, 9</TD> </TR> <TR> <TD>           4</TD> <TD>   10, 12, 14, 16</TD> </TR> <TR> <TD>           ...</TD> <TD>    ...</TD> </TR> </TABLE></CENTER> where the nth subsequence contains n elements, the last of which is n2.  So if we let c(n) denote the nth element of the Connell sequence then   <CENTER><TABLE BORDER=0 WIDTH="33%" BGCOLOR="#CCFFFF" > <TR ALIGN=CENTER> <TD>c( Tn ) =  n2 ,</TD><td> (1) </td> </TR> </TABLE></CENTER> where Tn =    n (n + 1)/ 2 denotes the nth triangular number. Lakhtakia and Pickover <a href="#R3">[3]</a> used (1) to show that   <CENTER><TABLE BORDER=0 WIDTH="40%" BGCOLOR="#CCFFFF" > <TR ALIGN=CENTER> <TD>lim n  c(n) / n  = 2 ,</TD><td> (2) </td> </TR> </TABLE></CENTER> 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 <a href="#R1">[1]</a>   <CENTER><TABLE BORDER=0 WIDTH="60%" BGCOLOR="#CCFFFF" > <TR ALIGN=CENTER> <TD>c(n) = 2n - Floor( ( 1 + Sqrt( 8n - 7 ) )  /  2 ) .</TD><td> (3) </td> </TR> </TABLE></CENTER>     <A HREF="../stevens.html">Stevens</A> <a href="#R4">[4]</a> defined a generalized Connell k-sequence Ck   for integers k >=  2 (whereby the classical  Connell sequence  becomes the special case C2 ).   In this paper we further  generalize the Connell sequence by affixing another parameter onto Stevens's sequence Ck.  <H2>2.Generalized Connell Sequence with Parameters</H2> 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.   <CENTER><TABLE BORDER WIDTH="100%" BGCOLOR="#FFFF99" > <TR> <TD>Definition 1: Let   m >= 2  and r >= 1  be integers. We denote by  Cm,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  S1, S2, ...  , each of finite length. 2. The subsequence  S1  consists of the element  1. 3.  If the nth  subsequence  Sn ends with the element  e , then the  (n+1)th subsequence Sn+1 begins with the element  e+1 . 4.  If  Sn  consists of  t  elements, then  Sn+1  consists of  t + r  elements. 5.  Each subsequence is nondecreasing, and the difference between two consecutive elements in the same subsequence is  m .  </TD> </TR> </TABLE></CENTER> The sequence  Ck  of Stevens <a href="#R4">[4]</a> is the sequence C k,1 .  When  (m , r) =  ( 3 , 2 ) we obtain <A HREF="http://oeis.org/A045928">C3, 2</A> :   <CENTER><TABLE BORDER WIDTH="60%" > <TR> <TD>           n</TD> <TD>     Sn</TD> </TR> <TR> <TD>               1</TD> <TD>     1</TD> </TR> <TR> <TD>               2</TD> <TD>     2, 5, 8</TD> </TR> <TR> <TD>               3</TD> <TD>     9, 12, 15, 18, 21</TD> </TR> <TR> <TD>               4</TD> <TD>     22, 25, 28, 31, 34, 37, 40</TD> </TR> <TR> <TD>           ...</TD> <TD>     ...</TD> </TR> </TABLE></CENTER> The final elements 1, 8, 21, 40, ...  in the subsequences appear to be the octagonal numbers, En =   n (3n-2 ). The nth subsequence  Sn  contains exactly  2n - 1 elements, and from the identity 1 + 3 + ... + (2n-1)  =  n2  we obtain <CENTER> C3,2( n2 ) =   En .</CENTER> Just as the Connell sequence relates triangular numbers to squares (see (1)), the sequence  C3,2   relates squares to octagonal numbers.  Triangular numbers, squares, and octagonal numbers are all examples of polygonal numbers. <H2>3. Relationships with Polygonal Numbers</H2> <CENTER><TABLE BORDER WIDTH="100%" BGCOLOR="#FFFF99" > <TR> <TD>Definition 2:  For integers  k >= 3, the nth  k-gonal number is <CENTER>Pk(n) =  n ( ( k -2 ) n - k + 4 ) / 2  .</CENTER>  </TD> </TR> </TABLE></CENTER> We shall demonstrate the relationship between  generalized Connell sequences  and polygonal numbers.  Consider the sequence Cm,r . By induction (see conditions 2 and 4 in Definition 1), Sn  contains exactly  ( n - 1 ) r + 1  elements. Therefore to reach the end of nth subsequence  Sn ,  we must count exactly <CENTER> | S1| +  | S2| +  ...  +  | Sn |  =   Pr+2( n )</CENTER> elements of the sequence  Cm,r . Hence  the last element of   Sn   is Cm,r ( Pr+2( n ) ) .  Thus Sn+1  begins (see condition 3 of Definition 1) with the element  Cm,r ( Pr+2( n ) ) + 1 , and, since  | Sn+1 | = nr + 1, it ends (see condition 5 of Definition 1) with the element  Cm,r ( Pr+2( n ) ) + 1 + m ( nr + 1 ) . But this last element is also expressible as  Cm,r ( Pr+2( n  + 1 ) ) . Therefore, assuming the induction hypothesis Cm,r ( Pr+2( n ) ) = Pmr+2( n ) ,  we obtain <CENTER> Cm,r ( Pr+2( n  + 1 ) ) =  Pmr+2( n ) + 1 + m ( nr + 1 ) =  Pmr+2( n + 1 ) ,</CENTER> and hence by induction we have for all  positive integers n,   <CENTER><TABLE BORDER=0 COLS=1 WIDTH="50%" BGCOLOR="#CCFFFF" > <TR> <TD> <CENTER>Cm,r ( Pr+2( n ) ) =  Pmr+2( n ) .</CENTER> </TD> <td> (4) </td> </TR> </TABLE></CENTER> (1) is the special case of (4) when  ( m , r ) = ( 2 , 1 ).  As we remarked in Section 2, C3,2( P4( n ) ) = P8( n) . Another example is given by C3,1  (<A HREF="http://oeis.org/A033292">A033292</A>) :   <CENTER><TABLE BORDER COLS=2 WIDTH="50%" > <TR> <TD>         n</TD> <TD>   Sn</TD> </TR> <TR> <TD>         1</TD> <TD>    1</TD> </TR> <TR> <TD>         2</TD> <TD>    2, 5</TD> </TR> <TR> <TD>         3</TD> <TD>    6, 9, 12</TD> </TR> <TR> <TD>         4</TD> <TD>    13, 16, 19, 22</TD> </TR> <TR> <TD>        ...</TD> <TD>       ...</TD> </TR> </TABLE></CENTER> Here the pentagonal numbers P5( n ) = n ( 3n - 1 ) / 2 at the end of each subsequence. It is interesting to note that, since all elements of  Sn  are congruent to  n ( mod m ), we obtain the following property of polygonal numbers: Pmr+2( n) is congruent to  n ( mod m ). <H2>4. Limiting Behavior</H2> We will determine the behavior of   Cm,r ( n ) / n as n goes  to infinity, following Lakhtakia and Pickover <a href="#R3">[3]</a>, by computing  limn Cm,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 = Pr+2( j ) + i .  Thus  Cm,r ( n )  belongs to the subsequence  Sj+1 . As Cm,r( Pr+2( j ) ) is the last element of Sj , we have from Definition 1 and (4)                                             Cm,r ( n ) =  Cm,r ( Pr+2( j ) + i )                                                            =  Cm,r( Pr+2( j ) ) + 1 + ( i - 1 ) m                                                            =   Pmr+2( j ) + 1 + ( i - 1 ) m. Thus, since   1 <=   i  <=  1 + rj   and   n = Pr+2( j ) + i ,  we have  A <=  Cm,r ( n ) / n  <=  B  ,  where                                 A = (  Pmr+2( j ) + 1 ) / ( Pr+2( j )  + 1 + rj ) ,                                   B =  ( Pmr+2( j ) + 1  + jmr ) / ( Pr+2( 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   <CENTER><TABLE BORDER=0 WIDTH="60%" BGCOLOR="#CCFFFF" > <TR> <TD> <CENTER>limn  Cm,r ( n ) / n  =  m .</CENTER> </TD> <td> (5) </td> </TR> </TABLE></CENTER> <H2>5. A Direct Formula</H2> To find a formula for  Cm,r ( n)  we modify Korsak's <a href="#R2">[2]</a> proof of (3). Define the sequence T by <CENTER> T( n )  =  mn  -  Cm,r ( n ) .</CENTER> We assume  n > 1  and write   n = Pr+2( 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 >=  Pr+2( j) + 1 , <CENTER>rj2 - ( r - 2) j - ( 2n - 2 ) <= 0,</CENTER> a quadratic inequality in  j  which implies <CENTER> j + 1 <= ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )2 ) ) / 2k ,</CENTER> and hence <CENTER>j + 1 =  Floor( ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )2 ) ) / 2k ) .</CENTER> Thus                  T( n )  =  ( m - 1 ) Floor( ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )2 ) ) / 2k ) , and so   <CENTER><TABLE BORDER=0 BGCOLOR="#CCFFFF" > <TR> <TD> <CENTER> Cm,r ( n ) = nm - ( m - 1 ) Floor( ( 3r - 2 + Sqrt( 8r ( n -1 ) + ( r - 2 )2 ) ) / 2k ) .</CENTER> </TD> <td> (6) </td> </TR> </TABLE></CENTER> <H2>References</H2> <a name="#R1">[1]</a>   Amer. Math. Monthly, 66, no. 8 (October, 1959), 724.  Elementary Problem E1382. <a name="#R2">[2]</a>   Amer. Math. Monthly, 67, no. 4 (April, 1960), 380. Solution to Elementary Problem E1382. <a name="#R3">[3]</a>   Lakhtakia, A. &  Pickover, C.  The Connell sequence,  J. Recreational Math., v. 25, no. 2 (1993), 90-92. <a name="#R4">[4]</a>    Stevens,  G.  A Connell-like sequence,  J. of Integer Sequences, v.1,  Article 98.1.4.   <hr> (Concerned with sequences <A HREF="http://oeis.org/A001614">A001614</A> , <A HREF="http://oeis.org/A033292">A033292</A> , <A HREF="http://oeis.org/A045928">A045928</A> , <A HREF="http://oeis.org/A045929">A045929</A> , <A HREF="http://oeis.org/A045930">A045930</A> .) <hr> Received February 9 1999; published in Journal of Integer Sequences, March 16 1999. <hr> Return to <a href="../index.html">Journal of Integer Sequences home page</a> <hr> </body> </html>

CINXE.COM

The Connell Sequence