# Summing (and not summing) to $0\bmod9$

Let $n_0,n_1,n_2\in\{1,2,\dots,8\}$ and consider the sum

\begin{align*} S&=\sum_{k=0}^8n_{k\bmod3}\\&=n_0+n_1+n_2+n_0+n_1+n_2+n_0+n_1+n_2. \end{align*}

Is there an efficient way to produce all possible triples $(n_0,n_1,n_2)$ such that the following two conditions hold:

• $\sum_{k=0}^8n_{k\bmod3}=3n_0+3n_1+3n_2\equiv0\bmod9$
• $\sum_{k=i}^jn_{k\bmod3}\not\equiv0\bmod9$, for $0\leq i\leq j\leq8$, and if $i=0$, then $j\ne8.$

That is, I want $S$ to sum to a multiple of $9$, and every "sub-sum" of $S$ (not necessarily starting from the first term) to not be a multiple $9$.

For examples:

• $(1,1,4)$ is a valid triple, since $1+1+4+1+1+4+1+1+4=18$ and each sub-sum does not produce a multiple of $9$.

• $(7,6,8)$ would not be valid, even though $7+6+8+7+6+8+7+6+8=63$, we have a sub-sum $6+8+7+6=27$.

There are a few things I have taken away so far:

• $n_0+n_1+n_2\equiv0\pmod3$
• Either $n_0+n_1+n_2\equiv3\pmod9$ or $n_0+n_1+n_2\equiv6\pmod9$
• If $(a,b,c)$ is a valid triple, then $(9-a,9-b,9-c)$ must also be valid.

I can trudge through the guess-and-check method, but I'm hoping there is a quicker way, as I'd like to generalize this. Thanks!

• Definitely, none of $n_k$ should be divisible by $9$.
• If $n_k$ is divisible by $3$, then one of the following sums will be divisible by $9$, (depending on the value of $n_0+n_1+n_2\bmod9$): $$n_k+(n_{k+1}+n_{k+2}+n_{k+3})\qquad n_k+(n_{k+1}+n_{k+2}+n_{k+3})+(n_{k+4}+n_{k+5}+n_{k+6})$$

## Proof that these conditions are sufficient:

For an easier notation, I will use $m,n,k$ instead of $n_i$s. Let $n,m,k$ be integers that are not divisible by $3$, but, $m+n+k$ is divisible by $3$, and $m+n+k$ is not divisible by $9$. Then, as you saw $9|3(m+n+k)$.

Let's look at the sub-sums.

• Any sub-sum with length one would not be divisible $3$ by our choice.
• Any sub-sum with length two would be of the form $m+n,n+k,k+m$. As $m+n+k$ is a multiple of $3$ and none of $m,n,k$ are multiples of $3$, $m+n+k-m,m+n+k-n,m+n+k-k$ are not divisible by $3$.

Now let's look at the sums with more than $2$ terms. As after each $m$ there is an $n$, and after each $n$ there is a $k$, the first $3$ terms of a sub-sum consists of a combination of $m,n,k$.

In other words, a sub-sum of length $3$ is always $m+n+k$. We know that this number is not divisible by $9$.

A sub-sum of length $4$ is equal to $(m+n+k)+$ a sub-sum of length $1$. As a sub-sum of length $1$ sum is not divisible by $3$ and $m+n+k$ is divisible by $3$, a sub-sum of length $4$ is not divisible by $3$.

A sub-sum of length $5$ is equal to $(m+n+k)+$ a sub-sum of length $2$. As a sub-sum of length $2$ sum is not divisible by $3$ and $m+n+k$ is divisible by $3$, a sub-sum of length $5$ is not divisible by $3$.

Similarly, a sub-sum of length $6,7,8$ is can be decomposed as $2(m+n+k)$+ a smaller sub-sum. And by the exact same reasoning, they can't be divisible by $9$.

## Finding $m,n,k$ satisfying these conditions

Observe that $3$ divides $m+n+k$ but does not divide $m,n,k$ implies $m\equiv n\equiv k\pmod3$.

As $3\not\lvert m$, we can choose $m$ from $6$ different choices. Then, for $n$ we're left with $3$ different choices, as we need $3|m-n$. At the end, we have only $2$ choices for $k$, as we want $3|m-k$ but do not want $9|m+n+k$. So, there are $36$ gvalid triplets.

• That's great. It follows that $m,n,k\equiv1\bmod3$ or $m,n,k\equiv2\bmod3$. Perfect explanation. – Bonnaduck Jun 5 '16 at 1:56
• Also, I accidentally downvoted, and it wont let me change it unless the answer is edited. Feel free to fix that / at the end, so I can change it to an upvote. – Bonnaduck Jun 5 '16 at 1:57
• I added the part about finding all valid triplets to the answer – Emre Jun 5 '16 at 2:03