A318749 Number of pairwise relatively nonprime strict factorizations of n (no two factors are coprime).

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 5, 1, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 3, 1, 1, 2, 4, 1, 1, 1, 2, 1, 1, 1, 5, 1, 1, 2, 2, 1, 1, 1, 5, 2, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 2, 1, 1, 1, 7, 1, 2, 2, 3, 1, 1, 1, 3, 1

Offset: 1

Author

Gus Wiseman, Sep 02 2018

Keywords

• nonn

Comments

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

Examples

			The a(96) = 7 factorizations are (96), (2*48), (4*24), (6*16), (8*12), (2*4*12), (2*6*8).
The a(480) = 18 factorizations:
  (480)
  (2*240) (4*120) (6*80) (8*60) (10*48) (12*40) (16*30) (20*24)
  (2*4*60) (2*6*40) (2*8*30) (2*10*24) (2*12*20) (4*6*20) (4*10*12) (6*8*10)
  (2*4*6*10)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A001055, A045778, A051185, A281116, A303282, A305843, A305854, A317748, A318715, A318717, A318721.

Programs

Mathematica

strfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#1,d]&)/@Select[strfacs[n/d],Min@@#1>d&],{d,Rest[Divisors[n]]}]];
Table[Length[Select[strfacs[n],And@@(GCD[##]>1&)@@@Select[Tuples[#,2],Less@@#&]&]],{n,50}]

PARI

A318749(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 += A318749(n/d, d-1, newfacs))); (s)); \\ Antti Karttunen, Oct 08 2018

Extensions

More terms from Antti Karttunen, Oct 08 2018