6
$\begingroup$

Let $\tau(n)$ denote the number of divisors of $n$ and $p$ prime.

Today in high school I've tried to find a number that is not very big, but has a huge number of divisors (compared to it's size), i.e. $\tau(n)/n$ has to be as big as possible.

Obviously, $0 \leq \tau(1) \leq 1$, since $\tau(1)/1=1$ and $\tau(p)/p=2/p$ (so this can become as small as we want). I have tried some values

  • $\tau(2)/2 = 1$
  • $\tau(3)/3 = 2/3$
  • $\tau(4)/4 = 0.75$
  • $\tau(5)/5 = 0.4$

However, I am wondering whether there is a big(er) number, with a high ratio of divisors? Exists any number that e.g. has again a ratio of 2/3?

Such a number is not in the form $p^x$, since $$ \frac{\tau(p^x)}{p^x} = \frac{x+1}{p^x}, $$ which become smaller and smaller for bigger $p$ or $x$.

Also not $\prod^\omega_i p_i$, since $$ \frac{\tau\left(\prod^\omega_i p_i\right)}{\prod^\omega_i p_i} = \frac{2^\omega}{\prod^\omega_i p_i} = \prod^\omega_i \frac{2}{p}, $$ which also (if I am correct) tends to 0 for bigger $\omega$.

Or does this already show that the ratio $\tau(n)/n$ can be only smaller not bigger for any higher number?

$\endgroup$
5
  • $\begingroup$ Comparing 3 and 4, you can already n example where the ratio can be larger for a larger number, but in general the ratio should go down. I have no proof, but I bet 12 is the last one with a ratio of 1/2 or greater. $\endgroup$
    – Bram28
    Apr 3 '17 at 16:36
  • $\begingroup$ most factors have a cofactor (or the square root of the number), and one of the factors has to be less than or equal to the square root of the number, so there is an upper bound of $2 \times \sqrt(n)$ So therefore 1 million has to have less than or equal to 2000 factors $\endgroup$
    – Cato
    Apr 3 '17 at 16:38
  • $\begingroup$ 6 has ratio 2/3 $\endgroup$ Apr 3 '17 at 16:40
  • $\begingroup$ See also en.wikipedia.org/wiki/Divisor_function#Growth_rate $\endgroup$
    – lhf
    Apr 3 '17 at 16:48
  • 1
    $\begingroup$ $2,4,6,12,24,30,36,48,60,72,\ldots$ each have a higher proportion of divisors than all larger numbers, so are called crowded numbers - see OEIS A066523 - the next is $84$, which might surprise some people $\endgroup$
    – Henry
    Apr 3 '17 at 23:42
7
$\begingroup$

However, I am wondering whether there is a big(er) number, with a high ratio of divisors? Exists any number that e.g. has again a ratio of 2/3?

Yes, $\tau(6)/6 = \frac{2}{3}$

Note that in the best case scenario, $n$ has divisors $1,2,...,\sqrt{n}$ together with their co-factors $\frac{n}{1},\frac{n}{2},...\frac{n}{\sqrt(n)}$, so that's at most $2*\sqrt{n}$ divisors. This should allow you to figure out the upper bound to any number with a certain ratio. (and this also tells you that the ratio, while it may go up or down from number to number, will in general go down)

For example, for a ratio of $\frac{1}{2}$, you have an upper bound of 16, since for $n > 16$, $n$ has less than $n/2$ divisors.

If you try a few numbers, you thus see that 12 will be the last one with a ratio of $\frac{1}{2}$ or more

