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

Author

Emanuel Landeholm, Jul 02 2021

Keywords

• nonn

Examples

			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.
		

Crossrefs

Cf. A220073.

Programs

PARI

a(n) = my(h=n>>1); n - #permcycles(vectorsmall(n,i, abs(2*i-n) + (i<=h))); \\ Kevin Ryde, Jul 23 2021

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="")