The root of all digits

First, we consider $n\equiv S(n) \pmod {9}$ , where $S(n)$ is the digit sum of $n$ .

Due to this fact, the digital root of a number $n$ will be the same as the remainder of the number after dividing by $9$ , as long as the number is not divisible by $9$ . Note: If the number is divisible by $9$ , then the process we will use here will not be able to tell us whether the digital root is $0$ or $9$ , because both $0$ and $9$ are congruent modulo $9$ .

The order that we sum the digits does not matter, and we can even sum the digits in 'chunks' to produce an intermediary result. We can therefore start by summing the consecutive integers that the number is composed of:

$\sum\limits_{k=1}^{500}k=\frac{(500)(501)}{2}=(250)(501)$

Doing some modular arithmetic:

$(250)(501)\equiv(7)(6)\equiv42\equiv6\pmod{9}$

Because the remainder of the number when divided by $9$ is $6$ , the digital root is $\boxed{6}$

I actually did a direct summation of all the digits! Well I mean after I group the digits properly, as follows:

• sum of 1-digit numbers = $1+2+\cdots+9=45$
• sum of 2-digit numbers = $10(1+2+\cdots+9) + (0+1+2+\cdots+9) = 495$
• sum of 3-digit numbers up to 499 = $100(1+2+3+4) + 10(0+1+2+\cdots+9) + (0+1+2+\cdots+9) = 1495$
• sum of the digits of 500 = 5

$\Rightarrow S = 45 + 495 + 1495 + 5 = 2040$ So the digital root of the number is 6.

I didn't notice that this is a number theory problem. If I had I wouldn't have tried it. ;)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def sum_digits(n):
    r = 0
    while n:
        r, n = r + n % 10, n / 10
    return r

number=123
for k in range(456,501):
    number=1000*number+k

while number>=10:
    number=sum_digits(number)

print number