A161810 a(n) is the maximum possible length of a sequence consisting of integers [0..n-1] such that no two nonempty adjacent segments of the same length have the same sum modulo n.

1, 3, 7, 16, 33, 35, 47, 61

Offset

1,2

Comments

The original source for this sequence was the problem 'perlbrac' in the 2009 USACO Holiday Contest (http://ace.delos.com/HOL09) which asked contestants to find the longest sequences of this type that they possibly could. a(n) is the upper bound on the length of such a sequence for a given n.

Links

Table of n, a(n) for n=1..8.

Formula

Replacing each element x of a solution by ((a x + b) mod n) also gives a solution if gcd(a,n) = 1. - Bert Dobbelaere, Apr 18 2019

Example

For example, in the sequence 0, 1, 2, 1, 0, 1, 2 (length 7) consisting of integers in the range [0..2], no two adjacent segments of equal length (e.g., 0, 1, 2 and 1, 0, 1) have the same sum modulo 3. There is also no longer sequence with this property, hence a(3) = 7.
From Bert Dobbelaere, Apr 18 2019: (Start)
Lexicographically earliest solutions represented as digit strings.
n  a(n)
1    1    0
2    3    010
3    7    0102010
4   16    0130102013101201
5   33    010214243213143040102142432131430
6   35    01024021240241402401024021240241402
7   47    01021614636032312426404301021614636032312426404
8   61    0120135461316135364357463523745020571465756571764713467127313
(End)

Crossrefs

Sequence in context: A376334 A298311 A366527 * A318604 A084631 A219846

Adjacent sequences: A161807 A161808 A161809 * A161811 A161812 A161813

Keyword

hard,more,nonn

Author

Brian Bi (bbi5291(AT)gmail.com), Jun 19 2009

Extensions

Definition and source corrected by Brian Bi (bbi5291(AT)gmail.com), Sep 19 2009

a(7)-a(8) from Bert Dobbelaere, Apr 18 2019

Status

approved