# Puzzle: Cumulative Sum Divisible by 10

If we sum the first $4$ positive integers, we get $4 + 3 + 2 + 1 = 10$, which I think is pretty cool.

I'm interested in seeing solutions to the following puzzle: If we take the cumulative sum of the first $N$ positive integers, how many times along the way will the sum be divisible by $10$?

In other words, define: $$f(N) = \left|\left\{n \leq N \;:\; \sum_{i=1}^n i = \frac{n(n+1)}{2} \text{ is divisible by 10}\right\} \right|$$

Is there a nice expression for $f(N)$?

-
I think this is a great question! –  mixedmath May 9 '12 at 3:01

## 5 Answers

You need $20$ to divide $n(n+1)$. Note $n$ and $n+1$ are of opposite parity. Hence, $4$ divides either $n$ or $n+1$. $5$ divides either $n$ or $n+1$ since $5$ is a prime. Hence, we have $4$ cases which gives us as discussed below.

$1$. $4|n$ and $5|n$. This case is trivial. Since $(4,5)=1$, we get that $20|n$ and hence $n \equiv 0\bmod 20$.

$2$. $4|n$ and $5|(n+1)$. This means that $n = 4k_4$ and $n+1 = 5k_5$. Hence, we get that $5k_5 - 4k_4 = 1$.

Solving such general congruence fall under the Chinese remainder theorem, as TMM points out in the comments, and is certainly something which you should look at. In this case, we solve it as follows. Clearly, $(k_4,k_5) = (1,1)$ is a solution. In general, if $ax+by$ has integer solutions and $(x_0,y_0)$ is one such integer solution, then all integer solutions are given by $$(x,y) = \displaystyle \left( x_0 + k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{a}, y_0 - k \frac{\text{lcm}[\lvert a \rvert,\lvert b \rvert]}{b} \right)$$ where $k \in \mathbb{Z}$. Hence, we get that $(k_4,k_5) = (1+5k,1+4k)$. This gives us that $n = 20k+4$ i.e. $n \equiv 4 \bmod 20$.

$3$. $4|(n+1)$ and $5|n$. This means that $n = 5k_5$ and $n+1 = 4k_4$. Hence, we get that $4k_4 - 5k_4 = 1$. Clearly, $(k_4,k_5) = (4,3)$ is a solution. Hence, we get that $(k_4,k_5) = (4+5k,3+4k)$. This gives us that $n=20k+15$ i.e. $n \equiv 15 \bmod 20$.

$4$. $4|(n+1)$ and $5|(n+1)$. This case is again trivial. Since $(4,5) = 1$, we get that $20|(n+1)$ and hence $n \equiv 19 \bmod 20$.

To summarize, the solutions are given by

\begin{cases} n \equiv 0\bmod 20 &(\text{ if }4 \text{ divides }n \text{ and }5 \text{ divides }n)\\ n \equiv 4\bmod 20 & (\text{ if }4 \text{ divides }n \text{ and }5 \text{ divides }n+1)\\ n \equiv 15\bmod 20 & (\text{ if }4 \text{ divides }n+1 \text{ and }5 \text{ divides }n)\\ n \equiv 19\bmod 20 & (\text{ if }4 \text{ divides }n+1 \text{ and }5 \text{ divides }n+1) \end{cases}

-
(+1) although I think mentioning the Chinese Remainder Theorem would have been nice –  TMM May 9 '12 at 16:31

Given the expression

$$f(N)=\#\left\{n\le N:\sum_{i=1}^n i=n(n+1)2 \text{ is divisible by 10}\right\},$$

each time when the $n=4,64,1024$, etc., take the root (e.g. in $2^2$, $2^6$, $2^{10}$), therefore, you can form your function in following two ways:

1. $\text{power}\,\%\,4=2$;
2. An arithmetic progression with first term 2 and $d=4$, will give you the powers of two.

Apologies for bad formatting.

-

Hint  If $\rm\:m,n,i\in \mathbb Z\:$ and $\rm\:(n,i) = 1\:$ with $\rm\:m,\:\!m\!+\!i\:$ powers of distinct primes, then

$\rm\quad\phantom{m\!|\:\!\rm n\!+\!i,}\:\ m(m\!+\!i)\:|\:n(n\!+\!i)\$ iff one of the four following cases holds

