# Using the invariance principle: how to solve $n+d(n)+d(d(n))=m$?

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?

-
Is the $d(n)$ defined relative to base $10$? – Sasha Aug 13 '12 at 17:24
Yes, d(n) defined relative to base 10. – Swapnanil Saha Aug 13 '12 at 17:25
What is the invariance principle in this context? – Ross Millikan Aug 13 '12 at 17:31
Well, I found the question in the context of invariance principle in the book, 'Problem Solving Strategies....Arthur Engel'.I would not have asked the question if I was so informed. If you feel the question belongs to some other domain, I would request you to edit. – Swapnanil Saha Aug 13 '12 at 17:36
What is the number of exercise in this book? – Norbert Aug 13 '12 at 17:57

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.

-
Do you insist I must replace m with 3k? And, is a general solution possible? – Swapnanil Saha Aug 13 '12 at 18:12
I 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$. – Sasha Aug 13 '12 at 18:21

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.

-