A050354 Number of ordered factorizations of n with one level of parentheses.

1, 1, 1, 3, 1, 5, 1, 9, 3, 5, 1, 21, 1, 5, 5, 27, 1, 21, 1, 21, 5, 5, 1, 81, 3, 5, 9, 21, 1, 37, 1, 81, 5, 5, 5, 111, 1, 5, 5, 81, 1, 37, 1, 21, 21, 5, 1, 297, 3, 21, 5, 21, 1, 81, 5, 81, 5, 5, 1, 201, 1, 5, 21, 243, 5, 37, 1, 21, 5, 37, 1, 513, 1, 5, 21, 21, 5, 37, 1, 297, 27, 5, 1, 201

Offset: 1

Author

Christian G. Bower, Oct 15 1999

Keywords

• nonn

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).

Dirichlet inverse of (A074206*A153881). - Mats Granvik, Jan 12 2009

Examples

			For n=6, we have (6) = (3*2) = (2*3) = (3)*(2) = (2)*(3), thus a(6) = 5.
		

Links

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

Crossrefs

Cf. A002033, A050351, A050352, A050353, A050355, A050356, A050357, A050358, A050359.

Programs

Mathematica

A[n_]:=If[n==1, n/2, 2*Sum[If[dIndranil Ghosh, May 19 2017 *)

PARI

A050354aux(n) = if(1==n,n/2, 2*sumdiv(n,d, if(dA050354aux(d), 0)));
A050354(n) = if(1==n,n,A050354aux(n)); \\ Antti Karttunen, May 19 2017, after Jovovic's general recurrence.

Sage

def A(n): return 1/2 if n==1 else 2*sum(A(d) for d in divisors(n) if dIndranil Ghosh, May 19 2017, after Antti Karttunen's PARI program

Formula

Dirichlet g.f.: (2-zeta(s))/(3-2*zeta(s)).

Recurrence for number of ordered factorizations of n with k-1 levels of parentheses is a(n) = k*Sum_{d|n, d1, a(1)= 1/k. - Vladeta Jovovic, May 25 2005

a(p^k) = 3^(k-1).

a(A002110(n)) = A050351(n).

Sum_{k=1..n} a(k) ~ -n^r / (4*r*Zeta'(r)), where r = 2.185285451787482231198145140899733642292971552057774261555354324536... is the root of the equation Zeta(r) = 3/2. - Vaclav Kotesovec, Feb 02 2019

Extensions

Duplicate comment removed by R. J. Mathar, Jul 15 2010