What is the last three digits of the sum of all values of N , 1 ≤ N ≤ 9 9 9 , such that 1 + 2 + 3 + … + N is a perfect square?
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.
Pell's Equation is a classical theory, closely connected to such number theory topics as continued fractions, algebraic units, and Diophantine approximations. Several solutions of this problem use some version of this theory.
Very elegant!
Love this solution. I took a much more basic approach. Unfortunately, I see some connections but I don't exactly understand how you jump from the equation x^2-2y^2=+ or -1 to the continued fraction.
We have 1 + 2 + ⋯ + N = 2 N ( N + 1 ) . Suppose that 2 N ( N + 1 ) = k 2 ⇔ N ( N + 1 ) = 2 k 2 ⇔ ( 2 N + 1 ) 2 − 8 k 2 = 1 . Let 2 N + 1 = x , we have x 2 − 8 k 2 = 1 . The fundamental of the Pell's equation x 2 − 8 k 2 = 1 is ( x 1 , k 1 ) = ( 3 , 1 ) . Therefore, the general solution is given as follow : { x i + 1 = 3 x i + 8 k i k i + 1 = 3 k i + x i Since 1 ≤ N ≤ 9 9 9 , we have 3 ≤ x ≤ 1 9 9 9 . Therefore, we can find the following solutions : ( x 1 , k 1 ) = ( 3 , 1 ) , ( x 2 , k 2 ) = ( 1 7 , 6 ) , ( x 3 , k 3 ) = ( 9 9 , 3 5 ) , ( x 4 , k 4 ) = ( 5 7 7 , 2 0 4 ) . The corresponding values of N are : 1 , 8 , 4 9 and 2 8 8 . The sum of these values are 3 4 6 .
We have: i = 1 ∑ N i = 2 N ( N + 1 ) = s 2 with s in an integer.
Or N ( N + 1 ) = 2 s 2 .
Suppose N is devided by the prime number k, then N+1 is not devided by k, Therefore, each prime number cannot appear in Prime Factorization of both N and N+1. Therefore, in N and N+1, there are a perfect square and a double of perfect square, we have two cases:
Cases 1: N = 2 p 2 , N + 1 = q 2 , so q 2 − 2 p 2 = 1 . According to [ P e l l ′ s E q u a t i o n ] ( h t t p : / / m a t h w o r l d . w o l f r a m . c o m / P e l l E q u a t i o n . h t m l ) and the condition 1 ≤ N ≤ 9 9 9 , we find two values of N: 8 and 288.
Cases 2: N = p 2 , N + 1 = 2 q 2 . Similarly, we have two values of N: 1 and 49.
The sum of four values of N: 1+8+49+288=346, so the answer is 346
Pell′sEquation
Next time don't put the Markdown code (the link) in \ ( \ )
Mã Markdown để nhúng link anh đừng bỏ trong tag LaTex \ ( \ ) nhé ^^
The explicit formula for the sum 1 + 2 + 3 + . . . + N is, of course, 2 N ⋅ ( N + 1 ) . In order for this to be a square, either both N and 2 N + 1 are square or both N + 1 and 2 N are square because N > 1 → g cd ( N , N + 1 ) = 1 → g cd ( 2 N , N + 1 ) = 1 , g cd ( N , 2 N + 1 ) = 1 .
If 2 N + 1 = x is square, then 2 x − 1 = N must be square. We remind ourselves that N ≤ 9 9 9 → x ≤ 4 9 9 and quickly check to find that only x = 1 , 2 5 satisfy these conditions. Therefore, N = 1 , 4 9 in this case.
If 2 N = y is a square, then 2 y + 1 = N + 1 is also a square. Again, y ≤ 4 9 9 , and we find that only y = 4 , 1 4 4 work. Therefore, N = 8 , 2 8 8 in this case.
All the values of N which satisfy the given conditions are then 1 , 8 , 4 9 , 2 8 8 and so we report the last three digits of 1 + 8 + 4 9 + 2 8 8 = 3 4 6 , which are, of course, 3 4 6 .
Without the use of Pell's equation, very nice.
N and N+1 cannot share a divisor. So sum can be expressed as N (N+1)/2=2a^2 b^2 with N=2a^2 or N=b^2 and gcd (a, b)=1. Now find all perfect squares of the form 2a^2 +/- 1. Checking 0 < a < 23 gives solutions N = 1, 8, 49 or 288.
Every triangular number is of the form 2 t ( t + 1 ) . Now, we want to solve
2 t ( t + 1 ) = s 2
With a bit of algebra this becomes ( 2 t + 1 ) 2 = 8 s 2 + 1
and then letting x = 2 t + 1 and y = 2 s , we get
x 2 − 2 y 2 = 1 .
This is Pell's equation, and the solutions for this are x = P 2 k + P 2 k − 1 , y = P 2 k , where P k is the kth Pell Number . Now, the solutions for N are 2 1 ( P 2 k + P 2 k − 1 − 1 ) .
The values of N < 1 0 0 0 that satisfies the condition are 1 , 8 , 4 9 , 2 8 8 , with sum 3 4 6 .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
The sum of the series 1+2+3+4+...+N is given by S = N*(N+1)/2
In order for S to be a perfect square we can consider 2 distinct cases,
1) N is a perfect square and (N+1)/2 is a perfect square
1<=N<1000. Also,if (N+1)/2 is to be an integer, N should be an odd number.
Hence the numbers we can consider for N are
1,9,25,49,81,121,169,225,289,361,441,529,625,729,841,961
The ones for which (N+1)/2 is a perfect square are 1,49
2) N+1 is a perfect square and N/2 is a perfect square
N+1 is a perfect square and since N will be divisible by 2,it must be an even number.
So,the values of N to be considered will be
8,24,48,80,120,168,224,288,360,440,528,624,728,840,960
Of which only 8,288 satisfy the condition N/2 is a perfect square
Hence N can take the values 1,8,49,288
So,the sum of all the values of N is = 1+8+49+288=346
The sum N(N+1)/2 is a perfect square. Case 1 : If N is even, then both N/2 and (N+1) should be squares. By trial, we see, N = 8, 288. Case 2 : In N is odd, then both N and (N+1)/2 should be squares. By trial, we see, N = 1, 49. So the answer = 1+8+49+288 = 346
In Python:
import math
def is_square(n):
return math.sqrt(n).is_integer()
if __name__ == '__main__':
squares = []
for n in range(999):
sum = 0
for n2 in range(n+1):
sum += n2+1
if is_square(sum): squares.append(n+1)
allsum = 0
for n in squares:
allsum += n
print(str(allsum)[-3:])
While a computer is a very helpful tool, our Algebra/Number Theory solvables are meant to be done by hand. We just started the Computer Science weekly challenge series on Brilliant, you may want to check it out for more appropriate programming challenges.
Keep such solutions to yourself.
N(N+1)/2=X^2 with X in an integer.(given condition) Or N(N+1)=2X^2 as we know if N is divided by the prime any number k, then N+1 is not divided by k, Therefore, each prime number cannot appear in Prime Factorization of both N and N+1. so, N and N+1, there are a perfect square and a double of perfect square now we can have two conditiions N=2p^2 and N+1=q^2 or q^2−2p^2=1. its a PELL'S equation Refer en.wikipedia.org/wiki/Pell...'s equation and en.wikipedia.org/wiki/Pell... number
and the condition 1≤N≤999, two values of N are 8 and 288. Cases 2: N=p^2,N+1=2q^2. again weget two values of nN: 1 and 49.so sum of 4 values of N is 1+8+49+288=346, so the answer is 346
N(N+1)/2=X^2 with X in an integer.(given condition) Or N(N+1)=2X^2 as we know if N is divided by the prime any number k, then N+1 is not divided by k, Therefore, each prime number cannot appear in Prime Factorization of both N and N+1. so, N and N+1, there are a perfect square and a double of perfect square now we can have two conditiions N=2p^2 and N+1=q^2 or q^2−2p^2=1. its a PELL'S equation Refer en.wikipedia.org/wiki/Pell...'s equation and en.wikipedia.org/wiki/Pell... number
and the condition 1≤N≤999, two values of N are 8 and 288. Cases 2: N=p^2,N+1=2q^2. again weget two values of nN: 1 and 49.so sum of 4 values of N is 1+8+49+288=346, so the answer is 346
Problem Loading...
Note Loading...
Set Loading...
Recall that ∑ k = 1 N k = N ( N + 1 ) / 2 . Suppose N ( N + 1 ) / 2 = M 2 . Since N , N + 1 cannot have any common factors greater than 1 (as they are relatively prime), either N = 2 y 2 or N + 1 = 2 y 2 . In the first case, we obtain M 2 = y 2 ( 2 y 2 + 1 ) or x 2 = ( M / y ) 2 = 2 y 2 + 1 . Similarly, in the second case, we obtain M 2 = ( 2 y 2 − 1 ) y 2 or x 2 = ( M / y ) 2 = 2 y 2 − 1 . Therefore, we wish to find solutions to the Pell equation x 2 − 2 y 2 = ± 1 , which relate to the convergents of the continued fraction representation of 2 = 1 + 2 + 2 + 2 + ⋯ 1 1 1 . These are 1 1 , 2 3 , 5 7 , 1 2 1 7 , 2 9 4 1 , … , corresponding to the solutions ( x , y ) = { ( 1 , 1 ) , ( 3 , 2 ) , ( 7 , 5 ) , ( 1 7 , 1 2 ) , ( 4 1 , 2 9 ) , … } . Note that since N ≤ 9 9 9 , 2 y 2 < 1 0 0 0 , or y < 2 3 . Therefore, we have four solutions: N = { 1 , 8 , 4 9 , 2 8 8 } , the sum of which is 3 4 6 .