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 2x 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 sa, 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.

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

Addendum

New Conjectures Added 3/20/06.

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)