Smallest $n$ with given number of solutions of $\frac{1}{u} + \frac{1}{v} = \frac{1}{n}$

With $n,u,v$ being positive integers, let $T(n)$ be the number of ordered pair of positive integers $(u,v)$ such that

$$\frac{1}{u} + \frac{1}{v} = \frac{1}{n}$$

What is the smallest $N$ such that such that $N$ is a prime power and $T(N) = 13$?

What about a general $k$? How do we find the smallest $n$ such that $T(n) = k$?

This problem is posed by Sreejato B.

Details: A prime power is of the form $p^n$, where is a prime number and is a positive integer

• This is (almost) Project Euler #108, just fyi. – Emily Jul 29 '13 at 21:25

If I calculated correctly:

• T(1) = 1
• T(2) = 3
• T(3) = 3
• T(4) = 5
• T(5) = 3
• T(6) = 9
• T(7) = 3
• T(8) = 7
• T(9) = 5
• T(10) = 9
• T(11) = 3
• T(12) = 15

So, if you meant to ask for the smallest $n$ where $T(n) \ge 12$, that would be $n = 12$. But $T(n)$ can never be exactly 12 because it's always odd.

tsillke gave one explanation. Another way to see this is that, because of symmetry, solutions come in pairs: If $(u, v) = (a, b)$ is a solution, then so is $(u, v) = (b, a)$. However, there's also always one solution with $u = v$, namely $(u, v) = (2n, 2n)$. This is counted as a single solution instead of a pair, making the number of solutions odd.

This problem is essentially equivalent to solving

$$\tau(n^2) = k$$

where $\tau(m)$ is the number of divisors of $m$

This we see by rewriting as

$$(u-n)(v-n) = n^2$$

Notice that, this necessarily implies that $k$ must be odd (number of divisors of a perfect square is odd), and so $T(n) = 12$ has no solutions.

There might not be a simple solution for the general case.

I am writing it as an answer so that it is more visible.

This is a live Brilliant problem, and in fact proposed by me! I am requesting the other answerers to kindly delete their solutions till $5/8/2013$. For your information, there is a typo in the question. It should have been $f(n)= 13$

• This seems rather like an attempt of disguising the problem than a typo. – Tomas Jul 30 '13 at 19:50
• @Tomas No, it is a typo, As tsillke pointed out, $T(n)$ must always be odd. For your information, I was the one who proposed this problem, and I have already solved it. – aba Jul 31 '13 at 4:04
• I am just saying, he also renamed the function from $f$ to $T$. So maybe he deliberately changed the value to $12$ (without knowing, that there is no solution) to disguise the problem. He received some answers, like the hint from tsillke, which he then could apply to the $13$ case. – Tomas Jul 31 '13 at 9:48
• That might be true. :) @Tomas – aba Jul 31 '13 at 15:30