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

  • $\begingroup$ This is (almost) Project Euler #108, just fyi. $\endgroup$ – 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$

  • 1
    $\begingroup$ This seems rather like an attempt of disguising the problem than a typo. $\endgroup$ – Tomas Jul 30 '13 at 19:50
  • $\begingroup$ @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. $\endgroup$ – aba Jul 31 '13 at 4:04
  • $\begingroup$ 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. $\endgroup$ – Tomas Jul 31 '13 at 9:48
  • $\begingroup$ That might be true. :) @Tomas $\endgroup$ – aba Jul 31 '13 at 15:30

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.