4

We are given $2$ integers, $a,b$ such that $0\leq\,a$ and $b\leq9)$, that are the first $2$ elements of a series. Each consecutive term of the series is defined as the sum of all the previous elements of the series, modulo $10$. That is, the first element is $a$, the second element is $b$, the third element (let's call it $c$) is $(a+b)\%10$, the fourth element is $(a+b+c)\%10$, where $c= (a+b)\%10$, and so on. If the series contains $n$ elements, how do I find the sum of the series?
One way to do this is just calculate every term and find the sum, but in my case $n$ could be very large, so I need something better than this.

After some calculation , I found that for any given $a$ and $b$,
3rd element $= (1*(a+b))\%10$
4th element $= (2*(a+b))\%10$
5th element $= (4*(a+b))\%10$, and so on, but I'm still not able to generate a formula for the sum for the first $n$ terms.

416E64726577
  • 370
Aditya Roshan
  • 49
  • @416E64726577 sir, i think when any element becomes 0 we will stop and if it becomes 2 , then we can stop as if we got 2 , the pattern will be continued with 2,4,8,6,2,4,8,6,2,4.. and so on, so we can calculate the sum fastly, correct me if i'm wrong – Aditya Roshan Jul 25 '19 at 20:36
  • As you mentioned, you're trying to calculate $a + b + \sum_{k=0}^n(2^k (a+b))% 10$. As modulo doesn't generally distribute, I don't see any obvious closed form$-$but perhaps there is one! – 416E64726577 Jul 25 '19 at 20:41
  • please tell me more – Aditya Roshan Jul 25 '19 at 20:43

2 Answers2

3

As you stated, let

$$c = (a+b)\%10 \tag{1}\label{eq1}$$

Next, let $f_i$, for $i \ge 1$, be the elements of the series, so $f_1 = a$, $f_2 = b$, $f_3 = c$ and, in general, for $i \ge 3$, you get

$$f_i = \left(2^{i-3}c\right)\%10 \tag{2}\label{eq2}$$

Next, note that $2^{5+j} = 32 \times 2^j \equiv 2 \times 2^j \equiv 2^{j+1} \pmod{10}$ for $j \ge 0$. Thus, this shows the values in \eqref{eq2} start repeating, with a period of $4$, beginning at $i = 4$. You can therefore determine the sum $S_n$ based on the value of $n$ being less than $4$ (i.e., $S_1 = a$, $S_2 = a + b$, $S_3 = a + b + c$), else its value based on its quotient and remainder modulo $4$.

John Omielan
  • 47,976
  • whenever i got 2 or 0 i stopped further process, if i got 0 i returned the current sum , if i got 2 then i know that it will now repeat as 2 4 8 6 , thus solved thanks. – Aditya Roshan Jul 25 '19 at 21:08
  • @AdityaRoshan You're welcome. This shows that you sometimes you need to check a bit further to see if there's any particular pattern. – John Omielan Jul 25 '19 at 21:10
2

Note: this assumed that the whole sum was to be reduced $\bmod 10$. It appears not, but I will leave it anyway.

The whole system is linear, so we can compute the values starting with $1,0$ and $0,1 $. If we ignore the mod $10$ we get $$1,0,1,2,4,8,16,\ldots 2^{n-3}\\ 0,1,1,2,4,8,16,\ldots,2^{n-3}$$ Now we can multiply the first by $a$, the second by $b$, add them, and take the result $\bmod 10$. For $n \ge 3$ the result is $$(a+b)2^{n-3} \bmod 10$$ Now if we add these up, because there were two $1$s at the start we just get $$(a+b)2^{n-2} \bmod 10$$

Ross Millikan
  • 374,822
  • sir, but this will help me in getting the nth term , how can i get the sum from this ? – Aditya Roshan Jul 25 '19 at 21:01
  • @RossMillikan Using $a = 3$ and $b = 8$, for just $n = 2$, the sum is $11$ but your answer gives $1$ instead. When adding the values $%10$, i.e., between $0$ and $9$, you can't instead just add the original values and then take the result modulo $10$. Note the OP wants the actual sum of the terms, not what they are modulo $10$. – John Omielan Jul 25 '19 at 21:20
  • @JohnOmielan: I had missed that. I thought the whole sum was to be reduced $\bmod 10$. It is much easier that way. – Ross Millikan Jul 25 '19 at 21:25