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)+ \cdots + d\left(k_m\right),$$where $1 = k_1 < k_2 < \cdots < k_m = n$ are all divisors of the number $n$. We call an integer $n > 1$ almost perfect if $f(n) = n$. Find all almost perfect numbers. Paulius Ašvydis
Problem
Source: European Mathematical Cup, 2015, Junior, P3
Tags: number theory, divisor
spacewalker
30.12.2016 14:07
How many terms are in that summation? EDIT: was just pointing out a typo, I think it has been corrected
Tugsuu
30.12.2016 14:54
hmmm, this is really similar to a past IMO problem
Find the formula for $f(n)$
Establish some bounds.
Answer:
$n \in \{1, 3, 18, 36\}$
Solution:
Lemma: $f(n)$ is muliplicative: Let $g(n)$ by the number of divisors of $n$. Therefore $f(n) = \sum_{d|n} g(n)$. By Dirichlet Convolution, since $g(n)$ is multiplicative, $f(n)$ is also multiplicative. $\square$ So it's sufficient to calculate $f(n)$ for prime powers.
\begin{align*}
f(p^{e}) &= \sum_{d|p^{e}} g(n) \\
&= 1 + 2 + \cdots + (e+1)\\
&= \frac{(e+1)(e+2)}{2}
\end{align*}Let $n = \prod_{i=1}^{k}p_{i}^{e_{i}}$. Define a new function $H_{p}(e) \coloneqq \frac{2p^{e}}{(e+1)(e+2)}$. By definition $H_{p}(0)=1$ for all primes $p$. Plugging in the equation for $f(n)$ reduces the problem to solving
\begin{align*}
1 &= \prod_{i=1}^{k} \frac{2p_{i}^{e_{i}}}{(e_{i}+1)(e_{i}+2)}\\
1 &= \prod_{i=1}^{k} H_{p_{i}}(e_{i})
\end{align*}Notice that $H_{p}(e) - H_{p}(e-1) = 2p^{e-1}\left(\frac{pe-e-2}{(e)(e+1)(e+2)}\right)$. This shows that
(1) $H_{p}(e)$ is strictly increasing for all $p\geq 5$,
(2) $H_{3}(e)$ is strictly increasing for $e\geq1$
(3) $H_{2}(e)$ is strictly increasing for $e\geq2$.
Some lower bounds and casework show that any prime $\geq 5$ can't divide $n$. Doing casework on $H_{2}(e)$ and $H_{3}(e)$ reveals the answers above.
RagvaloD
30.12.2016 15:42
We can find $f(n)$ without using any $f(n)$ and $d(n)$ properties. We will count how many times divisor of $n$ will be counted in $f(n)$ Let $n = \prod_{i=1}^{k}p_{i}^{e_{i}},q = \prod_{i=1}^{k}p_{i}^{r_{i}},r_i \leq e_i$ Then numbers of divisors of $n$, that also are divided by $q$ is $(e_1-r_1+1)(e_2-r_2+1)...(e_k-r_k+1)$ $f(n)=\sum_{r_1=0}^{e_1}\sum_{r_2=0}^{e_2}...\sum_{r_k=0}^{e_k} (e_1-r_1+1)(e_2-r_2+1)...(e_k-r_k+1)=\sum_{t_1=1}^{e_1+1}\sum_{t_2=1}^{e_2+1}...\sum_{t_k=1}^{e_k+1} (t_1t_2...t_k) = \prod_{i=1}^{k} \frac{(e_i+1)(e_i+2)}{2} $