Let’s discuss a number theory problem from Brilliant. Problem link is given at the end.
We’re asked to compute:
x=1∑2015gcd(x,2015)
where 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 to , there are exactly numbers divisible by
Let’s first factorize . The prime factorization of is:
2015=5∗13∗31
So the set of all divisors of comprises . We have excluded because all numbers excluding the numbers in have a of with .
Only the members of have a with . What are the possible s ? Let us list them:
So the possible values are the same the member of . Let’s find out how many numbers are divisible by the numbers in . One thing to note here is that, we want to find out how many numbers are divisible by only a particular member of . For example, when figuring out how many numbers are divisible by , we are interested in finding out numbers divisible only by and not any other number. As there could be numbers like which have both and or which have both and as factors, we have to exclude these numbers when calculating the numbers divisible by . For this reason, it is helpful to start from the last member of , 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 to are divisible only by ? The answer if , itself.
How many number are from to are divisible only by ? There are numbers divisible by from to , but one of the numbers, namely is divisible by also. So the actual answer is .
How many number are from to are divisible only by ? There are numbers divisible by from to , but one of the numbers, namely is divisible by also. So the actual answer is .
Using similar reasoning, we find that there are numbers divisible only by from to .
Now we come to single digit numbers. How many numbers from to are divisible only by ? The answer is (subtracting the numbers that has divisors either or or both). Similarly numbers are divisible only by and numbers divisible only by .
Now that we’ve all the counts, let’s express them in concrete terms. Let, , and be the set of numbers divisible by , and respectively. Using Inclusion-Exclusion Principle we find that,
So from to there are numbers divisible by either , or . So there are numbers not divisible by any of , or .
Finally we can now plug in the numbers to find the answer,
We can verify our answer by writing a simple C++ program:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sharing is caring. Share this story in...
Share: Twitter Facebook LinkedIn