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