# Find 4 positive integers not exceeding 70,000 such that each have more than 100 divisors

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.

• 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? Dec 12, 2015 at 3:03
• 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. Dec 12, 2015 at 4:07
• Are negative divisors allowed? :p Dec 12, 2015 at 4:16
• May find a lot of useful information: sequence d(n) in OEIS and Wikipedia Dec 12, 2015 at 4:18
• $2^23^25^2(7)(11)=69300$ has 108 factors. Dec 12, 2015 at 4:34

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.

• I was never told that negative factors was allowed so its most likely a trick question. Dec 12, 2015 at 20:25
• 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. Dec 12, 2015 at 20:37

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.