%I #16 Jun 07 2022 13:00:11
%S 1,1,1,1,2,2,8,8,30,72,408,408,4104,4104,29640,208704,1437312,1437312,
%T 22653504,22653504,318695040,2686493376,27628410816,27628410816,
%U 575372874240,1775480841216,21115550048256,132879856582656,2321256928702464,2321256928702464,83095013944442880
%N a(n) is the number of permutations p of [n] such that gcd(i, p(i)) > 1 for 2 <= i <= n.
%H Carl Pomerance, <a href="https://arxiv.org/abs/2203.03085">Coprime permutations</a>, arXiv:2203.03085 [math.NT], 2022. See TABLE 3.
%F a(p) = a(p-1) for primes p.
%o (Ruby)
%o def search(a, num, n)
%o if num == n + 1
%o @cnt += 1
%o else
%o (1..n).each{|i|
%o if a[i] == 0
%o if i == 1 || i.gcd(num) > 1
%o a[i] = num
%o search(a, num + 1, n)
%o a[i] = 0
%o end
%o end
%o }
%o end
%o end
%o def A(n)
%o a = [0] * (n + 1)
%o @cnt = 0
%o search(a, 1, n)
%o @cnt
%o end
%o def A354830(n)
%o (0..n).map{|i| A(i)}
%o end
%o p A354830(15)
%o (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
%Y Cf. A320843.
%K nonn
%O 0,5
%A _Seiichi Manyama_, Jun 07 2022
%E More terms from _Rémy Sigrist_, Jun 07 2022
|