A293900 -id:A293900 - 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

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1e_2, e_1e_3, e_2e_3, e_1e_2e_3, ..., e_1e_2...e_k}.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 6, 2, 1, 1, 4, 1, 1, 1, 24, 1, 4, 1, 4, 1, 1, 1, 36, 2, 1, 6, 4, 1, 1, 1, 120, 1, 1, 1, 96, 1, 1, 1, 36, 1, 1, 1, 4, 4, 1, 1, 576, 2, 4, 1, 4, 1, 36, 1, 36, 1, 1, 1, 16, 1, 1, 4, 720, 1, 1, 1, 4, 1, 1, 1, 8640, 1, 1, 4, 4, 1, 1, 1, 576, 24, 1, 1, 16, 1, 1, 1, 36, 1, 16, 1, 4, 1, 1, 1, 14400, 1, 4, 4, 96, 1, 1, 1, 36, 1

Offset: 1

Antti Karttunen, Oct 22 2017

nonn

a(1) = 1 (an empty product).

			For n = 36 = 2^2 * 3^2 the combinations of the exponents are [], [2] (as exponent of 2), [2] (as exponent of 3) and [2, 2]. Taking products of these multisets we get 1 (as an empty product), 2, 2 and 4. Thus a(36) = 1! * 2! * 2! * 4! = 1*2*2*24 = 96.
For n = 72 = 2^3 * 3^2 the combinations of the exponents are [], [2], [3] and [2, 3]. Taking products of these multisets we get 1, 2, 3 and 6. Thus a(72) = 1! * 2! * 3! * 6! = 1*2*6*720 = 8640.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences computed from exponents in factorization of n

Cf. A000142, A163820, A293900.

Array[Apply[Times, Map[Times @@ # &, Subsets@ FactorInteger[#][[All, -1]]]!] &, 105] (* Michael De Vlieger, Oct 23 2017 *)

A293902(n) = { my(exp_combos=powerset(factor(n)[, 2]), m=1); for(i=1,#exp_combos,m *= vecproduct(exp_combos[i])!); m; };
vecproduct(v) = { my(m=1); for(i=1,#v,m *= v[i]); m; };
powerset(v) = { my(siz=2^length(v),pv=vector(siz)); for(i=0,siz-1,pv[i+1] = choosebybits(v,i)); pv; };
choosebybits(v,m) = { my(s=vector(hammingweight(m)),i=j=1); while(m>0,if(m%2,s[j] = v[i];j++); i++; m >>= 1); s; };

(define (A293902 n) (if (= 1 n) n (/ (A163820 n) (A293900 n))))

For n = p^k * q * ... * r (with only one of the prime factors occurring multiple times), a(n) = A000142(k)^(2^(A001221(n)-1)).
a(p^n) = A000142(n), for any prime p.
For n > 1, a(n) = A163820(n) / A293900(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

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1e_2, e_1e_3, e_2e_3, e_1e_2e_3, ..., e_1e_2...e_k}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

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

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1*e_2, e_1*e_3, e_2*e_3, e_1*e_2*e_3, ..., e_1*e_2*...*e_k}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A293902 If n = p_1^e_1 * ... * p_k^e_k, p_1, ..., p_k primes, then a(n) = Product c! where c ranges over products of all combinations of exponents e_1, ..., e_k as {e_1, e_1e_2, e_1e_3, e_2e_3, e_1e_2e_3, ..., e_1e_2...e_k}.