login
a(n) is the length of a shortest integer sequence on a circle containing all permutations of the set {1, 2, ..., n} as subsequences.
2

%I #19 Jun 29 2024 10:48:13

%S 2,4,8,12,17

%N a(n) is the length of a shortest integer sequence on a circle containing all permutations of the set {1, 2, ..., n} as subsequences.

%C This is called r(n) in Lecouturier and Zmiaikou.

%H Emmanuel Lecouturier and David Zmiaikou, <a href="https://doi.org/10.1016/j.disc.2011.12.027">On a conjecture of H. Gupta</a>, Discrete Math. 312, 8(2012), 1444-1452.

%F a(n) <= n^2/2 if n is even.

%F a(n) < n^2/2 + n/4 -1 if n is odd.

%e From _Chai Wah Wu_, Jun 27 2024: (Start)

%e Sequence corresponding to each n (which may not be unique):

%e n = 2: 12

%e n = 3: 1232

%e n = 4: 12341214

%e n = 5: 123451215432

%e n = 6: 12345612156431265

%e (End)

%o (Python)

%o from itertools import count, permutations, product

%o def is_subseq(s, p):

%o while s != "" and p != "":

%o if p[0] == s[0]: s = s[1:]

%o p = p[1:]

%o return s == ""

%o def a(n):

%o digits = "".join(str(i) for i in range(n))

%o for k in count(0):

%o for p in product(digits, repeat=k):

%o r, c_all = (digits + "".join(p))*2, True

%o for q in permutations(digits):

%o w = "".join(q)

%o if not any(is_subseq(w, r[j:j+n+k]) for j in range(n+k)):

%o c_all = False

%o break

%o if c_all:

%o return n+k

%o print([a(n) for n in range(2, 6)]) # _Michael S. Branicky_, Jun 17 2024

%Y Cf. A062714.

%K nonn,hard,more

%O 2,1

%A _Michel Marcus_, Jun 15 2024