Determine all positive integers $n$ such that: $n+d(n)+d(d(n))+\dotsb=2023$.

247 Views Asked by At

For a positive integer number $n>1$, we say that $d(n)$ is its superdivisor if $d(n)$ is the largest divisor of $n$ such that $d(n)<n$. Additionally, we define $d(0)=d(1)=0$. Determine all positive integers $n$ such that: $$n+d(n)+d(d(n))+\dotsb=2023.$$

I didn't even understand this problem when I began solving it. I just now realized that if $d(n)<n$ it must mean that $d(d(n))<d(n)$, so the values of the sum must be decreasing, that means that after a finite number of steps we are going to have $d(d(\dotso d(n))\dotso)=d(1)=0$, so then I tried by saying that $n$ cannot be prime, because the smallest prime smaller than $2023$ is $2017$, so for $n=2017$ we have $$n+d(n)+d(d(n))+\dotsb=2017+1++0+0+0+0+\dotsb=2018,$$ so $n$ cannot be prime, but I am not sure what to do from there.

2

There are 2 best solutions below

0
On BEST ANSWER

Let $S(n)$ denote the sum, i.e. $$ S(n) = n + d(n) + d(d(n)) + \dotsb .$$ Note that $n$ cannot be larger than $2023$, and $d(n) \le n / 2$, as the largest divisor of $n$ is obtained by dividing $n$ by its smallest prime factor. This implies that $1012 < n < 2024$. This helps to reduce the search space a bit.[1]

Keeping on the theme of looking at the prime divisors of $n$, observe that if the prime factorization of $n$ is $ n = p_1 p_2 p_3 \dotsb p_m $, with the (possibly repeated) primes listed in decreasing order, then \begin{align} S(n) &= p_1 p_2 p_3 \dotsb p_m + p_1 p_2 p_3 \dotsb p_{m-1} + \dotsb + p_1 + 1 \\ &= p_1 \left( p_2 p_3 \dotsb p_m + p_2 p_3 \dotsb p_{m-1} + \dotsb + p_2 + 1\right) + 1 \\ &= p_1 S\left( \frac{n}{p_1} \right) + 1. \end{align} This implies that $$ S\left( \frac{n}{p_1} \right) = \frac{S(n)-1}{p_1}. $$ This greatly reduces the search space. With $S(n) = 2023$, the possible choices for $p_1$ are $2$, $3$, and $337$ (the factors of $S(n)-1 = 2022$). Then, since $p_1$ divides $S(n) - 1$, a brute force attack is possible (with a relatively small search space).

  • If $p_1 = 2$ (i.e. if the largest prime factor of $n$ is $2$), then it must be the case that $n$ is a power of $2$, i.e. $n = 2^k$ for some integer $k$. The only power of $2$ in the required range is $2^{10} = 1024$. But \begin{align} S(1024) &= 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 \\ &= 2047 \\ &\ne 2023. \end{align}

  • If $p_3=3$, then $$ S\left( \frac{n}{3} \right) = \frac{S(n) - 1}{3} = 674. $$ But then $$ S\left( \frac{n}{3p_2} \right) = \frac{673}{p_2}, $$ where $p_2$ is the largest prime factor of $n/3$ (and thus the second largest prime factor of $n$). But $673$ is prime, so it is its only prime factor. Hence $S(n/2019) = 1$, which implies that $n/2019 = 1$. Then $$ S(n) = S(2019) = 2019 + 673 + 1 = 2693 \ne 2023.$$ Hence it is not possible that $p_1 = 3$.

  • The only possibility remaining is that $p_1 = 337$. Then $$ S\left( \frac{n}{337} \right) = \frac{2022}{337} = 6. $$ Repeating the argument made above, $$ S\left( \frac{n}{337p_2} \right) = \frac{5}{p_2}, $$ which implies that $p_2 = 5$, and that $S(n/1685) = 1$. Therefore the only possibility is that $n = 1685$. Observe that $$ S(n) = 1685 + 337 + 1 = 2023, $$ as claimed.

This exhausts the three cases. The only $n$ which gives the desired result is in the final case; this $n$ is $1685$.


[1] Having finished the problem now, it turns out that I didn't use any of this (well, not very much, anyway), but this search for "good" candidates by winnowing down on prime factors led me to the approach below, so I am going to leave this comment in the answer.

[*] John Omielan pointed out in the comments that a similar problem appears on AoPS. Their solution (with $S(n) = 2021$ instead of $2023$) is remarkably similar to my own, which is both somewhat gratifying (it helps me to believe that this is correct) and incredibly annoying (as it turns out that I just did a bunch of work that someone else has already done). But I got nerd-sniped by this problem, and put the work in, so I'll leave my answer. :/

0
On

When we add up all the terms including $n$ & $d(n)$ , then :
(1) the last non-zero term will be $1$
(2) all other terms will have some factor common with $n$.

Here $2023-1=2022=2 \times 3 \times 337$
Thus the term before the last $1$ could be (A) $2$ (B) $3$ (C) $337$.

CASE A will not work out.
The earlier terms must be Powers of $2$
There is no way to get $2023-1-2=2020$ using Consecutive Powers of $2$.

Similarly CASE B will not work out.

CASE C :

That will leave $2023-1-337=1685=5 \times 337$ , which could be the first term.

Hence the Solution is $n=1685$

CHECK : $n+d(n)+d(d(n))+d(d(d(n)))=1685+337+1+0=2023$

ADDENDUM :

Can there be some variation where we have 1 more term ? No

Let it be $(XY337,Y337,337,1,0)$
We then have $(XY+Y)337=5 \times 337$
That will make $(X+1)Y=5$ which will not work out due to Prime $5$.

In general , is the Solution Unique ? Yes

Consider 2 Solutions
$m+d(m)+d(d(m))+\cdots+P_m+1=n+d(n)+d(d(n))+\cdots+P_n+1$

Then $m+d(m)+d(d(m))+\cdots+P_m=n+d(n)+d(d(n))+\cdots+P_n$
The largest factor on the $m$ terms & the largest factor on the $n$ terms must match to get the Equality.
When that factor is excluded , the next Equality will again force the next largest factor. Eventuality , that will make all the factors match & then terminate with $m=n$
In general , the Solution is Unique.