Maximizing a Strange Function

Note that if $\dfrac{n-a}{a}$ is a positive integer, so is $\dfrac{n}{a}$ . Thus, we want to find the number $n\le 1000$ such that it has the largest possible number of prime factors. Checking the list of Highly Composite numbers , we see that this number is $840$ with $32$ factors. Every single one of these factors can work for $a$ except $840$ since $a < n$ . Thus, the answer is $\boxed{31}$ .

The key is to use the Euclidean Algorithm . In short, if a number $n$ is divisible by $a$ , the expression will be an integer. For example, for $n=20$ , $a$ can equal $5$ , $10$ , $4$ , $2$ , or $1$ . Convince yourself that this is true. Do you see why?

Anyways, this can be applied to the problem by realizing that we're really just looking for the number $\leq 1000$ with the most factors. You're welcome to use any means, but you could just know that this is $840$ off the top of your head.

Now, you may be tempted to realize $840$ has $32$ factors and just put $32$ as your final answer, but read this line:

$\dots$ positive integral $a<n$ $\dots$

Because we're overcounting by $1$ since we obviously can't count $840$ , our final answer is $32-1=\boxed{31}$ .

Sage Code:

1
2
3
4
5
6
7

    def f(n):

    c = 0

    for a in xrange(1,n+1):

        if (n-a)/a > 0:

            if (n-a)/a in ZZ:

                c += 1

    return c

Next run:

1
2
3
4
5
6

    l = []
    
n = 1
    
while n < 1000:

        l.append(f(n))

        n += 1
   max(l)

It returns $31$