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.

2, 4, 8, 12, 17

Offset: 2

Author

Michel Marcus, Jun 15 2024

Keywords

• nonn
• hard
• more

Comments

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

Examples

			From _Chai Wah Wu_, Jun 27 2024: (Start)
Sequence corresponding to each n (which may not be unique):
n = 2: 12
n = 3: 1232
n = 4: 12341214
n = 5: 123451215432
n = 6: 12345612156431265
(End)
		

Links

• Emmanuel Lecouturier and David Zmiaikou, On a conjecture of H. Gupta, Discrete Math. 312, 8(2012), 1444-1452.

Crossrefs

Cf. A062714.

Programs

Python

from itertools import count, permutations, product
def is_subseq(s, p):
    while s != "" and p != "":
        if p[0] == s[0]: s = s[1:]
        p = p[1:]
    return s == ""
def a(n):
    digits = "".join(str(i) for i in range(n))
    for k in count(0):
        for p in product(digits, repeat=k):
            r, c_all = (digits + "".join(p))*2, True
            for q in permutations(digits):
                w = "".join(q)
                if not any(is_subseq(w, r[j:j+n+k]) for j in range(n+k)):
                    c_all = False
                    break
            if c_all:
                return n+k
print([a(n) for n in range(2, 6)]) # Michael S. Branicky, Jun 17 2024

Formula

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

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