Let $x$ be a base $k$ number with digits: $d_1 d_2 \cdots d_n$

(This implies the value of $x$ is $ d_1k^{n-1} +d_2k^{n-2} + \dots +d_{n-1}k+ d_n$)

We define $R(x)$ to be the "digit sum root":

If $x < k$, $R(x) = x$

Otherwise $R(x) = R(d_1 + d_2 + \dots + d_n)$

That is, we keep adding up the digits until we have a single digit. (all in base k)

What interesting properties does the function $R(x)$ have? For example, what can we say about $R(x + y)$? or $R(xy)$? and so on? How can we calculate $R$ efficiently for large $x$?

  • 1
    $\begingroup$ It has all the nice properties one might desire, and that we are perhaps familiar with in the case $k=10$. Hint: $x\equiv R(x)\pmod{k-1}$. $\endgroup$ – André Nicolas Aug 14 '12 at 19:10
  • $\begingroup$ Look on Wikipedia under "digital root": en.wikipedia.org/wiki/Digital_root. $\endgroup$ – mjqxxxx Aug 14 '12 at 19:12
  • $\begingroup$ I suspect you will have something like $\varphi(x)=\displaystyle\max_{n\leq x}R(n)=O(\ln x)$ $\endgroup$ – S4M Aug 14 '12 at 19:18
  • $\begingroup$ @AndréNicolas - looking at base 10, one has zero divisors $(3 \times 3 = 9)$. If one were to choose base 8 or base 12 this would not be the case. $\endgroup$ – Mark Bennet Aug 14 '12 at 19:23

Hint $\rm\ R(x)\equiv x\pmod{k\!-\!1}.\:$ It's the radix $\rm\,k\,$ analog of casting out $9$'s for radix $10$ (decimal).

Remark $\ $ You can find much further discussion in prior posts on casting nines.


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.