This is Argyn's blog. I comment on topics of my interests such as software, math, finance, and music. Also, I write about local events in Northern Virginia, USA and all things related to Kazakhstan

Wednesday, February 15, 2006

Sum-of-Digits Iterations

Today a co-worker mentioned an interesting math problem. Let's take any number and sum up all its digits. Then sum up the digits of that sum... and so on, untill we end up with one digit. I used to entertain myself with exactly this sort of excercises when riding a bus to musical school many years ago, but I didn't actually try to study the properties of this sum. So, tonigh I came home and started googling the subject. It took less than 5 minutes to find a relevant link.
Given a positive integer n, let s_B(n) denote the sum of the base-B
digits of n. If we apply the function s_B iteratively we eventually
arrive at a single-digit integer (in the range 0 to B-1) which we will
denote by r_B(n). We will say that n "reduces to" r_B(n) under iteration
of the sum-of-digits function.

PROPOSITION 1: For any given base B, the positive integer n reduces to
the residue of n modulo B-1. In other words, r_B(n) = n modulo B-1.

No comments: