A161810 - OEIS

%I #9 Jan 11 2020 19:51:46

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

%N 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.

%C 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.

%F 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

%e 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.

%e From _Bert Dobbelaere_, Apr 18 2019: (Start)

%e Lexicographically earliest solutions represented as digit strings.

%e n  a(n)

%e 1    1    0

%e 2    3    010

%e 3    7    0102010

%e 4   16    0130102013101201

%e 5   33    010214243213143040102142432131430

%e 6   35    01024021240241402401024021240241402

%e 7   47    01021614636032312426404301021614636032312426404

%e 8   61    0120135461316135364357463523745020571465756571764713467127313

%e (End)

%K hard,more,nonn

%O 1,2

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

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

%E a(7)-a(8) from _Bert Dobbelaere_, Apr 18 2019