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$
7
  • 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, 2015 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$
    – hmakholm left over Monica
    Dec 12, 2015 at 4:07
  • $\begingroup$ Are negative divisors allowed? :p $\endgroup$
    – fleablood
    Dec 12, 2015 at 4:16
  • $\begingroup$ May find a lot of useful information: sequence d(n) in OEIS and Wikipedia $\endgroup$
    – Jesse P Francis
    Dec 12, 2015 at 4:18
  • 1
    $\begingroup$ $2^23^25^2(7)(11)=69300$ has 108 factors. $\endgroup$
    – Gerry Myerson
    Dec 12, 2015 at 4:34

2 Answers 2

Reset to default
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$
2
  • $\begingroup$ I was never told that negative factors was allowed so its most likely a trick question. $\endgroup$
    – swandilaon
    Dec 12, 2015 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, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .