cp's OEIS Frontend

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

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