A346036 Number of swaps needed to return the recursive transform T(k) = concatenate(reverse(k), len(k) + 1) to the tuple 1, 2, ..., n.

0, 0, 1, 2, 2, 4, 5, 4, 6, 8, 7, 10, 10, 10, 13, 12, 12, 14, 17, 16, 18, 18, 17, 22, 22, 20, 25, 24, 24, 28, 29, 24, 26, 32, 31, 34, 32, 32, 35, 38, 36, 40, 35, 40, 40, 40, 39, 44, 46, 42, 49, 50, 44, 52, 51, 52, 52, 54, 51, 54, 58, 56, 59, 54, 54, 64, 61, 60

Offset

1,4

Links

Table of n, a(n) for n=1..68.

Example

For n=7, the T transforms give tuple 6,4,2,1,3,5,7 (triangle A220073 row 7) which requires a(7) = 5 swaps to return to 1,2,3,4,5,6,7.

Prog

(Python)
def swaps(l, start = 0):
  if len(l) == 0:
    return 0
  n = start + 1
  if l[0] != n:
    for i, x in enumerate(l):
      if x == n:
        l[0], l[i] = l[i], l[0]
        return 1 + swaps(l[1:], n)
    else:
      raise
  else:
    return swaps(l[1:], n)
def T(l):
  n = len(l)
  l.reverse()
  l.append(n + 1)
  return l
if __name__ == "__main__":
  l = [ ]
  for n in range(1, 100):
    l = T(l)
    n_swaps = swaps(l[:])
    print("{}, ".format(n_swaps), end="")
(PARI) a(n) = my(h=n>>1); n - #permcycles(vectorsmall(n, i, abs(2*i-n) + (i<=h))); \\ Kevin Ryde, Jul 23 2021

Crossrefs

Cf. A220073.

Sequence in context: A199088 A293974 A372672 * A138557 A129303 A255368

Adjacent sequences: A346033 A346034 A346035 * A346037 A346038 A346039

Keyword

nonn

Author

Emanuel Landeholm, Jul 02 2021

Status

approved