5
$\begingroup$

A highly composite number is a natural number $n\ge 1$, such that $t(m)<t(n)$ for all $m$ with $1\le m<n$ , where $t(n)$ is the number of divisors of $n$.

The link shows that the prime factorization of such a number $n$ contains non-increasing exponents and contains all primes upto the largest prime factor of $n$.

It is also claimed that for every $n>36$ the last exponent is always $1$, in other words, if $p$ is the largest prime factor of a highly composite number $n>36$, then $p^2$ does not divide $n$.

How can I prove this ?

The largest highly composite number not divisible by $9$, seems to be $$1680=2^4\cdot 3\cdot 5\cdot 7$$

Is this true, and how can I prove it ?

Finally

Given the sequence of the exponents, is there an efficient method to determine whether the sequence corresponds to a highly composite number ?

It is clear that it is sufficient to test the numbers corresponding to a non-increasing sequence and that the length is bounded by the smallest primorial exceeding the given number $n$. But for large $n$, many such sequences have to be checked.

Just for the sake of curiousity : What is the largest known highly composite number ?

$\endgroup$
2
$\begingroup$

Answer to the second question:

Suppose that $n>1680$ is highly composite and is not a multiple of $9$. Then: $$n=2^r\cdot 3\cdot 5\cdot\ldots\cdot p_k$$ where $p_k\ge11$, that is, $k\ge 5$

Then $t(n)=(r+1)2^{k-1}$. Define

$$n'=\frac{9n}{p_k}<n$$

Then $$t(n')=(r+1)4\cdot2^{k-3}=t(n)$$

which contradicts the fact that $n$ is highly composite.

$\endgroup$
  • $\begingroup$ We have $a_1\ge a_k$. So , how do you conclude the inequality with $\ge$ just above the line ? $\endgroup$ – Peter Aug 3 '16 at 11:53
  • $\begingroup$ Thank you! I managed to solve question $1$ very similar for my own after I posted my question. The answer to the second question is nice (+1)! $\endgroup$ – Peter Aug 3 '16 at 12:22
  • $\begingroup$ I noticed an error in the proof above the line. Set $a_1=4$ and $a_k=2$, then we get $\frac{(a_1+3)a_k}{(a_1+1)(a_k+1)}=\frac{7}{5}\cdot \frac{2}{3}=\frac{14}{15}<1$ $\endgroup$ – Peter Aug 4 '16 at 0:20
1
$\begingroup$

You do not seem to be aware of the Superior Highly Composite Numbers. This is a subsequence defined by Ramanujan. One may find arbitrarily many of these, in order, by careful programming. I have done this. So, the largest known HC number is some extraordinarily large SHC number.

Meanwhile, G. Robin designed a method (1983) for using two consecutive SHC numbers and filling in all the HC numbers in between. So, fairly difficult task.

$\endgroup$
1
$\begingroup$

Answer to question 1:

Suppose we have $n = 2^{a_1} 3^{a_2} \ldots p_k^{a_k}$ with $a_1 \ge a_2 \ge \ldots \ge a_k \ge 2$, $n > 36$ and $n$ is highly composite. I claim that $a_1 \ge 3$. Suppose $a_1 \le 2$; if $k=2$, then $n \le 2^2 3^2 = 36$, whereas if $k \ge 3$, then $t(\frac{4n}{5}) = \frac{a_1+3}{a_1+1} \cdot \frac{a_3}{a_3+1}\cdot t(n) \ge \frac{5}{3}\cdot\frac{2}{3}\cdot t(n) > t(n)$, so $n$ is not highly composite.

But then $t(\frac{p_{k+1} n}{2 p_k}) = 2 \cdot \frac{a_1}{a_1+1} \cdot \frac{a_k}{a_k+1}\cdot t(n) \ge 2 \cdot \frac{3}{4} \cdot \frac{2}{3} \cdot t(n) = t(n)$, while $\frac{p_{k+1} n}{2 p_k} < n$ by Bertrand's Postulate.

$\endgroup$

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.