A293902 -id:A293902 - cp's OEIS frontend

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

Leroy Quet, Aug 04 2009

nonn

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

			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.

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

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

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

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)

Definition corrected by Leroy Quet, Aug 15 2009

Edited and extended by Max Alekseyev, Jun 13 2011

A293900 Number of permutations of the divisors of n that are greater than 1, in which consecutive elements are not coprime and no divisor d may occur later than any divisor e if e < d and A007947(e) = A007947(d). That is, any subset of divisors sharing the same squarefree part occur always in ascending order inside the permutation.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 9, 1, 2, 2, 1, 1, 9, 1, 9, 2, 2, 1, 40, 1, 2, 1, 9, 1, 348, 1, 1, 2, 2, 2, 110, 1, 2, 2, 40, 1, 348, 1, 9, 9, 2, 1, 175, 1, 9, 2, 9, 1, 40, 2, 40, 2, 2, 1, 138660, 1, 2, 9, 1, 2, 348, 1, 9, 2, 348, 1, 1127, 1, 2, 9, 9, 2, 348, 1, 175, 1, 2, 1, 138660, 2, 2, 2, 40, 1, 138660, 2, 9, 2, 2, 2, 756, 1, 9, 9, 110

Offset: 1

Antti Karttunen, Oct 22 2017

nonn

This is a more restricted variant of A163820, inspired by David A. Corneth's suggestion (personal e-mail) for optimizing its computation.

			The proper divisors of 12 are 2, 3, 4, 6, 12. a(12) = 9 because we can find nine permutations of them such that consecutive elements d and e are not coprime (that is, gcd(d,e) > 1) and where no divisor d is ever followed by divisor e such that A007947(d) = A007947(e) and e < d. These nine allowed permutations are (note that 2 must become before 4 and 6 must become before 12):
  [2, 4, 6, 3, 12],
  [2, 4, 6, 12, 3],
  [2, 6, 3, 12, 4],
  [2, 6, 4, 12, 3],
  [3, 6, 2, 4, 12],
  [3, 6, 2, 12, 4],
  [3, 6, 12, 2, 4],
  [6, 2, 4, 12, 3],
  [6, 3, 12, 2, 4].

Antti Karttunen, Table of n, a(n) for n = 1..179 (based on b-file of A163820 provided by David A. Corneth)
Antti Karttunen, Scheme-program for computing this sequence
Index entries for sequences computed from exponents in factorization of n

Cf. A000961 (positions of 0 and 1's), A163820, A293902.

Cf. also A114717, A119842.

Iff n = p^k for some prime p and k >= 1 [that is, n is a term of A000961 > 1], then a(n) = 1.

a(n) = A163820(n)/A293902(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions