7
$\begingroup$

(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}$?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Mike Pierce Feb 26 '15 at 5:55
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Benjamin Dickman Mar 23 '15 at 7:35
5
$\begingroup$

You should know, for example, that the number of divisors $d(N)$ satisfies $$ d(N) \leq 24 \; \sqrt[3] {\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.

$\endgroup$
  • 2
    $\begingroup$ 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...) $\endgroup$ – Benjamin Dickman Feb 26 '15 at 5:56
  • 2
    $\begingroup$ @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 $\endgroup$ – Will Jagy Feb 26 '15 at 6:01
  • $\begingroup$ 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). $\endgroup$ – Benjamin Dickman Mar 23 '15 at 7:38
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.