A354830 a(n) is the number of permutations p of [n] such that gcd(i, p(i)) > 1 for 2 <= i <= n.

1, 1, 1, 1, 2, 2, 8, 8, 30, 72, 408, 408, 4104, 4104, 29640, 208704, 1437312, 1437312, 22653504, 22653504, 318695040, 2686493376, 27628410816, 27628410816, 575372874240, 1775480841216, 21115550048256, 132879856582656, 2321256928702464, 2321256928702464, 83095013944442880

Offset

0,5

Links

Table of n, a(n) for n=0..30.

Carl Pomerance, Coprime permutations, arXiv:2203.03085 [math.NT], 2022. See TABLE 3.

Formula

a(p) = a(p-1) for primes p.

Prog

(Ruby)
def search(a, num, n)
  if num == n + 1
    @cnt += 1
  else
    (1..n).each{|i|
      if a[i] == 0
        if i == 1 || i.gcd(num) > 1
          a[i] = num
          search(a, num + 1, n)
          a[i] = 0
        end
      end
    }
  end
end
def A(n)
  a = [0] * (n + 1)
  @cnt = 0
  search(a, 1, n)
  @cnt
end
def A354830(n)
  (0..n).map{|i| A(i)}
end
p A354830(15)
(PARI) a(n) = { my (v=select(x -> (!isprime(x)) || (2*x<=n), [2..n])); matpermanent(matrix(#v, #v, i, j, gcd(v[i], v[j])>1)) } \\ Rémy Sigrist, Jun 07 2022

Crossrefs

Cf. A320843.

Sequence in context: A120544 A155950 A162959 * A158302 A007083 A281019

Adjacent sequences: A354827 A354828 A354829 * A354831 A354832 A354833

Keyword

nonn

Author

Seiichi Manyama, Jun 07 2022

Extensions

More terms from Rémy Sigrist, Jun 07 2022

Status

approved