$\quad\begin{eqnarray} \rm &&&\rm m(m\!+\!i)\!\!\! &|&\rm n &\ \iff\ &\rm n\equiv\:\ \ 0&\rm\pmod{\:m(m\!+\!i)} \\ \rm &&&\rm m(m\!+\!i)\!\!\!&|&\rm n\!+\!i &\ \iff\ &\rm n\equiv -i&\rm\pmod{\:m(m\!+\!i)} \\ \rm m\!&|\:&\rm n,\!\!\!\!&\rm \phantom{m(}m\!+\!i\:&|&\rm n\!+\!i &\ \iff\ &\rm n\equiv\ m&\rm\pmod{\:m(m\!+\!i)} \\ \rm m\!&|&\:\!\rm n\!+\!i,\!\!\!\! &\rm \phantom{m(}m\!+\!i\!\!\!\!\!\!\:&|&\rm n &\ \iff\ &\rm n\equiv -m\!-\!i\!\!\!\!\:&\rm\pmod{\:m(m\!+\!i)} \end{eqnarray}$

Put $\rm\ m=4,\ i=1\:$ to solve your problem.

Hint for the proof: for prime powers $\rm\:p^k\:|\:n(n\!+\!i)\!\iff\! p^k\:|\:n\:$ or $\rm\:p^k\:|\:n\!+\!i\:$ by $\rm\:n,n\!+\!i\:$ coprime, by $\rm (n,n\!+\!i)=(n,i) = 1.$

-

Write $n$ in the form $20k+j$ where $0≤j<20$.

Then you have $n(n+1) = (20k+j)(20k+j+1) = 400k^2 + 40kj + 20k + j^2 + j$ which is obviously a multiple of 20 if and only if $j^2+j$ is. So the problem has been reduced to finding $0≤j<20$ where $j(j+1)$ is a multiple of 20; this occurs for $j=0,4,15,19$, so the solutions all have the form $n=20k+\{0,4,15,19\}$ for some integer $k$.

Where did I get the inspiration to write $n$ in the form $20k+j$? I guessed that it would repeat with period 10 or 20, and I looked at the list of triangular numbers in OEIS and saw that multiples of 10 did indeed appear at $n=4,15,19,20,24$, so 20 seemed to be the way to go.

Why did I guess that it would repeat with period 10 or 20? The main reason is that questions about when an polynomial $P(n)$ is divisible by $q$ usually does something like that, because if you calculate $P(n+q) - P(n)$ the constant term cancels, as do all the terms that are pure in $n$, and leaves you with some higher-order terms that are all divisible by $q$.

I knew that was the thing to try because I have seen a lot of problems of that type.

Addendum: How many solutions lie between 1 and $N$? Write $N=20k+j$ as before, and the answer is $4k$ plus a fudge factor. The fudge factor is 0 if $j<4$, 1 if $4≤j<15$, 2 if $15≤j<19$, and 3 if $j=19$.

-
I can't see why your substitution is useful, given that the conclusion is the same as the premise: n(n + 1) must be a multiple of 20, j(j + 1) must be a multiple of 20. Am I missing something? –  UncleZeiv May 9 '12 at 13:34
@uncleZeiv: The difference is that while $n$ can be any number, $j$ must be less than 20. –  MJD May 9 '12 at 14:36

Only the ones digit matters when figuring multiples of ten. Also, a multiple of ten plus a multiple of ten is a multiple of ten. Thus, we can find the applicable patterns that we need to consider:

First pattern to get to a multiple of ten (starting with 1):

1+2+3+4 = 10


Second pattern (starting from 5, since we counted 4 last in the previous pattern):

5+6+7+8+9+0+1+2+3+4+5 = 50


Third pattern (starting from 6):

6+7+8+9 = 30


Fourth pattern (starting from 5):

0


Repeat back to pattern 1

Now we have the 4 sequential patterns that we need to consider, which consist of 20 total numbers. I'm more of a programmer than a mathematician, so here's one way to represent the solution programmatically (in this case using JavaScript), with a working fiddle to see it in action:

function getMultiplesOfTenWhileCountingTo(finalCount){
//There are 4 multiples every 20 numbers
var multiples = Math.floor(finalCount/20) * 4;

//Add the additional multiples based on the remainder
var remainder = finalCount % 20;
if(remainder >= 4){
multiples++;
}
if(remainder >= 15){
multiples++;
}
if(remainder >= 19){
multiples++;
}
return multiples;
}

-