0
$\begingroup$

I'm the novice, sorry if I can't ask more specifically.

If the given number is 2-digits integer. We have sum = number*20%199%19.

Can you prove the above formula? And if it is an n-digits integer, what is the formula?

Thanks so much!

$\endgroup$
6
  • $\begingroup$ would this help $\endgroup$
    – Aven Desta
    Mar 3, 2020 at 6:58
  • 1
    $\begingroup$ @Babydesta I know we can use for-loop or while-loop for calculating it. But I ask if it exists a formula for the general case. Thank u though. $\endgroup$ Mar 3, 2020 at 7:01
  • $\begingroup$ For two digit number. if $n = [ab]$ where $a$, $b$ denote the digits. Then $b = n\%10$ and $a = \frac{n-b}{10}$, thus $sum = (n\%10) + ( \frac{n-b}{10})$ $\endgroup$
    – Aven Desta
    Mar 3, 2020 at 7:06
  • $\begingroup$ For three digit number. if $n = [abc]$, then $c = n\%100$ and $[ab] = \frac{n-c}{10}$ , and so on $\endgroup$
    – Aven Desta
    Mar 3, 2020 at 7:09
  • $\begingroup$ If $n = [a_0a_1...a_k]$, then $a_k=n\%10^{k-1}$, and $[a_0a_1...a_{n-1}] = \frac{n-a_k}{10}$, (ofcourse don't forget to replace $a_k$ with the previous calculated value) and so on $\endgroup$
    – Aven Desta
    Mar 3, 2020 at 7:12

3 Answers 3

1
$\begingroup$

Why does your formula work? Multiplication by $20$ shifts all digits one to the left and doubles them (possibly generating one carry to their left). Taking remainder modulo $199$ "equates" $200$ with $1$, hence for brings the original tens (now double-hundreds) to the unit place (while the one possible carry is ignored). After that, $19$ repeats the trick one place down.

This generalizes - with caveats. We might think that for three digits we can go by $(((20n)\bmod 1999)\bmod 199)\bmod 19$ but this fails: The final result cannot be $\ge 19$ whereas $999$ should produce $27$ as result. Also, after bringing the original hundreds and tens to the unit place, they may cause an additional carry so that the factor $2$ is not save enough any more. We could switch to a factor of $30$, but why not use $100$ and solve the problem for up to eleven digits (i.e., all that are guaranteed to have a digit sum of at most two digits)? $$\begin{align}(((((((((((100n)&\bmod 9999999999999)\bmod 999999999999)\\&\bmod 99999999999)\bmod 9999999999)\\&\bmod 999999999)\bmod 99999999)\\&\bmod 9999999)\bmod 999999)\\&\bmod 99999)\bmod 9999)\bmod 999)\bmod 99 \end{align}$$

$\endgroup$
1
  • $\begingroup$ I still don't understand how it can return sum of the number. $\endgroup$ Mar 3, 2020 at 8:04
0
$\begingroup$

Hint:

If $n = [a_0a_1...a_k]$, then

$a_k=n\%10^{k-1}$, and

$[a_0a_1...a_{k-1}] = \frac{n-a_k}{10} = \frac{n-n\%10^{k-1}}{10}$,

$\endgroup$
0
$\begingroup$

I found a closed form for Sum of digits of $n$ in base $10$ $=$ $\sum_{k=0}^{m} [\frac{n}{10^k}]-10\times [\frac{n}{10^{k+1}}]$ where $10^m$ is the largest power of $10$ less than ot equal to $n$ and $[]$ is the floor function. The rationale behind this is that taking the floor of $\frac{n}{10^k}$ 'deletes' the last $k$ digits.So one can use this to obtain the $k$th digit as $[\frac{n}{10^{k-1}}]-[\frac{n}{10^k}].Now just sum from $k=1$ to $k=$ the number of digits of n.

Remark: Using this similar technique one can extend this to arbitrary bases.Particularly in the case of $base-p$ where $p$ is prime we have the following note that $\left\lfloor\frac{(n)_p}{p}\right\rfloor$ is the number formed by removing the last digit of $(n)_p$.So $\left\lfloor\frac{(n)_p}{p^{k-1}}-\right\rfloor -p\times\left\lfloor\frac{(n)_p}{p^k}\right\rfloor$ is the $k$th digit of $(n)_p$ using this we can find each digit and sum them to get $S_p(n)=\sum_{k=1}^{m}{\left\lfloor\frac{(n)_p}{p^{k-1}}-\right\rfloor -p\times\left\lfloor\frac{(n)_p}{p^k}\right\rfloor}$ now expanding and using Legendre we see that $S_p(n)=v_p(n!)-p.v_p(n!)+n$ Hence we get $v_p(n!)=\frac{n-S_p(n)}{p-1}$ $\blacksquare$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .