# When is the number of $N$'s factors $1 + \sqrt{N}$?

(Answer: Only $N = 4$ and $N = 16$.)

The following question arose in a course for pre-service and in-service elementary school teachers:

For what $N \in \mathbb{N}$ is it the case that the number of $N$'s factors is $1 + \sqrt{N}$?

The initial observations were that this holds for $N = 4$ and $N = 16$, with $1 + \sqrt{4} = 3$ and $1 + \sqrt{16} = 5$ factors, respectively. (The factors of $4: 1, 2, 4$; the factors of $16: 1, 2, 4, 8, 16$.)

Noting $\sqrt{N} \in \mathbb{N}$ requires all primes in the prime factorization of $N$ to be raised to even powers, I tried a few individual cases using the standard technique for enumerating the number of factors.

For example:

If we have a prime squared $N = p^2$, then the number of factors is $2+1 = 3$.

Moreover, $1 + \sqrt{N} = 1 + p$. We now seek a prime $p$ for which $1 + p = 3$; so $p=2$ is the unique solution. In a similar vein, consider $p^4$ has $4+1 = 5$ factors, and square root $p^2$; so we need a prime $p$ for which $1+p^2 = 5$. Again $p = 2$ works, so we recover the aforementioned cases $4$ and $16$ that were initially found by just exploring.

I checked a few more examples, but did not find any other $N$ that worked.

An example that did not work: Consider the product of distinct primes squared $N = p^2 q^2$. Then the number of factors is $(2+1)(2+1) = 9$, and $1 + \sqrt{N} = 1 + pq$. We now seek distinct primes $p$ and $q$ for which we have $1 + pq = 9$, i.e., $pq = 8$; but no such primes exist, since $8 = 2^3$. So there is no admissible $N$ with this multiplicative structure.

One can work out other, individual examples with reasonable celerity: $p^2 q^4$ has $15$ factors, and equating this to one plus its square root gives $pq^2 = 14$; again, no distinct primes $p$ and $q$ exist to satisfy this condition, since $14 = 2 \cdot 7$.

I imagine there is a reasonably short (and totally elementary - even if not in the sense of "elementary school") approach to this problem in generality. I expect that there are no solutions other than $4$ and $16$, but do not see a quick way to argue as much.

For the sake of clarity, here is the question stated again:

For what $N \in \mathbb{N}$ is it the case that the number of $N$'s factors is $1 + \sqrt{N}$?

• Doing a brute-force search on $N$ yields only $4$ and $16$ for $N$ up to $100\,000\,000$ (searching only perfect squares, of course). – Mike Pierce Feb 26 '15 at 5:55

## 3 Answers

If $N = \prod_j p_j^{d_j}$ is the prime factorization of $N$, its number of divisors $\tau(N)$ is $\prod_j (1 + d_j)$. You want $\sqrt{N}$ to be an integer, so all $d_j \ge 2$ are even. The minimum value of $p^{d/2}/(1+d)$ for primes $p$ and even positive integers $d$ is $2/3$ at $p = 2$, $d = 2$. The only other cases where $p^{d/2}/(1+d) \le 3/2$ are $p=2, d=4$ or $6$ and $p=3, d=2$, where $p^{d/2}/(1+d) = 4/5, 8/7, 1$ respectively. So in order to have a chance for $\sqrt{N}$ to be less than the number of divisors, the exponent of $2$ must be either $2$ or $4$, there can be a $3^2$, but no other primes and no higher powers. That is, the only squares where $\tau(N) > \sqrt{N}$ are $4, 16, 36, 144$. These have $\tau(N) - \sqrt{N} = 1, 1, 3, 3$ respectively.

• Thanks for the answer! I've accepted it, but also written up a slightly more detailed version (with some examples) that might be easier for non-mathematicians to digest. – Benjamin Dickman Mar 23 '15 at 7:35

You should know, for example, that the number of divisors $d(N)$ satisfies $$d(N) \leq 24 \; \sqrt {\frac{N}{315}}.$$ Equality holds only at $N=2520.$

This is eventually smaller than the square root of $N,$ and you can make explicit bounds for your search. Put on programmable calculator, this bound is equal to $\sqrt N$ at about $N=1926$ and smaller after.

• Do you have a reference offhand? My preference is to have an elementary (and the more accessible, the better) argument; I am concerned that establishing such a bound on $d(N)$ is nontrivial. Moreover, it would still require an additional search. (But, +1 for indicating that the problem will not be intractable...) – Benjamin Dickman Feb 26 '15 at 5:56
• @BenjaminDickman, Ramanujan about 1912. The construction is called the Superior Highly Composite Numbers. See also mathoverflow.net/questions/43103/… I should emphasize that much of the argument, maybe all, is elementary; part is in Hardy and Wright. However, it is lengthy and may not be suitable for your class for that reason – Will Jagy Feb 26 '15 at 6:01
• Thanks for the pointer! I ended up accepting Robert Israel's argument since it is totally elementary (but also writing up a summary of it that could be presented to non-mathematician school teachers). – Benjamin Dickman Mar 23 '15 at 7:38

Just to rephrase Robert Israel's answer into more palatable language for the level at which I am presently teaching:

There are two functions to think about here.

The first is the divisor function, $N \rightarrow d(N) := \#\{N$'s distinct divisors$\}$.

The second is the function $N \rightarrow 1 + \sqrt{N}$.

The issue with finding (necessarily square) integers $N$ for which $d(N)$ and $1+\sqrt{N}$ are equal is that the latter grows very quickly; in fact, we have equality iff $N \in \{2^2, 2^4\}$.

For example, consider $5^2$: Then $d(5^2) = 2+1 = 3$, and $1+\sqrt{5^2} = 6$, where $6 > 3$.

Similarly, consider $7^4$: Then $d(7^4) = 4+1 = 5$, and $1 + \sqrt{7^4} = 50$, where $50 > 5$.

So if we consider a number like $N = 5^2 \cdot 7^4$, then $d(N) = 3 \cdot 5 = 15$, but $1 + \sqrt{N} = 246$.

In this way, one comes to see that we will almost always have $d(N) < 1 + \sqrt{N}$ by a fair bit.

The three exceptions to this (noting again that we want $N$ to be a perfect square so that its square root is an integer) are $2^2, 2^4,$ and $3^2$. Even with $N = 3^4$ we find $d(N) = 5 < 10 = 1 + \sqrt{N}$.

So we examine $N$ equal to each of $2^2, 2^4, 3^2, 2^2 \cdot 3^2,$ and $2^4 \cdot 3^2$.

(RI eliminates $3^2$ using a separate parity argument.)

The cases of $2^2$ and $2^4$ satisfy the desired equality; the others do not.

In particular:

$d(2^2) = 3 = 1 + \sqrt{2^2}$ and $d(2^4) = 5 = 1 + \sqrt{2^4}$.

However:

$d(3^2) = 3 < 4 = 1 + \sqrt{3^2}$;

$d(2^2 \cdot 3^2) = 9 > 7 = 1 + \sqrt{2^2 \cdot 3^2}$; and

$d(2^4 \cdot 3^2) = 15 > 13 = 1 + \sqrt{2^4 \cdot 3^2}$.

(For completeness, we might note that $d(1) = 1 < 2 = 1 + \sqrt{1}$.)

From here: Any other choice of $N$ will yield $d(N) < 1 + \sqrt{N}$. QED