Problem 3. Let $d(n)$ denote the number of positive divisors of $n$. For positive integer $n$ we define $f(n)$ as

$$
f(n)=d\left(k_{1}\right)+d\left(k_{2}\right)+\ldots+d\left(k_{m}\right)
$$

where $1=k_{1}1$ almost perfect if $f(n)=n$. Find all almost perfect numbers.

(Paulius Ašvydis)
First Solution. Alternative way to define $f(n)$ is

$$
f(n)=\sum_{k \mid n, k \geq 1} d(k)
$$

Let $n=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}}$ be the prime factorisation of $n$. We have $d(n)=\prod_{i=1}^{r}\left(a_{i}+1\right)$.

We prove the function $f$ is multiplicative, in particular, given coprime $n, m$ we have $f(n m)=f(n) f(m)$.

Using $n, m$ are coprime for the second inequality and the fact that function $d$ is multiplicative we get:

$$
f(n m)=\sum_{k \mid n m} d(k)=\sum_{k_{1}\left|n, k_{2}\right| m} d\left(k_{1} k_{2}\right)=\sum_{k_{1}\left|n, k_{2}\right| m} d\left(k_{1}\right) d\left(k_{2}\right)=\left(\sum_{k_{1} \mid n} d\left(k_{1}\right)\right)\left(\sum_{k_{2} \mid n} d\left(k_{2}\right)\right)=f(n) f(m)
$$

If $r=1$ we have $n=p_{1}^{a_{1}}$. We note that divisors of $n$ are $1, p_{1}, p_{1}^{2}, \cdots, p_{1}^{a_{1}}$ so $f(n)=\sum_{i=0}^{a_{1}}(i+1)=\frac{\left(a_{1}+1\right)\left(a_{1}+2\right)}{2}$.

Combining this with the multiplicativity result for $f$ we deduce $f(n)=\prod_{i=1}^{r} \frac{\left(a_{i}+1\right)\left(a_{i}+2\right)}{2}$.

We now prove that for primes $p \geq 5$ and $p=3$ provided $a \geq 3$ we have $f\left(p^{a}\right)=\frac{(a+1)(a+2)}{2}1$ and prime $p$ we have

$$
f(p n) \leqslant 3 f(n)
$$

The equality holds if and only if $G C D(p, n)=1$. Proof: For every integer $m$ we have that the set of divisors of the number $p m$ 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 $\operatorname{GCD}(p, m)=1$ (if we have that $p, m$ are disjoint, then it is obvious that none of the divisors of $p m$ are in both sets; if they are not coprime, then the number $p$ belongs to both sets).

This is why we have $d(p m) \leqslant 2 d(m)$ and

$$
f(p n)=\sum_{k \mid p n} d(k) \leqslant \sum_{k \mid n} d(k)+\sum_{k \mid n} d(p k) \leqslant f(n)+\sum_{k \mid n} 2 d(k)=3 f(n)
$$

In both inequalities equality holds if and only if sets from before are disjoint, i.e. when $\operatorname{GCD}(p, n)=1$.

Also, we simply see that $f\left(2^{k}\right)=d(1)+d(2)+\ldots+d\left(2^{k}\right)=1+2+\ldots+(k+1)=\frac{(k+1)(k+2)}{2}$.

Notice that if for some positive integer $n$ we have $f(n)f(n)$, conclude that there are not almost perfect numbers among their nice multiples. With formula for $f\left(2^{k}\right)$ conclude that for sufficiently big $k$ (when $f\left(2^{k}\right)5$ then we have $2 p>f(2 p)$, so for all almost perfect numbers of the form $2^{1} \cdot 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 have 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)5$ then we have $4 p>f(4 p)$, so for all almost perfect numbers of the form $2^{1} \cdot 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 multiples 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)<3 f(4 \cdot 9)=4 \cdot 27$. So, there are no more solutions in this case.

Fourth case: $k=3$

For any odd prime we have $f(8 p)=3 f(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$.