Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
2  
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? –  userNaN Aug 13 '12 at 17:57

2 Answers 2

up vote 1 down vote accepted

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.

enter image description here

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.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.