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$

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.