Let us take any odd natural $n$ and denote by $H(n)$ the number of ways how $n$ can be represented as the product of factors larger or equal than $3$, where the order of factors matters. For instance, if $n=27$, then $H(n)=4$, since

\[n = 3 \cdot 3 \cdot 3 = 9 \cdot 3 = 3 \cdot 9 = 27.\]

It is known that $H(n) < n^{\eta}$, where $\eta = 1.37779\dots$ is the unique positive real zero of $\left(1-\frac{1}{2^s}\right) \zeta(s)=2$, see Theorem 5 in [1]. Our aim is to show that this upper bound is optimal.

Lemma. For any $\varepsilon>0$ there exist infinitely many odd $n$ such that $H(n) > n^{\eta-\varepsilon}$.

Proof. We will argue along the same lines as in Section 3 of [2], where the similar optimality was obtained for all (even) numbers. First, we notice that

\[\left(1-\frac{1}{2^s}\right) \zeta(s) = \sum_{m=1,~ m ~\text{odd}}^{\infty} \frac{1}{m^s}.\]

Since this expression is a decreasing function of $s$, we take any $\varepsilon>0$ and find that

\[\sum_{m=1,~ m ~\text{odd}}^{\infty} \frac{1}{m^{\eta-\varepsilon}} > 2,\]

and there exists some odd $b$ such that

\[\sum_{m=1,~ m ~\text{odd}}^{b} \frac{1}{m^{\eta-\varepsilon}} > 2.\]

Recalling the monotonicity property and the definition of $\eta$, we can find some $\gamma \in (\eta-\varepsilon, \eta)$ such that

\[\sum_{m=1,~ m ~\text{odd}}^{b} \frac{1}{m^{\gamma}} = 2,\]

which we rewrite as

\[\sum_{m=3,~ m ~\text{odd}}^{b} \frac{1}{m^{\gamma}} = 1.\]

Let us now consider for each odd $m \in [3,b]$ and sufficiently large $t>0$ the function

\[c_m = c_m(t) = \text{floor}\left(\frac{t}{m^\gamma}\right).\]

Notice that

\[\frac{t}{m^\gamma} -1 \leq c_m \leq \frac{t}{m^\gamma},\]

which yields, in particular, that

\begin{equation}\label{eq:summ} \left(\frac{\sum_m c_m}{t}\right)^{\sum_m c_m} \geq \left(\sum_{m=3,~ m ~\text{odd}}^{b} \frac{1}{m^{\gamma}}-\frac{b}{t}\right)^{\sum_m c_m} = \left(1-\frac{b}{t}\right)^{\sum_m c_m} \geq \left(1-\frac{b}{t}\right)^{t} = e^{-b} + o(1). \end{equation}

This inequality will be used slightly below.

Let us define

\[n = \prod_{m=3,~ m ~\text{odd}}^b m^{c_m}.\]

Since $m$ is odd, we see that $n$ is odd. Moreover, clearly, $H(n)$ is bounded from below by the number of multiset permutations

\[v(n) = \frac{(\sum_m c_m)!}{\prod_m c_m!}.\]

Let us estimate $v(n)$ by Stirling’s bounds $\sqrt{2\pi} n^{n+1/2} e^{-n} \leq n! \leq e n^{n+1/2} e^{-n}$:

\[v(n) \geq \frac{\sqrt{2\pi}}{e^b} \sqrt{\frac{\sum_m c_m}{\prod_m c_m}} \prod_i\left(\frac{\sum_m c_m}{c_i}\right)^{c_i}.\]

First, recalling that $c_i \leq \frac{t}{i^\gamma}$ and using \eqref{eq:summ}, we get

\[\prod_i \left(\frac{\sum_m c_m}{c_i}\right)^{c_i} \geq \prod_i \left(\frac{\sum_m c_m}{t}\right)^{c_i} \left(\prod_i i^{c_i}\right)^\gamma = \left(\frac{\sum_m c_m}{t}\right)^{\sum_m c_m} n^\gamma \geq (e^{-b} + o(1)) n^\gamma.\]

Second, arguing exactly as in [2], we deduce that

\[\sqrt{\frac{\sum_m c_m}{\prod_m c_m}} \geq c_b \frac{1}{(\ln n)^\frac{b-5}{4}}\]

for some $c_b > 0$.

Combining the lattter two inequalities, we deduce that

\[H(n) \geq v(n) \geq C \frac{n^\gamma}{(\ln n)^\frac{b-5}{4}} > n^{\eta-\varepsilon}\]

for some $C>0$ and all sufficiently large $t$. The proof is complete.


Bibliography

  1. Chor, B., Lemke, P., & Mador, Z. (2000). On the number of ordered factorizations of natural numbers. Discrete Mathematics, 214(1-3), 123-133. 

  2. Coppersmith, D., & Lewenstein, M. (2005). Constructive bounds on ordered factorizations. SIAM Journal on Discrete Mathematics, 19(2), 301-303.  2