A293900 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

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

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

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

EXAMPLE

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

CROSSREFS

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

Cf. also A114717, A119842.