%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