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)