A317751 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

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.

LINKS

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

Index entries for sequences computed from exponents in factorization of n

EXAMPLE

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

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}]

PROG

(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

CROSSREFS

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

Cf. A317748, A317752, A317755, A317757.

Sequence in context: A333749 A238949 A076755 * A106490 A349281 A372502

Adjacent sequences: A317748 A317749 A317750 * A317752 A317753 A317754

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 06 2018

EXTENSIONS

More terms from Antti Karttunen, Sep 08 2018

STATUS

approved