2
$\begingroup$

I am looking at problems in Vandendriessche and Lee's Problems in elementary number theory and this is one of their problems:

Find $4$ positive integers not exceeding $70000$ such that each have more than $100$ divisors

I just started picking some numbers and looked at their factors:

$25=1,5,25;\;(3\;\text{divisors})$

$50=1,2,5,10,25,50;\;(6\;\text{divisors})$

$100=1,2,4,5,10,20,25,50,100;\;(9\;\text{divisors})$

$200=1,2,4,5,8,10,20,25,40,50,100,200;\;(12\;\text{divisors})$

So I guess $400$ should have $15$ factors based on the pattern above.

In this case I've noticed that there are $3$ more factors after each multiplication by $2$ but I think this approach wouldn't help me to find solutions.

$\endgroup$
  • 1
    $\begingroup$ Suppose we know the prime factorisation of an integer. We can find the number of divisors from there. How can we maximise the number of divisors? Smaller prime factors? $\endgroup$ – Element118 Dec 12 '15 at 3:03
  • 1
    $\begingroup$ Based on a semi-brute force search, the only solutions appear to be 50400, 55440, 60480, and 65520 (whereas 45360 has exactly 100 divisors and so doesn't qualify). But I can't come up with a nice pencil-and-paper argument that point to them. $\endgroup$ – Henning Makholm Dec 12 '15 at 4:07
  • $\begingroup$ Are negative divisors allowed? :p $\endgroup$ – fleablood Dec 12 '15 at 4:16
  • $\begingroup$ May find a lot of useful information: sequence d(n) in OEIS and Wikipedia $\endgroup$ – Jesse P Francis Dec 12 '15 at 4:18
  • 1
    $\begingroup$ $2^23^25^2(7)(11)=69300$ has 108 factors. $\endgroup$ – Gerry Myerson Dec 12 '15 at 4:34
1
$\begingroup$

If $p$ and $q$ are prime $p^nq^m$ have as divisors any $p^iq^j$. In other words $p^nq^m$ has $(n + 1)(m+1)$ divisors.

So we want $m = \prod p_i^{k_i} < 7* 10^4$ and $\prod (k_i + 1) > 100$. As a wild guess I'll try $2^43^45^3$ = 162000. This has exactly 100 factors: any {1,2,4,8,16}x{1,3,9,27,81}x{1,5,25,125} but it's too large.

$2^6*3^3*5*7$ = 60480 has 7*4*2*2 = 112 factors. So that's 1.

$2^5*3^2*5^2*7$=50400 has 108 factors so that's another.

This is actually harder than it looked.

.... unless it's a trick question and negative factors are allowed. In which case all of these have twice as many factors and we have a lot more leeway.

$\endgroup$
  • $\begingroup$ I was never told that negative factors was allowed so its most likely a trick question. $\endgroup$ – swandilaon Dec 12 '15 at 20:25
  • $\begingroup$ Henning in the comments came up with 4 so it probably isn't a trick question. I think I've come up with how to find numbers with more than 100 divisors, but I think I'm missing something about how to minimize them. $\endgroup$ – fleablood Dec 12 '15 at 20:37
1
$\begingroup$

Your method of using $N= 2^n M$ is good, but you should have experimented with other $M$. Let $D(n)$ be the number of divisors of $N$.

If $N = 2^n 5^\color{brown}2$, then,

$$D(n)= 3,6,9,12,15,\dots$$

for $n=1,2,3\dots$ as you observed. But its growth of $\color{brown}2+1 = 3$ divisors is too slow.

However, if $N = 2^n\cdot 3^\color{brown}2\cdot5^\color{brown}2\cdot7^\color{brown}1$,

$$D(n)= 36, 54, 72, 90, 108,\dots$$

which increases by $(\color{brown}2+1)(\color{brown}2+1)(\color{brown}1+1)$=18 divisors as $n$ goes up. If $N = 2^n\cdot 3^2\cdot5\cdot7\cdot11$, then,

$$D(n) = 48, 72, 96, 120,\dots$$

which increases by 24 divisors, and so on.

$\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.