The digit sum of a number is the sum of the digits in the number. Let $n$ be a natural number.
Then the digit sum of $n$ is $S(n)=\displaystyle\sum_{k=0}^{\lfloor{\log_{10} n}\rfloor}\frac{1}{10^k}\left(n\mod10^{k+1}-n\mod10^k\right)$, as is seen in this wiki page (I am interested in the base $10$ case only).
I am aware that the number of digits in $n$ equals $\lfloor{\log_{10} n}\rfloor+1$ in base $10$. Numerous posts are there regarding how to write a computer code for finding the sum of digits in a given positive number. However, I haven't found any source of the digit sum formula and I want to know how it is derived. I just need the basic idea. Any link to a source would be great too.
$\endgroup$3 Answers
$\begingroup$In this formula, $n\mod10^k$ means the remainder after $n$ is divided by $10^k$. Notice that this is precisely the last $k$ digits of $n$, e.g. $4355\mod 100=55$. Therefore $(n\mod 10^{k+1} - n\mod 10^k)$ is $10^k$ times the $k$-th digit of $n$.
$\endgroup$ 0 $\begingroup$An example easily makes clear the logic of the formula : Lets take $$N=123456$$ Then, for example, the third digit is $$\frac{(3456-456)}{1000}=\frac{(N\mod 10000)-N\mod 1000)}{1000}$$
I think just summing up the digits is efficient enough to determine the digit-sum. In PARI/GP, the number is converted to a vector and the components are just summed up. No clue whether there is a better method in general.
$\endgroup$ $\begingroup$$N = \sum_{i=0}^n a_i*10^i$.
What is the $k$th digit[1] in terms of $N$?
$N \mod 10^{k+1} = \sum_{i=0}^k a_i*10^i$. That is "stripping off" all the digits past $k$ and keeping just the first $k$.
$N\mod 10^{k} = \sum_{i=0}^{k-1} a_i*10^i$. That is "stripping off" all the digits at $k$ and beyond, and keeping just the first $k-1$ digits.
$N \mod 10^{k+1}-N\mod 10^{k} = \sum_{i=0}^k a_i*10^i -\sum_{i=0}^{k-1} a_i*10^i = a_k*10^k$. We stripped off all the digits past the $k$th digit. And then we subtracted all the ones before the $k$th digit. So all that is left is the $k$th digit (times the appropriate power of $10$).
Hence $\frac 1{10^k}(N \mod 10^{k+1}-N\mod 10^{k}) = a_k$; the $k$th digit.
So $\sum_{k=0}^n a_k = \sum_{k=0}^n \frac 1{10^k}(N \mod 10^{k+1}-N\mod 10^{k})$.
And... as you know, if $N$ has $n+1$ digits then $n = \lfloor \log N\rfloor$.
So $\sum_{k=0}^n a_k = \sum_{k=0}^{\lfloor \log N\rfloor} \frac 1{10^k}(N \mod 10^{k+1}-N\mod 10^{k})$
[1] I'm taking "$k$th digit" to mean digit in the $10^k$ position. I suppose one counld nitpick and say that is really the $k + 1$th digit, (or the $n+1 - k$th digit) but... let's not.
$\endgroup$
