Series of numbers that are divided by 3

Question

This is a logical problem and I can't solve it. The problem goes like this:

---

There is a series of numbers: $$3, 2, 1, 5$$

There is four ways to add the consecutive terms to have a number that is divided by 3 without leaving remainder (3 1 5 is not consecutive so it doesn't count):

• 3, that sums up 3.
• 3 2 1, that sums up 6.
• 2 1, that sums up 3.
• 1 5, that sums up 6.

There is another series that is: $$6, 1, 4, 124, 3, 6, 512, 3, 1, 33, 2, 2, 32, 100, 813, 4, 41, 1, 3, 8, 213, 5, 7, 61, 8, 42, 1, 4, 2, 20, 8$$

How many ways are there to sum up consecutive numbers that are divided by three?

It's there some trick? Fastest way to solve it?

Answer 1

Admittedly, I can't think of a solution that doesn't involve at least some tedium. However, I can at least think of a way to simplify the series itself and the approach. Do you know of modular arithmetic? If we take each of those numbers mod 3, that means we consider their remainder after being divided by 3, either 0, 1, or 2. If two numbers have the same such remainder, we say that they are congruent modulo 3. For example, $6 \cong 0 (mod 3)$. Or $101 \cong -1 (mod 3)$. Congruence comes from something called equivalence relations, which you don't need to understand, but is something very useful to know.

The example you gave can be rewritten as

$0, 2, 1, 2$

or

$0,-1,1,-1$.

We still want to sum up the numbers to get a multiple of 3, but it's much simpler to look at now. We also know a few things by looking at it this way:

1) We can add a multiple of $3$ to any sequence and still have a multiple of $3$, since it's just adding $0 mod 3$.

2) Numbers congruent $1$ and numbers congruent $2$ "cancel out" in the sense that their sum will be a multiple of $3$.

3) Having $3$ $1$s or $3$ $-1$s will cancel themselves out. In face, we can say that the difference between the number of $1$s we have and the number of $-1$s we have must be a multiple of 3.

From there, I think it's just tedium, though you could write a computer program to do it for you, but that's a different matter.

Answer 2

Hint: Keep a running total sequence mod 3.

Answer 3

You can look at the partial sums reduced modulo 3.

Suppose the original sequence is $a_1\ldots a_n$, then define a new sequence $b_0\ldots b_n$ by $b_k = \sum_{i=0}^k a_i\pmod{3}$. So basically you make the sequence of $b$'s by starting with a $0$ and then adding the next $a$ and reducing modulo $3$. Now if $b_k=b_l$ for some $i\neq j$ then $ 0 = b_k-b_l=\sum_{i=k}^l a_i \pmod{3}$ and we have found a sequential sum that is divisible by three.

So in your first example $(a_i)_i = (3, 2, 1, 5)$ then $(b_i)_i = (0, 0, 2, 0, 2)$. Now we are looking for places in the $b$ sequence where both numbers are the same:

• $b_0=b_1$ which corresponds to the sequence $3$.
• $b_0=b_3$ which corresponds to $3,2,1$.
• $b_1=b_3$ which corresponds to $2,1$.
• $b_2=b_4$ which corresponts to $1,5$.

To find the total number of consecutive sequences that have a sum divisible by three it is enough to count all pairs of indicies $i,j$ such that $b_i = b_j$. But this is simple with combinatorics. If $x$ is the number of zeros in the sequence $y$ the number of ones and $z$ the number of twos. Then the total number is ${x \choose 2} + {y\choose 2} + {z\choose 2}$.

Indeed in the example $x=3$, $y=0$ and $z=2$ and ${3\choose 2} + {0\choose 2} +{2\choose 2} = 3+0+1=4$

Answer 4

6,1,4,124,3,6,512,3,1,33,2,2,32,100,813,4,41,1,3,8,213,5,7,61,8,42,1,4,2,20,8

Replace these terms with their remainders when divided by 3:

0,1,1,1,0,0,2,0,1,0,2,2,2,1,0,1,2,1,0,2,0,2,1,1,2,0,1,1,2,2,2

This should be easier to visualize.

count them from left to right:

0; 0111;01110;011100;011100201;......

111;1110;11100;11100201;111002010;.....

0,1,1,1,0,0,2,0,1,0,2,2,2,1,0,1,2,1,0,2,0,2,1,1,2,0,1,1,2,2,2

1,1,0,0,2,0,1,0,2,2; 1,1,0,0,2,0,1,0,2,2,2,1;1,1,0,0,2,0,1,0,2,2,2,1,0;...

and so on.

Answer 5

Combining Jorik's and fleablood's answers: from the sequence reduced modulo $3$

$$0,1,1,1,0,0,2,0,1,0,2,2,2,1,0,1,2,1,0,2,0,2,1,1,2,0,1,1,2,2,2$$

we get the sequence of partial sums modulo $3$:

$$0,0,1,2,0,0,0,2,2,0,0,2,1,0,1,1,2,1,2,2,1,1,0,1,2,1,1,2,0,2,1,0$$

I hope I have that right! Now it's easy: this sequence contains $11$ $0$'s, $11$ $1$'s, and $10$ $2$'s. So from Jorik's answer, the number of sequences is

$${11 \choose 2} + {11 \choose 2} + {10 \choose 2} = 55 + 55 + 45 = 155$$

Answer 6

how isn't there an application that you can just enter a number and get a list of every divisible number up to a specified range, Like say you wanted to get every number divisible by 12 up to 40,000

anyone get what I'm saying?

like sure you can just enter the number on a calculator and add it to itself then keep hitting the equals key but that's a lot of tedious work