Determine the last three digits of
n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) .
This problem is posed by Zi Song Y.
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.
Most correct solutions were variations of this one and the two intended solutions. The most common mistake was not providing enough details, for example no explanation for the formula for the sum.
Some users discovered that the last three digits of the sum do not change as n is increased by 20. However, this phenomenon is not easy to justify. It is not true for the sum of n 5 or n 7 separately, and is related to the formula for the sum.
To find the last three digits, we consider:
n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) ( m o d 1 , 0 0 0 )
This is congruent to the sum of the last three digits of each summand, which, fortunately for us, repeat with a period of 1,000. This results from the fact that
( 1 , 0 0 0 + n ) 7 + ( 1 , 0 0 0 + n ) 5 ≡ n 7 + n 5 ( m o d 1 , 0 0 0 )
by the Binomial Theorem.
That means that the sum from n=0 to 10,000,000 is a multiple of 10,000, or:
n = 0 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 )
= n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) + ( 0 7 + 0 5 ) + ( 1 7 + 1 5 )
≡ 0 ( m o d 1 , 0 0 0 )
Basic arithmetic does the rest.
n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) + 2 ≡ 0 ( m o d 1 , 0 0 0 )
n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) ≡ 9 9 8 ( m o d 1 , 0 0 0 )
And so our answer is 998 .
n
=
2
∑
1
0
0
0
0
0
0
0
n
5
+
n
7
=
n
=
1
∑
1
0
0
0
0
0
0
0
(
n
5
+
n
7
)
-2
let xyz be the last 3 digits of
n
=
1
∑
1
0
0
0
n
5
+
n
7
then xyz will be the last three digits for summation from 1001 to 2000,2001 to 3000 and so on using binomial theorem. there are 10000 such summations so we get n = 1 ∑ 1 0 0 0 0 0 0 0 ( n 5 + n 7 ) %1000=000 on subtracting 2 we get 998.
The question is equivalent to finding the value of the sum $\mod 1000$. For any given $n$ we see that $(1000-n)\mod 1000 = -n$ and thus $(1000-n)^7\mod 1000 = (-n)^7\mod 1000 = -n^7\mod 1000$ and $(1000-n)^5\mod 1000 = (-n)^5\mod 1000 = -n^5\mod 1000$. Thus [\sum^1000 {n=1}(n^7 +n^5) = \sum^500 {n=1}(n^7 +n^5 +(1000 - n)^7 + (1000 - n)^5) = \sum^500_{n=1} (n^7 +n^5 - n^7 - n^5) = 0\mod 1000$.
By basic properties of modular arithmetic we get $\sum^{2000} {n=1001}(n^7 +n^5) = 0\mod 1000$, $\sum^{3000} {n=2001}(n^7 +n ^5) = 0\mod 1000$ etc. Thus the original problem just becomes [\sum^{10000000} {n=2}(n^7+n^5) = \sum^{1000} {n=2}(n^7+n^5)\mod 1000 = \sum^{1000}_{n=1}(n^7 + n^5) - 2\mod 1000 = -2\mod 1000 = 998 \mod 1000.
The final answer is 998
Since, n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 n 7 + n 5 = n = 1 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) − ( 1 7 + 1 5 ) = n = 1 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) − 2
We can prove that 2 × n = 1 ∑ k ( n p ) is always divisible by k if p is an odd number.
Since, we can always write ( k − c ) p as k p + a 1 k p − 1 + a 2 k p − 2 + . . . . . − c p where c is an integer constant and a 1 , a 2 , . . . . . . . ϵ Z . [We don't even have to know the values of a 1 , a 2 , . . . . . . . . . . . I'm not saying that we can't, but we just don't need to.] We can write- k p + a 1 k p − 1 + a 2 k p − 2 + . . . . . + c p as g k + c p where g ϵ Z .
Now, we can write: n = 1 ∑ k ( n p ) = S = 1 p + 2 p + 3 p + . . . . . . . . . . . . + k p But, S = k p + ( k − 1 ) p + ( k − 2 ) p + . . . + 1 p = k p + g 1 k − 1 p + g 2 k − 2 p + . . . . . + g k − 1 k − ( k − 1 ) p
If we add them both we get, 2 S = 2 k p + g 1 k + g 2 k + . . . + g k − 1 k = k × m . Here m = 2 k p − 1 + g 1 + g 2 + . . . . + g k − 1 and m is a integer.
So, 2 × n = 1 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) can be expressed as 1 0 7 × l where l is an integer. Since, 2 × n = 1 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) = 1 0 7 × l So, n = 1 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) = 2 1 0 7 × l = 5 l × 1 0 6
So,
n
=
2
∑
1
0
,
0
0
0
,
0
0
0
n
7
+
n
5
=
n
=
1
∑
1
0
,
0
0
0
,
0
0
0
(
n
7
+
n
5
)
−
(
1
7
+
1
5
)
=
5
l
×
1
0
6
−
2
=
1
0
3
×
5
0
0
0
l
−
2
=
1
0
3
+
1
0
3
+
1
0
3
+
.
.
.
.
.
.
+
1
0
3
−
2
[
5
0
0
0
l
times ]
=
9
9
8
+
4
9
9
9
l
×
1
0
3
So, the last three digits of
n
=
2
∑
1
0
,
0
0
0
,
0
0
0
(
n
7
+
n
5
)
=
n
=
2
∑
1
0
,
0
0
0
,
0
0
0
(
n
7
+
n
5
)
m
o
d
1
0
0
0
=
(
9
9
8
+
4
9
9
9
t
×
1
0
3
)
m
o
d
1
0
0
0
=
9
9
8
First, we show that for an odd number, k > 1 , ∑ i = 1 1 0 0 0 i k ≡ 0 ( m o d 1 0 0 0 ) .
This is because i k + ( − i ) k ≡ 0 ( m o d 1 0 0 0 ) and for k > 1 , 5 0 0 k ≡ 0 ( m o d 1 0 0 0 ) .
Now, using this fact, ∑ i = 1 1 0 0 0 0 0 0 0 ( i 5 + i 7 ) ≡ 0 ( m o d 1 0 0 0 ) . Hence, ∑ i = 2 1 0 0 0 0 0 0 0 ( i 5 + i 7 ) ≡ − 2 ≡ 9 9 8 ( m o d 1 0 0 0 ) and the answer is 9 9 8 .
The function f ( n ) = Σ j = 2 n u 7 + u 5 can be written as f ( n ) = 8 1 ( n 4 + 2 n 3 + 2 n 2 + 4 ) ( n 2 + n + 2 ) ( n + 2 ) ( n − 1 ) . Then f ( 1 0 7 ) = 8 1 ( A ⋅ 1 0 1 4 + 4 ) ( B ⋅ 1 0 7 + 2 ) ( 1 0 7 + 2 ) ( 1 0 7 − 1 ) , for integers A ans B. Continuing this way, for some integer K we obtain f ( 1 0 7 ) = 8 1 ( K ⋅ 1 0 7 + 8 ) ( 1 0 7 + 2 ) ( 1 0 7 − 1 ) = ( K ⋅ 1 0 6 + 1 ) ( 1 0 7 + 2 ) ( 1 0 7 − 1 ) ≡ − 2 m o d 1 0 0 0 . Thus we arrive at 998.
when n=20, the last 3 digits are 998 , and the next summation of 20 terms would go back to such value of last 3 digits, since 20 is a factor of 10,000,000, the summation of 10,000,000 terms could be traced=998.
The instinct is to develop a reccursive relation so that the terms will cancel and produce a formula that is easier to work with. I will break the question up into 2 parts and work with n^5 and n^7 separately although later it will be shown that they both satisfy the same relations.
Let us define: q(n) = q(n-1) + n^5 r(n) = r(n-1) + n^7
Solving for both the recurrence and summing them up, one obtains p(n)=n^4 * (n+1)^4 / 8. We realise that when n = 10^k, 1000 is always a factor since p(10^k)=1000 * (10^(4 * k - 3) * (10^k+1)^4 / 8).
Therefore, the last 3 digits of this is m000 - 1^7 - 1^5 (where m stands for the digits in front of the sum that we do not want) since the summation starts from 2^5 and 2^7. Therefore, the last 3 digits is 998.
any number with the same last 3 digit number that is raise to an integer, has the same last three digit number, like when 2 7 has same last three digit as of 1 0 0 2 7
the sum of the first 1 0 or { 1 , 2 , 3 … 1 0 } has 250 for the last three digits then the next 1 0 or { 1 1 , 1 2 , 1 3 … 2 0 } has 750 and and by doing this, it will make a pattern of { 2 5 0 , 7 5 0 , 2 5 0 … }
by this pattern, the first 2 0 numbers has a sum of 1 0 0 0 or 0 0 0 as its last three digit number. by this manner, the n = 1 ∑ 1 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) has 0 0 0 as its last three digit.
the 0 0 0 last three digits is only from 1 to 1 0 0 0 , but in n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) we started at 2 so we subtract 1 7 + 1 5 = 2 from the overall sum.
so 0 0 0 − 2 = 9 9 8 is the last three digit of n = 2 ∑ 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 )
Let's consider first the summmation of n^7+n^5 from 1 up to 1000000:
If n=1, 1^7+1^5= 1+1 =2
If n=2, 1^7+1^5+2^7+2^5= 2+160= 162
If n=3, 1^7+1^5+2^7+2^5+3^7+3^5= 2592
If n=4, 1^7+1^5+2^7+2^5+3^7+3^5+4^7+4^5= 20000 ...
Multiply all this values by 8, we will get 16, 1296, 20736, 160000, ... These values are equal to 2^4, 6^4, 12^4, 20^4, ... which are also equal to (1^4 x 2^4), (2^4 x 3^4), (3^4 x 4^4), (4^4 x 5^4), ... Therefore the summation of n^7+n^5 from 1 up to n is equal to 1/8 x (n^4) x (n+1)^4. Substitute 1000000 for n, the summation will be equal to 1/8 x (1000000)^4 x (1000001)^4.
To get the last three digits, we have to get the remainder when this expression is divided by 1000.
If 1000000 is 0(mod 1000), then (1000000)^4 is 0^4(mod 1000) or 0(mod 1000).
If 1000001 is 1(mod 1000), then (1000001)^4 is 1^4(mod 1000) or 1(mod 1000).
8 is obviously 8(mod 1000).
Therefore the remainder when 1/8 x (1000000)^4 x (1000001)^4 is divided by 1000 is (0 x 1)/4 or 0.
That is only the remainder of the summation of n^7+n^5 from 1 up to 1000000 when divided by 1000, but how about the remainder of the summation of n^7+n^5 from 2 up to 1000000 when divided by 1000?
It is simple. Simply subtract two from the result. That's because 1^7+1^5 is added to our result. Remember the result that we earlier get is from 1 up to 1000000 not 2 from 1000000.
Subtracting two from 0(mod 1000), the summation of n^7+n^5 from 2 up to 1000000 is -2(mod 1000) or simply 998(mod 1000).
This means that the last three digits of the summation of n^7+n^5 from 2 up to 1000000 is 998.
If the lower limit was 1 andwer would be 0. This is because the last three digits are the same no matter what full residue system mod 1000 you give. when taking the sum from 1 to 10,000,000 we have the sum for 10,000 residue systems. so it is 10,000 times a fixed integer. Hence answer is 0. so when we subtract 2 we get 998.
∑ n = 2 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) = ∑ n = 1 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) − 2 .
So we will find ∑ n = 1 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) m o d 1 0 0 0 and subtract 2 from that.
Let f ( x ) = x 7 + x 5 . We can see that f ( x ) is odd, So f ( k ) + f ( − k ) = 0
Thus, we can pair the numbers, having f ( 1 ) + f ( 9 9 9 ) = f ( 2 ) + f ( 9 9 8 ) = … = f ( 4 9 9 ) + f ( 5 0 1 ) = 0 . It can easily be seen that f ( 5 0 0 ) = 0 and f ( 1 0 0 0 ) = 0 .
This can also be applied to the numbers from 1 0 0 1 to 2 0 0 0 , 2 0 0 1 to 3 0 0 0 , and so on.
So ∑ n = 1 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) m o d 1 0 0 0 is 0 and the desired sum is 9 9 8
Problem Loading...
Note Loading...
Set Loading...
Let ∑ n = 1 1 0 0 0 ( n 7 + n 5 ) ≡ a ( m o d 1 0 0 0 ) .
Since n ≡ i ( m o d 1 0 0 0 ) for some i ∈ { 1 , 2 , 3 , … , 1 0 0 0 } , then, ∑ n = 1 0 0 1 2 0 0 0 ( n 7 + n 5 ) ≡ a ( m o d 1 0 0 0 ) .
In the same way, ∑ n = 2 0 0 1 3 0 0 0 ( n 7 + n 5 ) ≡ a ( m o d 1 0 0 0 ) , and so on.
Therefore, ∑ n = 1 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) ≡ ( 1 0 0 0 0 ) a ≡ 0 ( m o d 1 0 0 0 )
In other words, 2 + ∑ n = 2 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) ≡ 0 ( m o d 1 0 0 0 ) , or ∑ n = 2 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) ≡ 9 9 8 ( m o d 1 0 0 0 ) .
That means the last three digits of ∑ n = 2 1 0 , 0 0 0 , 0 0 0 ( n 7 + n 5 ) is 9 9 8 .