Inspired by shubhendra Singh

Number Theory Level 4

A sequence is defined as follows a 1 = a 2 = a 3 = 1 a_1=a_2=a_3=1 , and, for all positive integers n n , a n + 3 = a n + 2 + a n + 1 + a n a_{n+3}=a_{n+2}+a_{n+1}+a_n . Given that a 28 = 6090307 , a 29 = 11201821 a_{28}=6090307, a_{29}=11201821 , and a 30 = 20603361 a_{30}=20603361 , find the remainder when ∑ k = 1 28 a k \displaystyle\sum^{28}_{k=1} a_k is divided by 1000.

Also try this .


The answer is 834.

View wiki
Parth Lohomi by Parth Lohomi , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Parth Lohomi
Apr 16, 2015

Define the sum as s. Since a n = a n + 3 − a n + 2 − a n + 1 a_n\ = a_{n + 3} - a_{n + 2} - a_{n + 1} , the sum will be:

s = a 28 + ∑ k = 1 27 ( a k + 3 − a k + 2 − a k + 1 ) s = a 28 + ( ∑ k = 4 30 a k − ∑ k = 3 29 a k ) − ( ∑ k = 2 28 a k ) s = a 28 + ( a 30 − a 3 ) − ( ∑ k = 2 28 a k ) = a 28 + a 30 − a 3 − ( s − a 1 ) s = − s + a 28 + a 30 s = a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \\ s = a_{28} + \left(\sum^{30}_{k=4} a_{k} - \sum^{29}_{k=3} a_{k}\right) - \left(\sum^{28}_{k=2} a_{k}\right)\\ s = a_{28} + (a_{30} - a_{3}) - \left(\sum^{28}_{k=2} a_{k}\right) = a_{28} + a_{30} - a_{3} - (s - a_{1})\\ s = -s + a_{28} + a_{30}

Thus s = a 28 + a 30 2 s = \frac{a_{28} + a_{30}}{2} , and a 28 , a 30 a_{28},\,a_{30} are both given; the last four digits of their sum is 3668 3668 , and half of that is 1834 1834 Therefore, the answer is 834 \boxed{834}

7 Helpful 1 Interesting 0 Brilliant 0 Confused

@Parth Lohomi , we really liked your comment, and have converted it into a solution. If you subscribe to this solution, you will receive notifications about future comments.

Brilliant Mathematics Staff - 6 years, 1 month ago
Pranjal Jain
Feb 6, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
long int a,b,c,s,t;
a=1;
b=1;
c=1;
s=2;
for (int i=1;i<27;++i)
{
s=s+a;
t=a+b+c;
c=b;
b=a;
a=t;
}
cout<<s;
getch();
return 0;
}

It returns 13346834.

13346834 ≡ 834 m o d 1000 13346834\equiv 834 \mod 1000

1 Helpful 0 Interesting 0 Brilliant 0 Confused

@Parth Lohomi Can you post the algebraic solution? Thanks!

Calvin Lin Staff - 6 years, 4 months ago

Log in to reply

Define the sum as s. Since a n = a n + 3 − a n + 2 − a n + 1 a_n\ = a_{n + 3} - a_{n + 2} - a_{n + 1} , the sum will be:

s = a 28 + ∑ k = 1 27 ( a k + 3 − a k + 2 − a k + 1 ) s = a 28 + ( ∑ k = 4 30 a k − ∑ k = 3 29 a k ) − ( ∑ k = 2 28 a k ) s = a 28 + ( a 30 − a 3 ) − ( ∑ k = 2 28 a k ) = a 28 + a 30 − a 3 − ( s − a 1 ) s = − s + a 28 + a 30 s = a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \\ s = a_{28} + \left(\sum^{30}_{k=4} a_{k} - \sum^{29}_{k=3} a_{k}\right) - \left(\sum^{28}_{k=2} a_{k}\right)\\ s = a_{28} + (a_{30} - a_{3}) - \left(\sum^{28}_{k=2} a_{k}\right) = a_{28} + a_{30} - a_{3} - (s - a_{1})\\ s = -s + a_{28} + a_{30}

Thus s = a 28 + a 30 2 s = \frac{a_{28} + a_{30}}{2} , and a 28 , a 30 a_{28},\,a_{30} are both given; the last four digits of their sum is 3668 3668 , and half of that is 1834 1834 Therefore, the answer is 834 \boxed{834}

@Calvin Lin ,check it out!

Parth Lohomi - 6 years, 3 months ago

Log in to reply

Very nice. Could you post this as a separate solutions, instead of a comment? Thanks!

Calvin Lin Staff - 6 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...