# Find the number of such sequences

Let $N$ be the number of sequences $a_1, a_2, a_3,\ldots,a_{24}$ that satisfy the following conditions.

i) For all $1\le i \le 24$, $1\le a_i \le 24$.

ii) For all $i \equiv 0 \text{ (mod 2)}$, $a_1+a_2+\cdots+a_i \equiv 1 \text{(mod 2)}$.

iii) For all $i \equiv 0 \text{ (mod 3)}$, $a_1+a_2+\cdots+a_i \equiv 2 \text{(mod 3)}$.

If $N=p_1^{a_1}p_2^{a_2}$ where $p_1$ and $p_2$ are prime numbers, find $p_1+a_1+p_2+a_2$.

I found that $a_{i}+a_{i+1} \equiv 0 \pmod{2}$ and $a_i+a_{i+1}+a_{i+2} \equiv 0 \pmod{3}$ for all even $i$ and $i \equiv 0 \pmod{3}$, respectively. Do we have to use the Chinese Remainder Theorem next?

• I think you mean $a_i+a_{i+1}\equiv0\pmod2$. And the two congruences don't have to hold for all $i$, just every second/every third $i$, respectively. Is this a contest problem? – Greg Martin Oct 7 '16 at 1:48
• @GregMartin Yes, it is. – user19405892 Oct 7 '16 at 1:53
• It seems to me that $a_1\equiv a_2\equiv 1\pmod 3$ and simultaneously $a_1+1\equiv a_2\pmod 2$ to go along with what you found, and therefore $a_2=6k+3+a_1$. – abiessu Oct 7 '16 at 2:13

## 1 Answer

For convenience, let $S_n$ be defined by $$S_n = a_1 + a_2 + \dots + a_n,$$ so that you conditions become

• $S_n \equiv 1 \pmod 2$ if $n \equiv 0 \pmod 2$
• $S_n \equiv 2 \pmod 3$ if $n \equiv 0 \pmod 3$.

We will work in blocks of $6$ numbers at a time. There is no restriction on the value of $a_{6k+1}$ other than that $1 \leq a_{6k+1} \leq 24$, so $a_{6k+1}$ can be any of $24$ different values.

For $a_{6k+2}$, we require that $$S_{6k+2} = S_{6k+1} + a_{6k+2} \equiv 1 \pmod 2.$$

This means that if $S_{6k+1}$ is even, then the only restriction on $a_{6k+2}$ is that it must be odd, and if $S_{6k+1}$ is odd, then the only restriction on $a_{6k+2}$ is that it must be even. In either case, there are $12$ options for the value of $a_{6k+2}$.

Similarly, the only restriction on $a_{6k+3}$ is that $$a_{6k+3} \equiv 2 - S_{6k+2} \pmod 3.$$

Since there are $8$ numbers with each possible remainder modulo $3$ amongst the numbers $1, 2, 3, \dots, 24$, we see that there are always $8$ options for the value of $a_{6k+3}$ once all of the previous numbers have been chosen.

Continuing in this way, we see that there are

• $24$ options for the value of $a_{6k+1}$
• $12$ options for the value of $a_{6k+2}$
• $8$ options for the value of $a_{6k+3}$
• $12$ options for the value of $a_{6k+4}$
• $24$ options for the value of $a_{6k+5}$
• $4$ options for the value of $a_{6k+6}$

once all of the previous numbers have been chosen in each case.

Thus there are $24 \times 12 \times 8 \times 12 \times 24 \times 4 = 2^{15} \cdot 3^4$ ways to choose the numbers in each block of $6$ numbers. There are $4$ blocks of $6$ numbers to fill, and so the total number of sequences is $$\left( 2^{15} \cdot 3^4 \right)^4 = 2^{60} \cdot 3^{16}.$$