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

%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