A293900 - OEIS

%I #17 Oct 23 2017 20:08:42

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

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

%U 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

%N 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.

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

%H Antti Karttunen, <a href="/A293900/b293900.txt">Table of n, a(n) for n = 1..179</a> (based on b-file of A163820 provided by David A. Corneth)

%H Antti Karttunen, <a href="/A293900/a293900_1.txt">Scheme-program for computing this sequence</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

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

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

%e 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):

%e   [2, 4, 6, 3, 12],

%e   [2, 4, 6, 12, 3],

%e   [2, 6, 3, 12, 4],

%e   [2, 6, 4, 12, 3],

%e   [3, 6, 2, 4, 12],

%e   [3, 6, 2, 12, 4],

%e   [3, 6, 12, 2, 4],

%e   [6, 2, 4, 12, 3],

%e   [6, 3, 12, 2, 4].

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

%Y Cf. also A114717, A119842.

%K nonn

%O 1,6

%A _Antti Karttunen_, Oct 22 2017