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

Question

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.

Answer 1

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.

Answer 2

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.