

A163820


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


4



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


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


LINKS



FORMULA

a(p) = 1 for all primes p. a(p*q) = 2 for all pairs of (not necessarily distinct) primes p and q.
a(p^n) = A000142(n), for all primes p.
(End)


EXAMPLE

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.


MATHEMATICA

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


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



