European Mathematical Cup

Alternative way to define $f(n)$ is $$f(n)=\sum _{k|n,k\ge 1}d(k).$$ Let $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_r^{{\alpha }_r}$ be the prime factorization of $n$. We have $d(n)={\prod }_{i=1}^r({\alpha }_i+1)$. We prove the function $f$ is multiplicative, in particular, given coprime $n,m$ we have $f(mn)=f(m)f(n)$. Using $n,m$ are coprime for the second inequality and the fact that function $d$ is multiplicative we get: $$f(mn)=\sum _{k|m}d(k)=\sum _{k_1|n,k_2|m}d(k_1{k}_2)=\sum _{k_1|n}d(k_1)d(k_2)=\left(\sum _{k_1|n}d(k_1)\right)\left(\sum _{k_2|m}d(k_2)\right)=f(n)f(m).$$ If $r=1$ we have $n=p_1^{{\alpha }_1}$. We note that divisors of $n$ are $1,p_1,p_1^2,\dots ,p_1^{{\alpha }_1}$, so $$f(n)=\sum _{i=0}^{{\alpha }_1}(i+1)=\frac{({\alpha }_1+1)({\alpha }_1+2)}{2}.$$ Combining this with the multiplicativity result for $f$ we deduce $f(n)={\prod }_{i=1}^n\frac{({\alpha }_i+1)({\alpha }_i+2)}{2}$. We now prove that for primes $p\ge 5$ and $p=3$ provided $a\ge 3$ we have $f(p^a)=\frac{(a+1)(a+2)}{2}<\frac{2}{3}{p}^a$ by induction on $a$. As a basis $3<\frac{2p}{3}$ for $p\ge 5$ and $6<\frac{2}{3}\cdot 3^3$. For the step it is enough to notice that $\frac{a+3}{a+1}\le 2<p$ in both cases. Similarly we can prove for $p=2$ that $f(p^a)<p^a$ provided $a\ge 4$. By explicitly checking the remaining cases $p=2$ and $a=1,2,3$ and $p=3,a=1,2$ we conclude $f(p^a)\le \frac{2}{3}{p}^a$ for all $p,a$ and $f(p^a)\le p^a$ for all $p\ge 3$ and $p=2,a\ge 4$. Assuming $f(n)=n$ we would have ${\prod }_{i=1}^k\frac{f(p_i^{{\alpha }_i})}{p^{{\alpha }_i}}=1$ so the above considerations imply that only possible prime divisors are 2,3. If $k=1$ the only possible solution is $n=3$. If $k=2$ we have $p_1=2,p_2=3$ and $1\le a_1\le 2$ and $1\le a_2\le 2$ which give 4 cases to check giving the other 2 solutions $n=18,36$.

---

Alternative solution.

We hereby present one similar but different solution which does not use a lot of properties of the function $f$. Firstly, we will prove the following lemma: Lemma. For any positive integer $n>1$ and prime $p$ we have $$f(pn)\le 3f(n).$$ The equality holds if and only if $GCD(p,n)=1$. Proof. For every integer $m$ we have that the set of divisors of the number $pm$ is the union of the following two sets: set of divisors of $m$ set of divisors of $m$ multiplied by $p$. Also those two mentioned sets are disjoint if and only if $GCD(p,m)=1$ (if we have that $p,m$ are disjoint, then it is obvious that none of the divisors of $pm$ are in both sets; if they are not coprime, then the number $p$ belongs to both sets). This is why we have $d(pn)\le 2d(m)$ and $$f(pn)=\sum _{k|pn}d(k)\le \sum _{k|n}d(k)+\sum _{k|n}d(pk)\le f(n)+\sum _{k|n}2d(k)=3f(n).$$ In both inequalities equality holds if and only if sets from before are disjoint, i.e. when $GCD(p,n)=1$.

Also, we simply see that $f(2^k)=d(1)+d(2)+...+d(2^k)=1+2+3+...+(k+1)=\frac{(k+1)(k+2)}{2}$. Notice that if for some positive integer $n$ we have $f(n)<n$, then for every $p\ge 3$ we have $f(pn)\le 3f(n)\le pf(n)<pn$. Consequently, if $f(n)<n$, then for every odd $m$ we have $f(mn)<mn$. Because of this, we will introduce new terms. Number $n$ is nice multiple of $m$ if $m|n$ and $m/n$ is odd number. Analogously, we define nice divisor. Our statement from above is: if for some $n$ we have $f(n)<n$, then neither of its nice multiplies is almost perfect number. Our strategy will be the following: check the cases of the small numbers and see ratio of numbers $n$ and $f(n)$. When we have that $n>f(n)$, conclude that there are not almost perfect numbers among their nice multiplies. With formula for $f(2^k)$ conclude that for sufficiently big $k$ (when $f(2^k)<2^k$ this is enough to conclude that there are no more almost perfect numbers. By induction, it is simple to prove that $f(2^k)<2^k$ for $k\ge 4$. Thus, there are no almost perfect numbers of the form $2^k\cdot m$, where $k\ge 4$ and $m$ is odd, since they all have $2^k$ as their nice divisor. We only have to check the numbers of the form $2^k\cdot m$, where $k\le 3$ and $m$ is odd. First case: $k=0$ For any odd prime $p$ we have $f(p)=d(1)+d(p)=3\le p$. From that we see that $n=3$ is solution. Moreover, we do not have any more solutions: if some odd number has a prime divisor different from 3, since $f(p)<p$ this number can not be almost perfect number; if it is a power of 3 bigger than 3, since $f(9)<3f(3)=9$, there are no more solutions as well (9 is nice divisor of every power of 3 bigger that 3). Second case: $k=1$. For any odd prime we have $f(2p)=3f(2)=9$. If $p>5$ then we have $2p>f(2p)$, so for all almost perfect numbers of the form $2^{1}m$ number $m$ has to have prime divisors 3 and/or 5. We directly see that neither 6 or 10 is almost perfect. SO, in this case, almost perfect number has to be a nice divisor of the form $2\cdot 9,2\cdot 15$ or $2\cdot 25$. For $n=18$ we have another solution, in other two cases we have inequality $f(n)<n$. If we want to seek new solution in this case, since they cannot be nice multiplies of 30 and 50, the only possibility is that almost perfect number has nice divisor $2\cdot 27$. But we have (equality case in lemma) that $f(2\cdot 27)<3f(2\cdot 9)=2\cdot 27$. So, there are no more solutions in this case. Third case: $k=2$ For any odd prime we have $f(4p)=3f(4)=18$. If $p>5$ then we have $4p>f(4p)$, so for all almost perfect numbers of the form $2^{1}m$ number $m$ has to have prime divisors 3 and/or 5. We directly see that neither 12 or 20 is almost perfect. So, in this case, almost perfect number has to have a nice divisor of the form $4\cdot 9,4\cdot 15$ or $4\cdot 25$. For $n=36$ we have another solution, in other two cases we have inequality $f(n)<n$. If we want to seek new solution in this case, since they cannot be nice multiplies of 60 and 100, the only possibility is that almost perfect number has nice divisor $4\cdot 27$. But we have (equality case in lemma), that $f(4\cdot 27)<3f(4\cdot 9)=4\cdot 27$. So, there are no more solutions in this case. Fourts case: $k=3$ For any odd prime we have $f(8p)=3f(8)=30$. Similarly to other cases, we only observe candidates of the form $8\cdot 3^l$. Number 8\cdot 3 is not almost perfect, all other candidates have nice divisor 8\cdot 9. But, we have $f(72)=60<72$. As we always concluded, we do not have any new solutions. So all almost perfect numbers are 3,18,36.