Let $n=p_1^{a_1}\cdots p_k^{a_k}$ be the prime power factorization of the positive integer $n$, with $p_1<\cdots<p_k$ and $a_i>0$. Define $\kappa(n)=(a_1,\dots,a_k)$, the composition type of $n$. Define $\lambda(n)$, the partition type of $n$, to be the weakly decreasing rearrangement $(b_1,b_2,\dots,b_k)$ of $a_1,a_2,\dots,a_k$. For instance, $\kappa(350)=(1,2,1)$ and $\lambda(350)=(2,1,1)$. Are there asymptotic formulas (or at least good bounds) for the number of distinct composition types and partition types among the integers $1,2,\dots,n$?

1$\begingroup$ The amount of composition types is also the amount of numbers $2^{a_1} 3^{a_2} \dots p_n^{a_n}$ with all $a$s nonzero. The amount of partition types is the amount of products of primordials. $\endgroup$– Command MasterApr 21 at 22:10

$\begingroup$ The amount of composition types is $\sum_i \pi(\frac n{p_i\#}, p_i)$. $\endgroup$– Command MasterApr 21 at 22:30

3$\begingroup$ Your count of partition types looks to have a(n)=A085089(n), with a(2^n)=A025488(n) in OEIS. $\endgroup$– Hugo van der SandenApr 22 at 12:48

1$\begingroup$ A025487(n) is the list of the least integers of each "prime signature" (= "partition type") in the question. A note in that OEIS entry states: "Hardy & Ramanujan prove that there are exp((2 Pi + o(1))/sqrt(3) * sqrt(log x/log log x)) members of this sequence up to x". That paper of Hardy and Ramanujan (1917) can be found at imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper34/page1.htm $\endgroup$– Michael LugoApr 22 at 18:01
1 Answer
I do not remember seeing these questions before but Ramanujan's work on highly composite numbers contains related statistics. Obviously the vectors a or b belong to the respective types iff they give the exponents for the k smallest primes, and the associated product is $\leq N$. Therefore a is composition type of an integer $\leq N$ iff $\sum_j a_j \log p_j \leq \log N$. In particular $k\leq (1+o(1))(\log N)/(\log\log N)$. We would therefore guess, using the usual estimate for lattice points inside a kdimensional tetrahedron that the number of such configurations is $(1/k!) \prod_{j=1}^k (\log N)/(\log p_j)$ and this is roughly $e^{(1+o(1))k} = e^{(1+o(1))(\log N)/(\log\log N)}$. Probably this argument can be made into a proof.
To estimate the number of partition types we make this a product of squarefree factorizations of this type, each using only the smallest primes. Therefore let $P_k=p_1\cdots p_k$ so that each $p_1^{b_1}\cdots p_k^{b_k}$ with $b_1\geq b_2\geq \cdots$ equals some $P_1^{c_1}\cdots P_k^{c_k}$ with each $c_i\geq 0$. Therefore c is such a configuration iff $\sum_j c_j \log P_j \leq \log N$, where here $\log P_j=\sum_{i\leq j} \log p_i = (1+o(1)) p_j$ by the prime number theorem so, roughly $\sum_j c_j p_j \leq \log N$. In this case the tetrahedron formula will not give a good estimate. This appears to be a more standard partition type problem and perhaps you know how to proceed. I would guess that to get the right size, moreorless, you would count solutions here with r primes $\leq \frac 1r \log N$ allowing multiplicity, and so the number of solutions is $\binom{\frac 1r \log N+r1}{r1}$; this is maximizimed with $r\approx \sqrt{\log N}$ and so the answer is probably of the shape $e^{c\sqrt{\log N}}$.

$\begingroup$ though not a definitive answer, it seems worth an acceptance. $e^{c\sqrt{\log N}}$ is reasonable since $\sum a_i$ tends to be of the order $\log N$, and the number of partitions of $\log N$ is $e^{c\sqrt{\log N}+o(\sqrt{\log N})}$. $\endgroup$ Apr 24 at 19:21