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.

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

Author

Antti Karttunen, Oct 22 2017

Keywords

• nonn

Comments

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

Examples

			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].
		

Links

• 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

Crossrefs

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

Cf. also A114717, A119842.

Formula

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).