$\endgroup$
4
  • $\begingroup$ Ok great, and another one? $\endgroup$ Apr 3 '17 at 16:39
  • $\begingroup$ Not after that. 12 will be the last one with ratio 1/2 or greater. $\endgroup$
    – Bram28
    Apr 3 '17 at 16:40
  • $\begingroup$ Oh ok, that's interesting. Why? Can you proof that? $\endgroup$ Apr 3 '17 at 16:41
  • 1
    $\begingroup$ because factors appear in pairs, or otherwise the factor is the square root, and one of the pairs has to be less than the square root e.g x = ab then a or b has to be less than or equal to the square root, giving an upper limit of $2 \sqrt(x)$ for the number of factors or $\frac{2}{\sqrt{x}}$ for $\tau$ $\endgroup$
    – Cato
    Apr 3 '17 at 16:44
3
$\begingroup$

If $n = \prod p_i^{m_i}$ then $\tau (n) = \prod (m_i + 1)$

So we want $\frac {\tau(n)}{n} = \frac{\prod(m_i + 1)}{\prod p_i^{m_i}}$

The actual values of the prime factors are irrelevant to the number of divisors so to get a high ratio we want the primes to be as small as possible. So $p_i$ should be the $i$-th prime. $p_1=2;p_2 = 3;p_3 = 5; etc.$.

Which $p_i$ are raised to which power $m_i$ is irrelevent so to get a high ratio we want the high powers to go to the lowest primes so $m_1 \ge m_2 \ge m_3 ....$.

And obviously as we take higher powers $m_i$ the ratio of $\frac {m_i + 1}{p_i^{m_i}}$ is going to decrease radically.

That's not very precise but it gives a good frame work. For $n = p^m$ the highest ratio will be $n=2^m$ and the ratio is $(m+1)/2^m$ so for $n = 2,4,8,16... $ we have the ratio is $2/2=1,3/4,4/8 = 1/2,5/16, 6/32...$ etc.

For $n = p^mq^k$ the highest ratio will be $n = 2^{m+a}3^m$ and the ratio is $m(m+a)/2^{m+a}3^m$. So for $n = 6;12; 36;24;72;216 etc$; the ratio is $\frac 46;\frac 6{12};\frac 9{36}$ etc.

For no having three prime factors we have $n = 2*3*5; 2^2*3*5;2^2*3^2*5;2^3*3*5$ yields ratios of $\frac {8}{30};\frac{12}{60}; \frac{18}{180};\frac{16}{120} etc.$

Okay, that isn't precise but it's clear that those are the highest ratios.

$\tau(n) = 1$ only if $n = 2$; $\tau(n) = 3/4$ only if $n = 4$; $\tau(n)=2/3$ only if $n = 6$ and $\tau(n)=1/2$ only if $n =8,12$.

$\endgroup$
3
  • $\begingroup$ $84=2^2\times 3 \times 7$ has a higher ratio of $\frac{12}{84}$ than $\frac{18}{180}$ or $\frac{16}{120}$ and is as deserving as being on the list as the others $\endgroup$
    – Henry
    Apr 3 '17 at 23:41
  • $\begingroup$ 60 = 2^2 x 3 x 7 has a higher ratio of 12/60 = 1/5. $\endgroup$
    – fleablood
    Apr 3 '17 at 23:46
  • $\begingroup$ I never said the list was a list of the highest ratios. It obviously isn't. I said it was a framework as to how high we can expect ratios to be.. The low ratios aren't on the list because they are high. They are on the list because they show that we have reached the end of the line $\endgroup$
    – fleablood
    Apr 3 '17 at 23:51
1
$\begingroup$

Well I don't know if such a big number exist or not but I can make a guess how we can get that.

The number of divisors of a number $n$ whose prime factorisation is $p_1^{a_1}.p_2^{a_2}......p_n^{a_n}$ are $(a_1+1).(a_2+1).(a_3+1).....(a_n+1)$.

To get the highest ratio, we need to select smallest prime numbers. Further, we need to manipulate all the $a_i$ in such a way so that the number if factors become maximum.

$\endgroup$
1
  • $\begingroup$ $84=2^2\times 3 \times 7$ has a higher ratio of divisors than any larger number ($\frac17$) despite having a prime factor of $7$ but not $5$ $\endgroup$
    – Henry
    Apr 3 '17 at 23:37

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.