0
$\begingroup$

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
$\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$
2
$\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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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