A317751 Number of divisors d of n such that there exists a factorization of n into factors > 1 with GCD d.

0, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 3, 2, 2, 2, 3, 1, 2, 1, 3, 2, 2, 2, 5, 1, 2, 2, 3, 1, 2, 1, 3, 3, 2, 1, 4, 2, 3, 2, 3, 1, 3, 2, 3, 2, 2, 1, 3, 1, 2, 3, 4, 2, 2, 1, 3, 2, 2, 1, 5, 1, 2, 3, 3, 2, 2, 1, 4, 3, 2, 1, 3, 2, 2, 2, 3, 1, 3, 2, 3, 2, 2, 2, 4, 1, 3, 3, 5, 1, 2, 1, 3, 2

Offset: 1

Author

Gus Wiseman, Aug 06 2018

Keywords

• nonn

Comments

Also the number of distinct possible GCDs of factorizations of n into factors > 1.

Also the number of nonzero terms in row n of A317748.

a(prime^n) = A008619(n).

If n is squarefree and composite, a(n) = 2.

Examples

			The divisors of 36 that are possible GCDs of factorizations of 36 are {1, 2, 3, 6, 36}, so a(36) = 5.
		

Links

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

Crossrefs

Cf. A000005, A000837, A001055, A014963, A045778, A050370, A162247, A281116, A289509.

Cf. A317748, A317752, A317755, A317757.

Programs

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
goc[n_,m_]:=Length[Select[facs[n],And[And@@(Divisible[#,m]&/@#),GCD@@(#/m)==1]&]];
Table[Length[Select[Divisors[n],goc[n,#]!=0&]],{n,100}]

PARI

A317751aux(n, m, facs, gcds) = if(1==n, setunion([gcd(Vec(facs))],gcds), my(newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); gcds = setunion(gcds,A317751aux(n/d, d, newfacs, gcds)))); (gcds));
A317751(n) = if(1==n,0,length(A317751aux(n, n, List([]), Set([])))); \\ Antti Karttunen, Sep 08 2018

Extensions

More terms from Antti Karttunen, Sep 08 2018