Find all natural numbers $n$ for which equality holds $n + d (n) + d (d (n)) +... = 2021$, where $d (0) = d (1) = 0$ and for $k> 1$, $ d (k)$ is the superdivisor of the number $k$ (i.e. its largest divisor of $d$ with property $d <k$). (Tomáš Bárta)
Problem
Source: 2021 Czech and Slovak Olympiad III A p4
Tags: number theory, divisor, divides
06.06.2021 19:16
Bashy problem. The only solution is $$\boxed{n=1919}$$This indeed works since $d(n)=101$ and $d(d(n))=1$. Now we prove that it is the only solution. Let $$f(n)=n+d(n)+d(d(n))+\cdots$$for all positive integers $n$. Lemma: If $p$ is the largest prime divisor of $n$, then $f \left(\dfrac{n}{p} \right)=\dfrac{f(n)-1}{p}$ Proof: Note that $\frac{n}{d(n)}$ is just the smallest prime factor of $n$. That means, if the prime factors of $n$ are $p_1,p_2,\dots p_k$, in non-decreasing order (counting multiplicities), then $$f(n)=p_1p_2p_3\cdots p_k+ p_2p_3\cdots p_k + p_3 \cdots p_k +\cdots +p_k+1$$Now checking the required equality is routine. $\blacksquare$ This means, in particular, that $p \mid f(n)-1=2020$ $\implies$ $p=2$, $5$ or $101$. Case I: $p=2$ Let $n=2^a$. Then it is easy to calculate that $f(n)=2^{a+1}-1$ $\implies$ $2^{a+1}=2022$, which is impossible. Case II: $p=5$ Let $m=\frac{n}{5}$. Then by the Lemma, we get $f(m)=404$ $\implies$ The largest prime factor, $q$, of $m$ divides $403$ $\implies$ $q=13$ or $31$, which is impossible since we must have $q \leq p = 5$. Case III: $p=101$ Let $m=\frac{n}{101}$. Then by the Lemma, we get $f(m)=20$ $\implies$ The largest prime factor, $q$, of $m$ divides $19$ $\implies$ $q=19$ $\implies$ $19 \cdot 101 = 1919 \mid n$. But note that $$n \leq f(n)=2021 <2 \cdot 1919$$So in fact $n=1919$, as required. $\blacksquare$
07.06.2021 00:20
A shorter proof. Let $n=q_1q_2\cdots q_N$ where $q_1\le q_2\le \cdots \le q_N$ are primes. Note that $d(n) = q_2\cdots q_N$, $d(d(n))=q_3\cdots q_N$, and so on. Consequently, we deduce \[ q_1q_2\cdots q_N + q_2q_3\cdots q_N + \cdots + q_N = 2020 \implies q_N\mid 2020. \]In particular, $q_N\in\{2,5,101\}$. Now, if $q_N=101$, then dividing by $q_N$, we now obtain \[ q_1q_2\cdots q_{N-1}+q_2q_3\cdots q_{N-1}+\cdots +q_{N-1}= 19. \]In particular, $q_{N-1}\mid 19$, forcing $q_{N-1}=19$, and thus $n=19\cdot 101=1919$. Next, if $q_N=2$, then $n=2^N$ forcing the sum to be $2^N+2^{N-1}+\cdots+1 =2^{N+1}-1$, clearly impossible. The last case to consider is $q_N=5$. Dividing above, we find $q_{N-1}\mid 2020/5 - 1 = 403 = 13\cdot 31$. As $q_{N-1}\le q_N=5$, this however is not possible.
26.05.2023 12:17
Why q1.q2..qn+...+qn=2020 when the title is 2021 ?
26.05.2023 12:18
grupyorum wrote: A shorter proof. Let $n=q_1q_2\cdots q_N$ where $q_1\le q_2\le \cdots \le q_N$ are primes. Note that $d(n) = q_2\cdots q_N$, $d(d(n))=q_3\cdots q_N$, and so on. Consequently, we deduce \[ q_1q_2\cdots q_N + q_2q_3\cdots q_N + \cdots + q_N = 2020 \implies q_N\mid 2020. \]In particular, $q_N\in\{2,5,101\}$. Now, if $q_N=101$, then dividing by $q_N$, we now obtain \[ q_1q_2\cdots q_{N-1}+q_2q_3\cdots q_{N-1}+\cdots +q_{N-1}= 19. \]In particular, $q_{N-1}\mid 19$, forcing $q_{N-1}=19$, and thus $n=19\cdot 101=1919$. Next, if $q_N=2$, then $n=2^N$ forcing the sum to be $2^N+2^{N-1}+\cdots+1 =2^{N+1}-1$, clearly impossible. The last case to consider is $q_N=5$. Dividing above, we find $q_{N-1}\mid 2020/5 - 1 = 403 = 13\cdot 31$. As $q_{N-1}\le q_N=5$, this however is not possible.