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,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

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

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

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)

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

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

Sequence in context: A112623 A130675 A319118 * A284465 A327899 A276157

Adjacent sequences: A163817 A163818 A163819 * A163821 A163822 A163823

Keyword

nonn

Author

Leroy Quet, Aug 04 2009

Extensions

Definition corrected by Leroy Quet, Aug 15 2009

Edited and extended by Max Alekseyev, Jun 13 2011

Status

approved