# Properties of Digit Sums

This notebook is known to be compatible with Julia 0.5. A basic foreknowledge of induction and mathematical proof will enrich your experience.

How would you check for divisibility by $3$ or $9$? You might know the trick. A number is divisible by $3$ if and only if the sum of its digits is divisible by $3$, and a number is divisible by $9$ if and only if the sum of its digits is divisible by $9$.

Why does this trick work? In this notebook, we'll look at some computational evidence, and then talk a bit about modular arithmetic, a computational strategy that we can use to prove these results.

## What is a digit sum?

Hold on. What do we mean by digit sum? Let's define the concept mathematically. Let $n$ be a positive whole number with base-$10$ representation $d_id_{i-1}d_{i-2}\dots d_3d_2d_1$, where all the $d_1$ are digits from $0$ to $9$, and we take the convention that $d_i\ne 0$. Then define the _sum of digits_ of $n$, denoted by $\operatorname{s}(n)$, as follows:

\begin{equation}
\operatorname{s}(n) = \sum_{k=1}^i d_k
\end{equation}

Why do we define the digits in reverse? That will make expressing $n$ as a sum of powers of $10$ easier. In fact, recall the definition of the base-$10$ system:

\begin{equation}
n = \sum_{k=1}^i d_k \cdot 10^{k-1}
\end{equation}

## How do I calculate it?

Let's first see how to extract the digits of a number, say, $1997$.


```julia
digits(1997)
```




    4-element Array{Int64,1}:
     7
     9
     9
     1



Wow, that's incredibly convenient. These digits are in the order we want too, counting from the right. We can compute each individual digit easily too:


```julia
d = digits(1997)
d[4]
```




    1



If you are used to a zero-based indexed programming language, note that Julia indexes arrays starting at $1$. So the fourth digit (counting from the right) is $1$. So far so good. Now how can we compute the sum of the digits?


```julia
sum(digits(1997))
```




    26



Doesn't get any easier than that! This syntax is so clean and descriptive that there is no point even making a helper function to compute it. Now that we have some syntax, let's verify the properties we alluded to initially. First, let's verify that a number is divisible by $9$ if and only if its sum of digits is divisible by $9$. To compute whether a number is divisible by $9$, we compute what it's remainder would be when divided by $9$, and check if it is zero. In Julia, the remainder operator is `%` (or the `rem` function), and the equality testing operator is `==`.


```julia
1997 % 9 == 0
```




    false




```julia
819 % 9 == 0
```




    true



Okay, so what numbers between $1$ and $1000$ are divisible by $9$? We can compute a vector of those numbers easily by using a `filter`. We want to find all elements $n$ in `1:1000` where `n % 9 == 0`. Here's how to write that in code:


```julia
A = filter(n -> n % 9 == 0, 1:1000)
```




    111-element Array{Int64,1}:
       9
      18
      27
      36
      45
      54
      63
      72
      81
      90
      99
     108
     117
       ⋮
     900
     909
     918
     927
     936
     945
     954
     963
     972
     981
     990
     999



Now let's do the same computation, using the sum of digits as the divisibility test:


```julia
B = filter(n -> sum(digits(n)) % 9 == 0, 1:1000)
```




    111-element Array{Int64,1}:
       9
      18
      27
      36
      45
      54
      63
      72
      81
      90
      99
     108
     117
       ⋮
     900
     909
     918
     927
     936
     945
     954
     963
     972
     981
     990
     999




```julia
A == B
```




    true



Success. We've computed the multiples of $9$ two ways, and both times we got the same result. But that's not a proof! **rest to come**

4af0cbbd39f5ce8fc7e90212b062f2def5d7f41a
ipynb
Jupyter Notebook
digit-sums/digitsums.ipynb
TotalVerb/EMAC
dbbb6b7875d07f125d90f71d31d46074fbf2c6df
MIT
digit-sums/digitsums.ipynb
TotalVerb/EMAC
dbbb6b7875d07f125d90f71d31d46074fbf2c6df
MIT
digit-sums/digitsums.ipynb
TotalVerb/EMAC
dbbb6b7875d07f125d90f71d31d46074fbf2c6df
MIT
Qwen/Qwen-72B
1. YES
2. YES