On the number of ordered factorizations of natural numbers Original Research Article

We study the number of ways to factor a natural number n into an ordered product of integers, each factor greater than one, denoted by H(n). This counting function from number theory was shown by Newberg and Naor (Adv. Appl. Math. 14 (1993) 172–183) to be a lower bound on the number of solutions to the so-called probed partial digest problem, which arises in the analysis of data from experiments in molecular biology. Hille (Acta Arith. 2 (1) (1936) 134–144) established a relation between H(n) and the Riemann zeta function ζ. This relation was used by Hille to prove tight asymptotic upper and lower bounds on H(n). In particular, Hille showed an existential lower bound on H(n): For any t<ρ=ζ−1(2)≈1.73 there are infinitely many n which satisfy H(n)>nt. Hille also proved an upper bound on H(n), namely H(n)=O(nρ). In this work, we show an improved upper bound on the function H(n), by proving that for every n, H(n)1 is a constant. One sequence has elements of the form 2ℓ3j, and they satisfy H(ni)⩾niti, where limi→∞ ti=t≈1.43. This t is the maximum constant for sequences whose elements are products of two distinct primes. Another sequence has elements that are products of four distinct primes, and they satisfy H(ni)>nid, where d≈1.6.