What is the remainder when a_{2013} is divided by 7?

[anemone]

Consider a sequence given by \(\displaystyle a_n=a_{n-1}+3a_{n-2}+a_{n-3}\), where \(\displaystyle a_0=a_1=a_2=1\).

What is the remainder of \(\displaystyle a_{2013}\) divided by \(\displaystyle 7\)?

 

[chisigma]

Consider a sequence given by \(\displaystyle a_n=a_{n-1}+3a_{n-2}+a_{n-3}\), where \(\displaystyle a_0=a_1=a_2=1\).

What is the remainder of \(\displaystyle a_{2013}\) divided by \(\displaystyle 7\)?

Operating modulo 7 we have...

$$a_{0}=1$$
$$a_{1}=1$$
$$a_{2}= 1$$
$$a_{3} = 1 + 3 + 1 = 5$$
$$a_{4} = 5 + 3 + 1 = 2\ \text{mod}\ 7$$
$$a_{5} = 2 + 1 + 1 = 4\ \text{mod}\ 7$$
$$a_{6} = 4 + 6 + 5 = 1\ \text{mod}\ 7$$
$$a_{7} = 1 + 12 + 2 = 1\ \text{mod}\ 7$$
$$a_{8} = 1 + 3 + 4 = 1\ \text{mod}\ 7$$
$$a_{9} = 1 + 2 + 1 =5\ \text{mod}\ 7$$

... and we can stop because the sequence is mod 7 periodic with period 6. Now is $2013\ \text{mod}\ 6 = 3$, so that the requested number is $a_{3}=5$...

Kind regards

$\chi$ $\sigma$

 

[Opalg]

I agree with chisigma on the level of algebra, but not on the level of arithmetic. In fact, reducing all the coefficients mod 7 as we go along,

$a_{n+3} = a_{n+2} + 3a_{n+1} + a_{n}$,

$a_{n+4} = a_{n+3} + 3a_{n+2} + a_{n+1} = (a_{n+2} + 3a_{n+1} + a_{n}) + 3a_{n+2} + a_{n+1} = 4a_{n+2} + 4a_{n+1} + a_{n}$,

$a_{n+5} = a_{n+4} + 3a_{n+3} + a_{n+2} = (4a_{n+2} + 4a_{n+1} + a_{n}) + 3(a_{n+2} + 3a_{n+1} + a_{n}) + a_{n+2} = a_{n+2} + 6a_{n+1} + 4a_{n}$,

$a_{n+6} = a_{n+5} + 3a_{n+4} + a_{n+3} = (a_{n+2} + 6a_{n+1} + 4a_{n}) + 3(4a_{n+2} + 4a_{n+1} + a_{n}) + (a_{n+2} + 3a_{n+1} + a_{n}) = a_{n}$

(for all $n\geqslant0$). So the sequence repeats with period $6$. It starts with $(a_0,a_1,a_2,a_3,a_4,a_5) = (1,1,1,5,2,4)\pmod7$, and since $2013=3\pmod6$ it follows that $a_{2013} = a_3 = 5\pmod7.$

 

[anemone]

Thanks to both chisigma and Opalg for the submission to this problem and I've been really impressed with the creativity that gone into the two approaches above and please allow me to thank you all again for the time that the two of you have invested to participate in this problem. :)

 

[CellCoree]

To find the remainder of a_{2013} divided by 7, we can use the given sequence a_n=a_{n-1}+3a_{n-2}+a_{n-3} and work backwards. Since a_0=a_1=a_2=1, we can first find a_3 by plugging in the values for a_2, a_1, and a_0 into the sequence.

a_3=a_{3-1}+3a_{3-2}+a_{3-3}
a_3=a_2+3a_1+a_0
a_3=1+3+1
a_3=5

Next, we can find a_4 by plugging in the values for a_3, a_2, and a_1.

a_4=a_{4-1}+3a_{4-2}+a_{4-3}
a_4=a_3+3a_2+a_1
a_4=5+3+1
a_4=9

We can continue this process until we reach a_{2013}. However, we can observe a pattern in the remainders of the terms. The remainders of the terms in the sequence are: 1, 3, 5, 2, 6, 4, 1, 3, 5, 2, 6, 4, 1, 3, 5, 2, 6, 4, ... This pattern repeats every 6 terms. Therefore, the remainder of a_{2013} divided by 7 will be the same as the remainder of a_{2013 mod 6}, which is a_{3}.

a_{2013 mod 6}=a_3=5

Therefore, the remainder of a_{2013} divided by 7 is 5.