Submitted to J. Comb. Th. A on Jan. 4, 2006
Rejected on Feb. 20, 2006

New conjectures and list of OEIS entries placed in Addendum on 3/20/06

Posted on Web Page 3/25/06

Note

On a Generalization of Very Odd Sequences

John W. Layman
<layman@math.vt.edu>
Department of Mathematics, Emeritus
Virginia Polytechnic Institute and State University
Blacksburg, Virginia, 24060, U.S.A.
January, 2006

Suppose that nεN and a = (,...,) is a sequence of length n with ε {0,...,b-1}.  For 0≤k≤n-1, let

= .

If   ≡ r (mod b) for k = 0,...,n-1, we say that the sequence a is very(b,r). This generalizes the concept of very odd sequences introduced by Inglis and Wiseman. We show that arbitrarily long very(3,1) and very(3,2) sequences exist by proving that, given a very(3,r) sequence, a longer very(3,3-r) sequence can be constructed, for r=1,2. A related conjecture is stated for very(5,1) and very(5,4) sequences.

1. Introduction.

Suppose that n and b are natural numbers and that a = (,...,) is a sequence of length n with ε {0,...,b-1}.  For 0≤k≤n-1, let

= .

If
≡ r (mod b) for k = 0,...,n-1, we say that the sequence a is very(b,r). Pelikan [5] conjectured that no very(2,1) sequence exists for n>4.   MacWilliams and Odlyzko [3] and Alles [1] showed that this conjecture is false, the latter also giving a constructive proof that there exist infinitely many finite very(2,1) sequences and showing explicitly how to construct a very(2,1) sequence of length 7n-3 from one of length n.  Sequences that are very(2,1) were called very odd sequences by Inglis and Wiseman [2], who showed further that very(2,1) sequences of length n exist if and only if the order of 2 is odd in the multiplicative group of integers modulo 2n-1.

As an example of a very(2,1) sequence we give
a = 101011100011, of length 12, found by Alles in showing that Pelikan's conjecture is false.  The corresponding sequence of 's is 7,3,3,1,3,3,3,1,1,1,1,1, showing that a is very(2,1).

The values of n for which there exists a very(2,1) sequence were determined by Alles by a systematic search for n up to 50 and later extended by using the Inglis and Wiseman condition mentioned above.  The sequence of such values begins {1,4,12,16,24,25,36,37,40,45,52,64,76,81,...} and is sequence A053006 in the Online Encyclopedia of Integer Sequences [4].

2. Very(3,r) Sequences.

We now consider very(3,1) and very(3,2) sequences.  The existence of such sequences can be seen from the example
a = 112102 with corresponding A = {11,5,5,5,2,2} ≡ {2,2,2,2,2,2} (mod 3), showing that a is a very(3,2) sequence.  A systematic computer search finds that the sequences of lengths n for which very(3,r) sequences exist begin:

Lengths of very(3,1) sequences:  {1,5,7,17,35,...},
Lengths of very(3,2) sequences: {2,6,12,14,20,24,30,36,...}.

An open question immediately arises: do very(3,r) sequences always have a length with the same even/odd parity as r?

We now look at a partial listing of some very(3,r) sequences:
very(3,1):
= 1
very(3,2):
= 12
very(3,1):
= 12021
very(3,2):
= 12021000021012

It is apparent that

= (2)

= 0(2)

= 0000(2),

where 2
x denotes (2,...,2), reduced modulo 3, for a sequence x of length l, and where juxtaposition means concatenation.  This suggests the following question: Can a longer very(3,3-r) sequence always be constructed from a very(3,r) sequence, where r = 1,2?  We will answer this affirmatively in the next section.

3.  Constructing Longer Very(3,r) Sequences.

Here and in the following we will take the multiple s
a, where s is an integer and a is a very(b,r) sequence, to mean multiplying each term of a by s and then reducing modulo b.

We now present our main result, answering the question raised at the end of the previous section.

Theorem.  Let a be a very(3,r) sequence of length n, for r=1 or 2, and let z be a sequence of n-1 0's.  Then az(2a) is a very(3,3-r) sequence of length 3n-1.

Proof.  If we write
b = az(2a) and

= ,

we are required to show that ≡ 3-r (mod 3) for k = 0,...,3n-1.  For convenience we break this up into three cases, as follows.

Case 1, 0 ≤ k ≤ n-1.  In this case it is convenient to write

=   + .

But in the first sum, where 1 ≤ i ≤ n-k, we have
= , so the first sum is simply .  In the second sum, = 0 for n+1 ≤ i ≤ 2n-1 and = 2 for 2n ≤ i ≤ 3n-1, so that sum reduces to

