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

Author

Seiichi Manyama, Jun 07 2022

Keywords

• nonn

Links

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

Crossrefs

Cf. A320843.

Programs

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

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)

Formula

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

Extensions

More terms from Rémy Sigrist, Jun 07 2022