Let $d(n)$ be the digital sum of $n$. How to solve $n+d(n)+d(d(n))=m$, where $n$ and $m$ are natural?
Using the invariance principle: how to solve $n+d(n)+d(d(n))=m$?
-
0Pg. 13, Q 55. Note that I've changed it, for a general solution. – 2012-08-13
2 Answers
Not a solution, simply a large size observation. May be deleted once a full solution is posted.
Notice that the left-hand-side is always a multiple of $3$. Indeed, let $ n = \sum_{k=0}^{\ell} d_k \cdot 10^k $ Observe, that $n \equiv d(n) \mod 3$, by virue of $10^k \equiv 1 \mod 3$.
Then $ \left(n + d(n)\right) \bmod 3 = \sum_{k=0}^{\ell} d_k \cdot \left(10^k +1 \right) \bmod 3 = \left(-\sum_{k=0}^{\ell} d_k \right) \bmod 3 = \left(-d(n) \bmod 3\right) = \left(-d(d(n))\right) \bmod 3 $
Thus the equation is only solvable if $m$ is a multiple of $3$.
Here is a plot of the left-hand-side for $1 \leqslant n \leqslant 3^4$, which shows that the solution is not unique.
It also seems, empirically, that $\left(n + d(n) + d(d(n))\right) \bmod 9 = 3\left(n \bmod 3\right)$, although I do not know how to prove that.
-
1I claim that if $m$ is not a multiple of $3$, then no solution exists. From the plot, the solution is not unique. For instance, for $m=18$, equation has two solutions, $n=6$ and $n=12$, but for $m=27$, there are three solutions, $n=9$, $n=15$ or $n=21$. – 2012-08-13
Note that for any positive $x$, we have $L(x) \le d(x) \le 9L(x)$, where $L(x)$ is the number of decimal digits in $x$ and is monotonic (unlike the digit sum itself). This allows us to define a rapidly converging iteration on the interval where $n$ may be found for a given $m$. Specifically, suppose we know that $n \ge a$. Then $ \begin{eqnarray} m &=& n+d(n)+d(d(n)) \\ &\ge& n + L(n) + L(L(n)) \\ &\ge& n + L(a)+L(L(a)) \end{eqnarray} $ implies that $n \le m - L(a) - L(L(a))$. Similarly, if we know that $n \le b$, we can derive the lower bound $n \ge m - 9L(b) - 9L(9L(b))$. This suggests the iteration $ [a_{i+1}, b_{i+1}]=[\max(a_i, m-9L(b_i)-9L(9L(b_i))),\min(b_i, m-L(a_i)-L(L(a_i)))], $ where we can start with $[a_0,b_0]=[1,m]$. When this iteration reaches a fixed point, we can simply check the values it contains, and are guaranteed to find all solutions for $n$.
This method converges rapidly to a narrow interval. For instance, starting with $m=34657812654812376587236687521$, one reaches the bounds $m-288 \le n \le m-31$ in two iterations; checking these values gives $n=m-149$ and $n=m-155$ as the only two solutions.