A163820 Number of permutations of the divisors of n that are greater than 1, in which consecutive elements are not coprime.

0, 1, 1, 2, 1, 2, 1, 6, 2, 2, 1, 36, 1, 2, 2, 24, 1, 36, 1, 36, 2, 2, 1, 1440, 2, 2, 6, 36, 1, 348, 1, 120, 2, 2, 2, 10560, 1, 2, 2, 1440, 1, 348, 1, 36, 36, 2, 1, 100800, 2, 36, 2, 36, 1, 1440, 2, 1440, 2, 2, 1, 2218560, 1, 2, 36, 720, 2, 348, 1, 36, 2, 348, 1, 9737280, 1, 2, 36, 36, 2, 348, 1, 100800, 24, 2, 1, 2218560, 2, 2, 2, 1440, 1, 2218560, 2, 36, 2, 2, 2, 10886400, 1, 36, 36, 10560

Offset: 1

Author

Leroy Quet, Aug 04 2009

Keywords

• nonn

Comments

a(n) depends only on prime signature of n (cf. A025487). So a(60) = a(90) since 60 = 2^2 * 3 * 5 and 90 = 2 * 3^2 * 5 both have prime signature (2,1,1). - Antti Karttunen, Oct 22 2017

As a consequence of the comment above, a(n) = a(A046523(n)). - David A. Corneth, Oct 22 2017

Examples

			The divisors of 12 that are > 1 are 2,3,4,6,12. In the permutations that are counted, 3 cannot be next to 2 or 4. However, a permutation that is among those counted is 6,2,4,12,3. The GCDs of adjacent pairs in this permutation are gcd(6,2)=2, gcd(2,4)=2, gcd(4,12)=4, gcd(12,3)=3. Note that all of these GCDs are > 1.
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..359 (first 119 terms from Antti Karttunen)
• Antti Karttunen, Scheme-program for computing this sequence
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. also A046523, A114717, A119842, A122977, A122978, A293900, A293902.

Programs

Mathematica

Array[Count[Permutations@ Rest@ Divisors[#], ?(NoneTrue[Partition[#, 2, 1], CoprimeQ @@ # &] &)] - Boole[# == 1] &, 59] (* _Michael De Vlieger, Nov 04 2017 *)

Formula

a(p) = 1 for all primes p. a(p*q) = 2 for all pairs of (not necessarily distinct) primes p and q.

From Antti Karttunen, Oct 22 2017: (Start)

a(p^n) = A000142(n), for all primes p.

a(n) = A293900(n)*A293902(n).

(End)

Extensions

Definition corrected by Leroy Quet, Aug 15 2009

Edited and extended by Max Alekseyev, Jun 13 2011