Sum of GCD's?!

Algebra Level 4

Consider the sequence 50 + n 2 50 + n^2 for positive integer n n :

51 , 54 , 59 , 66 , 75 , 51, 54, 59, 66, 75, \ldots

If we take the greatest common divisor of 2 consecutive terms, we obtain

3 , 1 , 1 , 3 , 3, 1, 1, 3, \ldots

What is the sum of all distinct elements in the second series?


The answer is 272.

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.

3 solutions

Joel Tan
Nov 20, 2014

Note that the n n th term is n 2 + 50 n^{2}+50 for any positive integer n n . Suppose that x x is a possible GCD. Then:

x n 2 + 50 , x ( n + 1 ) 2 + 50 x|n^{2}+50, x|(n+1)^{2}+50

Now we subtract to get x ( n + 1 ) 2 + 50 n 2 50 = 2 n + 1 x|(n+1)^{2}+50-n^{2}-50=2n+1 .

Thus x ( 2 n + 1 ) ( 2 n 1 ) = 4 n 2 1 x|(2n+1)(2n-1)=4n^{2}-1

However, x 4 ( n 2 + 50 ) = 4 n 2 + 200 x|4 (n^{2}+50)=4n^{2}+200 .

From the last two equations, subtracting gives x 201 x|201 . Since x x is a positive integer, x = 1 , 3 , 67 , 201 x=1, 3, 67, 201 .

It suffices to show that all of them work.

1 and 3 have been shown to work in the question, the 33rd and 34th term have a GCD of 67 and the 100th and 101st term have a GCD of 201. Thus the answer is 1 + 3 + 67 + 201 = 272 1+3+67+201=272 .

Just Perfect! Thanks. I dunno why some are reporting it.

Satvik Golechha - 6 years, 6 months ago

Log in to reply

Maybe some are thinking that by lagrange interpolation the sequence is not properly defined :)

Joel Tan - 6 years, 6 months ago

Log in to reply

I'm not complaining, but that's true. Unfortunately, by interpolation we can assume that the next term in the sequence 1,2,3,4,5,6, __ is something like π 100 i cos 2.9 \sqrt{\pi}^{100i\cos{2.9}}

Trevor Arashiro - 6 years, 6 months ago

Log in to reply

@Trevor Arashiro Well, I dunno what interpolation is. This was meant ter be a gen'ral mathematical series. I even added "Mental Ability" ter make it sure that it's a numb'r series.

Satvik Golechha - 6 years, 6 months ago

Nice Thinking !!

Shubhendra Singh - 6 years, 6 months ago

Very nice solution.

Jakub Kocák - 6 years, 6 months ago

dude- that was great.

Ash Dab - 6 years, 6 months ago

This is surprising that we both have the exact same solutions.

Kartik Sharma - 6 years, 4 months ago

A Python script that solves problem

- - coding: utf-8 - -

Author: Michael Fitzgerald 9/14/17 """

Consider the sequence 50 + n^2 for positive integer n

51,54,59,66,75......

If we take the greatest common divisor of 2 consecutive terms, we obtain

3,1,1,3..........

What is the sum of all distinct elements in the second series?

def gcd(a, b): #Euclid algorithm if b == 0: if not a in distinct g c d: distinct g c d.append(a) return a else: return gcd(b, a % b) # recursive

a = 50 arr = [] distinct g c_d = []

for i in range(1,1000000): x = a + i**2 arr.append(x) if len(arr) > 2: arr.pop(0) gcd(arr[1], arr[0])

str1 = ','.join(str(e) for e in distinct g c d)
print str1 print 'The sum of all distinct elements in the second series is: %d' \ % sum(distinct
g c d)

Michael Fitzgerald - 3 years, 9 months ago

How did you got form: X|4n^2 +1 To X|4(n^2+50) ?

And why do you restrict x to be up to 201?

Moshe Bouhnik - 3 years ago

Can someone explain the steps in this solution between finding the difference 2n + 1 and finding the factors of 201? Given my inexperience with this type of problem, those steps seem unmotivated.

What is the point of multiplying 2n + 1 and 2n - 1, or subtracting 4n^2 - 1 from 4n^2 + 200?

Is any of this related to polynomial division, which was what I tried and failed to use to solve the problem?

Emily Falces - 2 years, 9 months ago

I did not understand the problem as stated.

Robert Dale - 3 years, 12 months ago
Cody Han
Nov 21, 2014

I wrote a little bit of Haskell code for this one, where binaryGCD comes from the arithmoi package and nub comes from Data.List (nub returns a list's unique elements):

1
2
3
nums = 51 : 54 : zipWith (\a b -> b + (b - a) + 2) nums (tail nums)
gcds = zipWith binaryGCD nums (tail nums)
nub gcds

Of course, this assumes that no new GCD values appear when the numbers get extremely large. Output: [3, 1, 67, 201] .

David Krüger
Apr 9, 2016

Very simple, the for loop extends to much larger numbers as well:

1
2
3
4
5
6
7
8
a = zeros(1,100);

for n = 1:100
    a(n) = gcd((50+n^2),(50+(n+1)^2));
end

A = unique(a);
sum(sum(A))

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...