Let’s discuss a number theory problem from Brilliant. Problem link is given at the end.

We’re asked to compute:

x=12015gcd(x,2015) \sum_{x = 1}^{2015} \gcd(x, 2015)

where gcd(a,b) stands for the greatest common divisor function.

We’ll actually solve this problem without writing any computer program because where’s the fun in that?

This problem is actually solvable in a variety of ways. I’ll discuss one approach here, and I’ll try to add different approaches some time in the future (no guarantees!)

The problem seems very difficult to solve by hand, but actually it’s not. You need to the following to solve it:

  • From 1 to n, there are exactly nk numbers divisible by k

Let’s first factorize 2015. The prime factorization of 2015 is:

2015=513312015 = 5 * 13 * 31

So the set of all divisors of 2015 comprises d={5,13,65,155,403,2015}. We have excluded 1 because all numbers excluding the numbers in d have a gcd of 1 with 2015.

Only the members of d have a gcd>1 with 2015. What are the possible gcds >1? Let us list them:

gcd(5,2015)=5gcd(13,2015)=13gcd(31,2015)=31gcd(65,2015)=65=513gcd(155,2015)=155=531gcd(403,2015)=403=1331gcd(2015,2015)=2015=51331

So the possible gcd values are the same the member of d. Let’s find out how many numbers are divisible by the numbers in d. One thing to note here is that, we want to find out how many numbers are divisible by only a particular member of d. For example, when figuring out how many numbers are divisible by 5, we are interested in finding out numbers divisible only by 5 and not any other number. As there could be numbers like 130 which have both 5 and 13 or 465 which have both 5 and 31 as factors, we have to exclude these numbers when calculating the numbers divisible by 5. For this reason, it is helpful to start from the last member of d, find out its divisors, move to the member to its left until we’ve reached the first member, excluding extraneous number in the way (in each iteration the extraneous cases will only involve the cases processed previously).

How many number are from 1 to 2015 are divisible only by 2015? The answer if 1, 2015 itself.

How many number are from 1 to 2015 are divisible only by 403=1331? There are 2015403=5 numbers divisible by 403 from 1 to 2015, but one of the numbers, namely 2015 is divisible by 5 also. So the actual answer is 51=4.

How many number are from 1 to 2015 are divisible only by 155=531? There are 2015155=13 numbers divisible by 155 from 1 to 2015, but one of the numbers, namely 2015 is divisible by 13 also. So the actual answer is 131=12.

Using similar reasoning, we find that there are 30 numbers divisible only by 65=513 from 1 to 2015.

Now we come to single digit numbers. How many numbers from 1 to 2015 are divisible only by 5? The answer is 2015511230=360 (subtracting the numbers that has divisors either 13 or 31 or both). Similarly 120 numbers are divisible only by 13 and 48 numbers divisible only by 31.

Now that we’ve all the counts, let’s express them in concrete terms. Let, A, B and C be the set of numbers divisible by 5, 13 and 31 respectively. Using Inclusion-Exclusion Principle we find that,

|ABC|=|A|+|B|+|C||AB||AC||BC|+|ABC|

So from 1 to 2015 there are 403+155+6531135+1=575 numbers divisible by either 5, 13 or 31. So there are 2015575=1440 numbers not divisible by any of 5, 13 or 31.

Finally we can now plug in the numbers to find the answer,

x=12015gcd(x,2015)=gcd(5,2015)360+gcd(13,2015)120+gcd(31,2015)48+gcd(65,2015)30+gcd(155,2015)12+gcd(403,2015)4+gcd(2015,2015)1+x{5,13,31,65,155,403,2015}gcd(x,2015)1440=5360+13120+3148+6530+15512+4034+20151+11440=13725

We can verify our answer by writing a simple C++ program:

#include <iostream>
#include <algorithm>
int main(){
int g = 0;
for(int x = 1 ; x <= 2015 ; ++x){
g += std::__gcd(x,2015);
}
std::cout << g << '\n';
return 0;
}
// output : 13725

Problem link :- Sum of all