4 = 4.

Thus
= 5 ≡ 2r (mod 3).  But since 2r ≡ 3-r (mod 3) for r = 1,2,  we have ≡ 3-r (mod 3) for 0 ≤ k ≤ n-1.

Case 2, n ≤ k ≤ 2n-1.  For this case we write

=

=
+ + .

Since
= 0 for n+1 ≤ i ≤ 2n-1, the summands of the first and third sums are always 0, thus we have

= .

Since n ≤ k ≤ 2n-1 in this case, we have 1 ≤ i ≤ n and 2n ≤ i+k ≤ 3n-1 and thus
= and  = 2 in this sum, which means that

= ().

Now make the change of summation index j = i - (2n-k-1) to get

= 2

=2
.

Thus we again obtain
≡ 2r (mod 3) ≡ 3-r (mod 3) for n ≤ k ≤ 2n-1, i.e.
0 ≤2n-k-1 ≤ n-1.

Case 3, 2n-1 < k ≤ 3n-2.  Since k > 2n-1, we have 3n-k-1 < n and i+k ≥ 2n.  Therefore within the range of summation the summand is always

=  (2).

Thus,
=

=
(2)

= 2
.

So in all cases we have
≡ 2r (mod 3) ≡ 3-r (mod 3),  for 0 ≤ k ≤ 3n-2,  completing the proof.                                  ■

4. Concluding Remarks.

Other properties of very(b,r) sequences have been investigated through systematic computer calculation.  We conclude by presenting some results and a conjecture on very(5,r)sequences.

A systematic search finds the following (partial) lists of very(5,r) sequences:

very(5,1):
= 1
very(5,1):
= 131
very(5,1):
= 1310034300131
and
very(5,4):
= 2
very(5,4):
= 212
very(5,4):
= 2120013100212

These, and other longer sequences suggests the following conjecture.

Conjecture.  Let
a be a very(5,1) (respectively very(5,4)) sequence of length n and let z be a sequence of n-1 0's..  Then az(3a)za is a very(5,1) (respectively very(5,4)) sequence of length 5n-2.

References.

1.  Peter Alles, On a conjecture of J. Pelikan, J. Combin. Theory Ser. A 60 (1992), 312-312.

2.  Nicholas F. J. Inglis and Julian D. A. Wiseman, Very Odd Sequences, J. Combin. Theory Ser. A 71 (1995), 89-96.

3.  F. J. MacWilliams and A. M. Odlyzko, Pelikan's conjecture and cyclotomic cosets, J. Combin. Thepry Ser. A 22 (1977), 110-114.

4. Online Encyclopedia of Integer Sequences, Neil Sloane, Editor,  <http://www.research.att.com/projects/OEIS>.

5. "Problems", Colloq. Math. Soc. Janos. Bolyai, Vol. 10, p. 1549, North-Holland, Amsterdam, 1975.

----------------------------------------------------

Conjecture.  Let a be a very(3,r) sequence of length n, for r=1,2, and let z be a sequence of n-1 0's and w a sequence of 3n-2 0's.  Then aw(2a)zaz(2a)z(2a) is a very(3,3-r) sequence of length 11n-5.  (This has been verified for n=1,6,61,...,7321.)

Conjecture.  Let a be a very(6,r) sequence of length n and let z be a sequence of n-1 0's.  Then (2a)z(4a) is a very(6, 2r mod 6) sequence of length 3n-1.  (This has been verified for n=1,2,5,14,41,..., 3281.)

Conjecture.  Let a be a very(7,r) sequence of length n and let z be a sequence of n-1 0's.  Then az(3a) is a very(7, 10r mod 7) sequence of length 3n-1.  (Verified for n=1,2,5,14,41,122,...,3281.)

Conjecture.  Let a be a very(7,r) sequence of length n and let z be a sequence of n-1 0's.  Then az(5a) is a very(7, 26r mod 7) sequence of length 3n-1.  (Verified for n=1,2,5,14,41,122,...,3281.)

Related Sequences Listed in the OEIS.

Lengths of very(2,1) sequences:  A053006 {1,4,12,16,24,25,36,37,40,...}

Lengths of very(3,r) sequences:  Aaaaaaa {1,2,5,6,7,12,14,17,20,24,...}

Lengths of very(5,r) sequences:  Abbbbbb {1,3,6,10,13,16,...}

Lengths of very(6,r) sequences:  Acccccc {1,2,4,5,6,7,...}

Lengths of very(7,r) sequences;  Adddddd {1,2,4,5,10,11,14,15,...}

Created by Mathematica  (March 25, 2006)