cp's OEIS Frontend

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

%I A373728 #19 Jun 29 2024 10:48:13
%S A373728 2,4,8,12,17
%N A373728 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 A373728 This is called r(n) in Lecouturier and Zmiaikou.
%H A373728 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 A373728 a(n) <= n^2/2 if n is even.
%F A373728 a(n) < n^2/2 + n/4 -1 if n is odd.
%e A373728 From _Chai Wah Wu_, Jun 27 2024: (Start)
%e A373728 Sequence corresponding to each n (which may not be unique):
%e A373728 n = 2: 12
%e A373728 n = 3: 1232
%e A373728 n = 4: 12341214
%e A373728 n = 5: 123451215432
%e A373728 n = 6: 12345612156431265
%e A373728 (End)
%o A373728 (Python)
%o A373728 from itertools import count, permutations, product
%o A373728 def is_subseq(s, p):
%o A373728     while s != "" and p != "":
%o A373728         if p[0] == s[0]: s = s[1:]
%o A373728         p = p[1:]
%o A373728     return s == ""
%o A373728 def a(n):
%o A373728     digits = "".join(str(i) for i in range(n))
%o A373728     for k in count(0):
%o A373728         for p in product(digits, repeat=k):
%o A373728             r, c_all = (digits + "".join(p))*2, True
%o A373728             for q in permutations(digits):
%o A373728                 w = "".join(q)
%o A373728                 if not any(is_subseq(w, r[j:j+n+k]) for j in range(n+k)):
%o A373728                     c_all = False
%o A373728                     break
%o A373728             if c_all:
%o A373728                 return n+k
%o A373728 print([a(n) for n in range(2, 6)]) # _Michael S. Branicky_, Jun 17 2024
%Y A373728 Cf. A062714.
%K A373728 nonn,hard,more
%O A373728 2,1
%A A373728 _Michel Marcus_, Jun 15 2024