Estimating the number of multiplicative partitions (Q1101476): Difference between revisions

Let f(n) be the number of essentially different factorisations of n: for example \(f(12)=4\) since \(12=1.12=2.6=3.4=2.2.3.\) It is proved that \((i)\quad f(n)\leq n(\log n)^{-\alpha}\) for each \(\alpha >0\) and all \(n>n(\alpha)\); \((ii)\quad f(n)\leq (\log n)^{-1}\) for all \(n>1\), \(n\neq 144\). These improve the result f(n)\(\leq n\) already obtained by the authors, in response to a conjecture of \textit{J. F. Hughes} and \textit{J. O. Shallit} [Am. Math. Mon. 90, 468-471 (1983; Zbl 0523.10007)]. An independent asymptotic result of \textit{E. R. Canfield}, \textit{P. Erdős} and \textit{C. Pomerance} [J. Number Theory 17, 1-28 (1983; Zbl 0513.10043)] is stronger than (i) but does not imply (ii).