A050370 Number of ways to factor n into composite factors.

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

Offset

1,16

Comments

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

N. J. A. Sloane, Transforms

Formula

Dirichlet g.f.: Product_{n is composite}(1/(1-1/n^s)).

Moebius transform of A001055. - Vladeta Jovovic, Mar 17 2004

Maple

with(numtheory):
g:= proc(n, k) option remember; `if`(n>k, 0, 1)+
      `if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d)),
         d=divisors(n) minus {1, n}))
    end:
a:= proc(n) a(n):= add(mobius(n/d)*g(d$2), d=divisors(n)) end:
seq(a(n), n=1..100);  # Alois P. Heinz, May 16 2014

Mathematica

g[n_, k_] := g[n, k] = If[n > k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d > k, 0, g[n/d, d]], {d, Divisors[n] ~Complement~ {1, n}}]]; a[n_] := Sum[ MoebiusMu[n/d]*g[d, d], {d, Divisors[n]}]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 23 2017, after Alois P. Heinz *)

Prog

(Python)
from sympy.core.cache import cacheit
from sympy import mobius, divisors, isprime
@cacheit
def g(n, k): return (0 if n>k else 1) + (0 if isprime(n) else sum((0 if d>k else g(n//d, d)) for d in divisors(n)[1:-1]))
def a(n): return sum(mobius(n//d)*g(d, d) for d in divisors(n))
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Aug 19 2017, after Maple code

Crossrefs

Cf. A001055, A002808, A050371, A050372, A050373, A050374, A050375.

a(p^k)=A002865. a(A002110)=A000296.

Sequence in context: A147768 A167746 A360616 * A050374 A238877 A047886

Adjacent sequences: A050367 A050368 A050369 * A050371 A050372 A050373

Keyword

nonn

Author

Christian G. Bower, Nov 15 1999

Status

approved