|
%I #29 May 03 2020 06:03:03
%S 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,
%T 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,
%U 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
%N Number of ways to factor n into composite factors.
%C 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).
%H Alois P. Heinz, <a href="/A050370/b050370.txt">Table of n, a(n) for n = 1..10000</a>
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F Dirichlet g.f.: Product_{n is composite}(1/(1-1/n^s)).
%F Moebius transform of A001055. - _Vladeta Jovovic_, Mar 17 2004
%p with(numtheory):
%p g:= proc(n, k) option remember; `if`(n>k, 0, 1)+
%p `if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d)),
%p d=divisors(n) minus {1, n}))
%p end:
%p a:= proc(n) a(n):= add(mobius(n/d)*g(d$2), d=divisors(n)) end:
%p seq(a(n), n=1..100); # _Alois P. Heinz_, May 16 2014
%t 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_ *)
%o (Python)
%o from sympy.core.cache import cacheit
%o from sympy import mobius, divisors, isprime
%o @cacheit
%o 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]))
%o def a(n): return sum(mobius(n//d)*g(d, d) for d in divisors(n))
%o print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Aug 19 2017, after Maple code
%Y Cf. A001055, A002808, A050371, A050372, A050373, A050374, A050375.
%Y a(p^k)=A002865. a(A002110)=A000296.
%K nonn
%O 1,16
%A _Christian G. Bower_, Nov 15 1999
|
