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$?
$\begingroup$
$\endgroup$
4
asked Apr 21 at 19:39
-
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$– Daniel WeberCommented Apr 21 at 22:10
-
$\begingroup$ The amount of composition types is $\sum_i \pi(\frac n{p_i\#}, p_i)$. $\endgroup$– Daniel WeberCommented 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$– Hugo van der SandenCommented Apr 22 at 12:48
-
3$\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 LugoCommented Apr 22 at 18:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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}}$.
-
$\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$ Commented Apr 24 at 19:21
$\begingroup$
$\endgroup$
Let M(p) denote the primorial of p, that is, the product of all primes up to p. This is sometimes denoted p#. So, for example, M(5) = 30. Say an integer n is "compact" if its largest squarefree divisor is a primorial. For example, 12 and 18 are compact, but 15 is not. For the first problem, we are to count the number of compact numbers up to N. This is precisely the sum of Psi(N/M(p),p) where p runs over the primes p with M(p) <= N and Psi(x,y) counts the number of y-smooth numbers up to x, that is, the number of n <= x with all prime factors of n at most y.
As noted by others, the prime number theorem implies that M(p) = e^{(1+o(1))p}, so that M(p) <= N when p <= (1+o(1))log N. So, the number of compact numbers up to N is within a factor log N of the maximum value of Psi(N/M(p),p). One can then appeal to the "Z-theorem" of DeBruijn, which is Theorem 1 in https://pure.tue.nl/ws/portalfiles/portal/2158712/597534.pdf and see that the maximum occurs when p = (1/2+o(1))log N. So the number of compact integers up to N is 2^{(1+o(1))log N/loglog N}.
One may be able to fine tune this argument and get an asymptotic formula using a paper of Hildebrand and Tenenbaum, "On integers free of large prime factors" in Trans. Amer. Math. Soc. 296 (1986), 265--290. By the way, the sequence of compact numbers is found at https://oeis.org/A055932 .
For the partition problem, as Granville says, this is the number of multiplicative partitions of numbers <= N into primorials. Actually, as Lugo points out this was worked out by Hardy and Ramanujan. They get that the count is exp((2 pi/sqrt{3} +o(1))(log N/loglog N)^{1/2}). This count is closely related to the number of prime partitions of numbers up to log N (since log M(p) is approximately p), and so it may be possible to get a true asymptotic formula, or at least a better error term for the log of the count, using a relatively recent result of Vaughan: https://link.springer.com/article/10.1007/s11139-007-9037-5 which has a corrigendum: https://link.springer.com/article/10.1007/s11139-017-9929-y
