Let $k$ be a fixed positive integer. Find all functions $f :\mathbb{N}\to\mathbb{N}$ such that for any distinct positive integers $a_1,a_2,\ldots,a_k$, there exists a permutation $(b_1,b_2,\ldots,b_k)$ of $\{a_1,a_2,\ldots,a_k\}$ such that $f(a_1)/b_1+ f(a_2)/b_2+\ldots+ f(a_k)/b_k$ is a positive integer.

Please help, I'm really stuck here, I guess $f$ must be constant or linear, I tried induction on $k$, but the permutation mess everything, the case $k=1$ is trivial, idk how to deal with $k>1$.

  • $\begingroup$ Constants don't work. If $f(n)=c$ for all $n$ then, for large $a$ $\frac {f(a)}a$ is not an integer. $f(n)=cn$ works for $c\in \mathbb N$. $\endgroup$
    – lulu
    Nov 3, 2020 at 9:47
  • 1
    $\begingroup$ More broadly, if, for every $n$ we have $n\,|\,f(n)$ then $f(n)$ works. thus $f(n)=n^m$ works but so do "piecewise" functions like $f(n)=n^2$ if $n$ is even and $f(n)=n^5$ if $n$ is odd. $\endgroup$
    – lulu
    Nov 3, 2020 at 9:51
  • $\begingroup$ @lulu and OP I wrote a solution last night but it was messy. Just cleaned it up. Please let me know if you find anything wrong. Thanks. $\endgroup$
    – Neat Math
    Nov 4, 2020 at 12:55

1 Answer 1


Lemma: If $p$ is a prime number, $A, B, M \in \mathbb{N}$, $p \nmid B$, $M$ and $p$ are coprime, then the sum $\frac{A}{M} + \frac{B}{p}$ cannot be a positive integer.

Proof of the lemma is straightforward: $\frac{A}{M} + \frac{B}{p}=N \Rightarrow pA + MB=NMp \Rightarrow p | MB$, a contradiction.

Now we prove $\forall n \in \mathbb N$, we must have $n|f(n)$. We construct a sequence $a_1, a_2, \ldots, a_k$ in the following fashion: $a_1=n$, and $\forall 2\leqslant j \leqslant k$,

$$ a_j > \max\{a_m, f(a_m) , \forall 1\leqslant m<j\}, \text{ and } a_j \text{ is a prime number}. $$

Then there's a permutation $\{ b_j, 1\leqslant j \leqslant k \}$ of $\{ a_j, 1\leqslant j \leqslant k \}$ such that $S \equiv \sum_{j=1}^k f(a_j)/b_j$ is a positive integer. Assume $b_i = a_k$ for some index $i$, we have

$$ S = \frac{A}{\prod_{j=1}^{k-1} a_j} + \frac{f(a_i)}{a_k}. $$

From the lemma, since $\gcd(\prod_{j=1}^{k-1} a_j, a_k)=1$, we know $a_k | f(a_i)$. By construction $a_k > f(a_j), \forall j<k$, therefore $i=k, a_k | f(a_k)$.

It follows that $\sum_{j=1}^{k-1} f(a_j)/b_j$ is also a positive integer. By the same reasoning we have $b_{k-1} = a_{k-1}, a_{k-1} | f(a_{k-1})$. We repeat this process until finally we have $f(n)/n$ as a positive integer.

On the other hand if $n|f(n), \forall n\in \mathbb{N}$, the identity permutation guarantees that $\sum f(a_j)/a_j$ is a positive integer. $\blacksquare$

  • $\begingroup$ I don't understand "we pick prime number $p_2, p_2, \cdots, p_k$ in the following manner, $p_2>\max (n,f(n))$. Should the first $p_2$ be a $p_1$? $\endgroup$
    – lulu
    Nov 4, 2020 at 13:36
  • $\begingroup$ No it's $p_2$. The first number is $n$. $\endgroup$
    – Neat Math
    Nov 4, 2020 at 13:39
  • $\begingroup$ Why does $p_2$ appear twice on your list? $\endgroup$
    – lulu
    Nov 4, 2020 at 13:40
  • $\begingroup$ Ah, I see. Your goal is to define the numbers $a_i$ and $a_1=n$. It's confusing to write $p_2, p_2, \cdots, p_k$ though. $\endgroup$
    – lulu
    Nov 4, 2020 at 13:41
  • $\begingroup$ Yes I agree. I want to emphasize all numbers are prime except for $n$. Later I used $a_j$ instead. $\endgroup$
    – Neat Math
    Nov 4, 2020 at 13:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .