21
$\begingroup$

Of course, following the rules found by Ramanujan, such a highly composite number would need to factorize into all primes ascending up to 9999991 (with descending powers as the primes progress) so the highly composite number would be insanely large.

However a highly composite number needs more factors than all other numbers before it, so surely any number with very large prime factors like 9999991 is automatically at a disadvantage?

So is there a limit to the size of the largest prime factor of a highly composite number, or is it limitless? Is there even a way to know?

$\endgroup$
42
$\begingroup$

Yes, every prime occurs as a prime factor of a highly composite number. Suppose towards a contradiction that it does not; then let $p_n$ be the least prime which does not occur as a factor. Note that this means a highly composite number cannot contain any primes higher than $p_n$ either, since switching out such a prime for $p_n$ gives a smaller number with the same number of divisors. Thus, this would mean that all highly composite numbers are of the form $$ 2^{k_1} \cdot 3^{k_2} \cdots p_{n-1}^{k_{n-1}}. $$ Since there are infinitely many highly composite numbers, at least one of the values $k_i$ must be unbounded; hence, there is a prime $p_i$ and a highly composite number such that $p_n < p_i^{\lfloor k_i/3 \rfloor }$. But now note that removing $\lfloor k_i/3\rfloor$ copies of the prime $p_i$ from this number lowers the total number of divisors by less than $1/3$, while adding the prime $p_n$ doubles its number of divisors. This contradicts the assumption that this was the prime factorization of a highly composite number.

Thus, $p_n$ occurs in the prime factorization of a highly composite number.

Edit: Since this question has received so much attention, I feel like it might be worth explaining some of the intuition behind this answer. Recall, a highly composite number is a number which has more divisors than any number before it. Now, if $$ p_1^{k_1} \cdots p_n^{k_n} $$ is any prime factorization of a number, then that number will have \begin{equation} \qquad\qquad\qquad\qquad\qquad(1 + k_1) \cdots (1 + k_n)\qquad\qquad\qquad\qquad(1) \end{equation} divisors: namely, for every prime $p_i$ a divisor can include that prime $0, 1, \ldots, k_i$ times, which gives $1 + k_i$ options. Note that the primes don't really factor into this anymore; swapping out all copies of a prime with a prime that did not yet occur in the number leaves the $k_i$ and therefore the number of divisors unchanged.

Of course, which primes occur in the number does matter for the size of the number: higher primes give a higher number.

Thus, we think of constructing highly composite numbers as a sort of optimization problem: by multiplying by a new prime factor, we "buy" some new divisors, at the "expense" of making the number larger.

At first, we use low prime factors for that; multiplying by 2, 3, 5 is much "cheaper" than multiplying by 9999991. However, there is a law of diminishing returns. The first time you add a prime factor, you double the number of divisors: in formula (1), a factor $(1 + 0)$ is replaced by one of the form $(1 + 1)$. The second time you do it, a factor $(1 + 1)$ is replaced by $(1 + 2)$, providing only a multiplier of $\frac32$ to the number of divisors.

So, the more and more of the same prime factor you add, the less returns you get off that. If you keep it up long enough, higher primes become more "lucrative". Eventually, you will have exhausted so much of the usefulness of all primes below 9999991, that it becomes optimal to add the prime factor 9999991. The proof just makes this precise. With a little more fidgeting, you can prove that in fact every number, not just every prime, divides a highly composite number.

$\endgroup$
  • $\begingroup$ it may be convenient to notice that power of 2 has to be unbounded (since it's bigger then all others) $\endgroup$ – RiaD Jan 22 '18 at 0:35
12
$\begingroup$

Given a prime $p,$ there is always a highly composite number which has $p$ as a factor. In fact, there is always a highly composite number for which $p$ is the largest prime factor. There is a subsequence that Ramanujan called the Superior Highly Composite Numbers. These numbers are always highly composite. Given a real $\delta > 0,$ we construct $$ N_\delta = \prod_{i=1}^\infty p_i^{a_i},$$ where only a finite number of the exponents $a_i$ are nonzero, with specific value $$ a_i = \left\lfloor \frac{1}{p_i^\delta - 1} \right\rfloor. $$ The smallest SHC number which is divisible by prime $9999991$ uses $$ \delta = \frac{\log 2}{ \log 9999991} \approx 0.043004. $$ I calculate that the exponent of the prime $2$ is $33,$ exponent of the prime $3$ is $20.$ Go Figure.

Let's see, the number $N_\delta$ is, very roughly, $e^{9999991} \approx 10^{4342941}$

$\endgroup$
6
$\begingroup$

We can even estimate the size of the first highly composite number that includes $9999991$ as a factor. Write $N=2^{k_1} \cdot 3^{k_2} \cdots p_{n-1}^{k_{n-1}}.$ where $p_{n-1}$ is the prime just before $9999991$. The number of factors of $N$ is $(k_1+1)(k_2+1)\ldots (k_{n-1}+1)$. We want to compare the number of factors of $9999991N$ with the number of factors we can get by multiplying $N$ by a collection of smaller primes that multiply to about $9999991.$ If we increase $k_i$ by $1$, including potentially increasing $k_n$ from $0$ to $1$, we multiply the number of factors by $\frac {k_i+2}{k_i+1}$ or increase the log of the number of factors by $\log \frac {k_i+2}{k_i+1}$. We increase the log of $N$ by $\log p_i$, so the gain in $\frac {\log \text { factors}}{\log N}$ is $\frac {\log \frac {k_i+2}{k_i+1}}{\log p_i}\approx \frac {\frac 1{k_i+1}}{\log p_i}$ and we assume this is roughly constant over all the $k_i$ or $k_i=\frac c{\log p_i}$ This shows that $k_1$, the exponent on $2$ is about $\frac {\log 9999991}{\log 2} \approx 23$ We can assess the exponents on all the intervening primes similarly.

$\endgroup$
  • $\begingroup$ While interesting, this isn't really an answer to the question so much as 'further reading' given the answer. $\endgroup$ – the dark wanderer Mar 28 '17 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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