2
$\begingroup$

Definition Given integer $a$ and $b$, with $a>1$, there exist integer $r$

Let W be the function , function define as follows

$$W(a,b)=r$$

Where $$r=r_1+r_2+...+r_{m+1}$$ And

$$a\cdot q_1=b+r_1$$ $$a\cdot q_2=q_1+r_2$$ $$a\cdot q_3=q_2+r_3$$ $$\vdots$$ $$a\cdot q_{m+1}=q_m+r_{m+1}=a$$ Up to $q_{m+1}=1$

And

$0\leq r_i<a$ for $i={1,2,...,m+1}$.

More simply

$a^{m+1}=b+r_1+ar_2+a^2r_3+...+a^mr_{m+1}$

For example $W(5,17)=4$.

Here are some More interesting properties which I already proved

$r+b=1 \mod a-1$

$W(odd,odd)=even$

$W(odd,even)=odd$

I want more information on such type of function/algorithm. Properties of this type of function which deep connection with number theory. its really helpfull for me.

$\endgroup$
6
  • $\begingroup$ Could you be more precise please. Like what are the lines $aq = b + r$ Euclidean division ? PS : For Tex use {} and not () for $q_{m+1}$ $\endgroup$ Commented Mar 1, 2019 at 18:22
  • $\begingroup$ @Bleuderk now is it ok $\endgroup$
    – Pruthviraj
    Commented Mar 1, 2019 at 18:57
  • $\begingroup$ For the case of $a=2$, this seems highly related to 2's complement: en.wikipedia.org/wiki/Two%27s_complement where in your case the equation is $-b = r_1+ar_2+a^2r_3+...+a^mr_{m+1} - a^{m+1}$. $\endgroup$
    – antkam
    Commented Mar 1, 2019 at 19:14
  • $\begingroup$ @antkam thanks, But not getting the expected results $\endgroup$
    – Pruthviraj
    Commented Mar 1, 2019 at 19:58
  • $\begingroup$ perhaps you can explain where 2's complement do not give expected results (when $a=2$)? then i can perhaps understand the differences between that and what you're looking for... $\endgroup$
    – antkam
    Commented Mar 1, 2019 at 20:02

1 Answer 1

1
$\begingroup$

This answer assumes $b>0$. Also, while this does not give useful references, it does map the original problem into a very well-known related problem.

Take $m$ to be the smallest integer s.t. $a^{m+1} \ge b$, i.e. $m = \lceil \log{b}/\log{a} \rceil - 1$.

As you said, $a^{m+1}=b+r_1+ar_2+a^2r_3+...+a^mr_{m+1}$.

Rearranging, we get: $(a^{m+1} - b) = r_{m+1} a^m + ... + r_3 a^2 + r_2 a^1 + r_1 a^0 $.

In other words, the sequence of $m+1$ digits $(r_{m+1}, ..., r_3, r_2, r_1)$ is the representation of the non-negative integer $(a^{m+1} - b)$ in base $a$, and so $W(a,b) =r=$ the digit sum in this base-$a$ representation.

E.g. for $a=5, b=17$ we have:

  • $m+1 = 2$ since $5^2 > 17$

  • $a^{m+1} - b = 5^2 - 17 = 25-17 = 8 = 13_5$ (i.e. $13$ in base $5$).

  • Sum of digits $W(5,17) = r = 1+3 = 4$ as desired.

E.g. proof that $b + r = 1 \mod (a-1)$:

  • $a^k \mod (a-1) = 1^k \mod (a-1) = 1$ for any $k$

  • So $\mod (a-1)$ we have: $r = \sum r_k = r_{m+1} a^m + ... + r_3 a^2 + r_2 a^1 + r_1 a^0 = (a^{m+1} - b) = 1 - b$.

You can probably prove many more interesting things about $W(a,b)$ based on understanding it as the digit sum of $(a^{m+1} - b)$ in base $a$.

$\endgroup$
2
  • $\begingroup$ Actually I know this information. But I'm looking more Deep reference $\endgroup$
    – Pruthviraj
    Commented Mar 2, 2019 at 2:19
  • $\begingroup$ haha, oh well. so you're really looking for references on the digit sum (for any given base $a$)? interesting... $\endgroup$
    – antkam
    Commented Mar 2, 2019 at 2:48

You must log in to answer this question.

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