# 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? – Element118 Dec 12 '15 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. – Henning Makholm Dec 12 '15 at 4:07
• Are negative divisors allowed? :p – fleablood Dec 12 '15 at 4:16
• May find a lot of useful information: sequence d(n) in OEIS and Wikipedia – Jesse P Francis Dec 12 '15 at 4:18
• $2^23^25^2(7)(11)=69300$ has 108 factors. – Gerry Myerson Dec 12 '15 at 4:34

## 2 Answers

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. – swandilaon Dec 12 '15 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. – fleablood Dec 12 '15 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.