A319786 Number of factorizations of n where no two factors are relatively prime.

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 2, 2, 1, 1, 7, 2, 2, 1, 2, 1, 4, 1, 4, 1, 1, 1, 3, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 7, 1, 1, 2, 2, 1, 1, 1, 7, 5, 1, 1, 3, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 12, 1, 2, 2, 4, 1, 1, 1, 4, 1

Offset

1,4

Comments

First differs from A305193 at a(36) = 4, A305193(36) = 5.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Nov 07 2018

Links

Antti Karttunen, Table of n, a(n) for n = 1..11520

Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Index entries for sequences computed from exponents in factorization of n

Example

The a(48) = 7 factorizations are (2*2*2*6), (2*2*12), (2*4*6), (2*24), (4*12), (6*8), (48).

Mathematica

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], !Or@@CoprimeQ@@@Subsets[#, {2}]&]], {n, 100}]

Prog

(PARI) A319786(n, m=n, facs=List([])) = if(1==n, (1!=gcd(Vec(facs))), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs, d); s += A319786(n/d, d, newfacs))); (s)); \\ Antti Karttunen, Nov 07 2018

Crossrefs

Cf. A001055, A007716, A045778, A049311, A162247, A281116, A283877, A305193, A305854, A306006, A316980, A318749.

Cf. A319755, A319759, A319760, A319765, A319779, A319787, A319782, A319789.

Sequence in context: A351219 A328855 A327658 * A321271 A305193 A038538

Adjacent sequences: A319783 A319784 A319785 * A319787 A319788 A319789

Keyword

nonn

Author

Gus Wiseman, Sep 27 2018

Extensions

More terms from Antti Karttunen, Nov 07 2018

Status

approved