13
$\begingroup$

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$?

$\endgroup$
4
  • 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$ Apr 21 at 22:10
  • $\begingroup$ The amount of composition types is $\sum_i \pi(\frac n{p_i\#}, p_i)$. $\endgroup$ Apr 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$ Apr 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$ Apr 22 at 18:01

1 Answer 1

13
$\begingroup$

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 k-dimensional 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, more-or-less, 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+r-1}{r-1}$; this is maximizimed with $r\approx \sqrt{\log N}$ and so the answer is probably of the shape $e^{c\sqrt{\log N}}$.

$\endgroup$
1
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.