Project Euler
Introduction
Project Euler (named after the famous Swiss mathematician, Leonhard Euler) is a website that consists of a series of problems that test both your mathematical and programming skills. Started in 2001 by Colin Hughes, it has grown to have more than a million users as of 2020. With a new problem added every 10 days on average, the site currently consists of more than 700 problems of varying difficulty. It also has a discussion forum thread for every problem that can be unlocked after you solve that particular problem. Here you could see how others have solved the problem
Let us now try to solve a problem from the archive.
Problem 401
The divisors of 6 are 1,2,3 and 6.
The sum of the squares of these numbers is 1+4+9+36=50.
Let sigma2(n) represent the sum of the squares of the divisors of n.
Thus sigma2(6)=50.
Let SIGMA2 represent the summatory function of sigma2, that is
SIGMA2(n) = Σsigma2(i) for i=1 to n.
The first 6 values of SIGMA2 are: 1,6,16,37,63 and 113.
Find SIGMA2(10^(15)) modulo 109.
Solution
Let us look at sigma2(i) for 1 ≤ i ≤ 6:
Note that
1 appears 6 times
2 appears 3 times
3 appears 2 times
4,5 and 6 each appears once
We can observe that k appears ⌊n/k⌋ times. Therefore,
SIGMA2(n) = Σ ⌊n/k⌋*k²
This requires n iterations
This is still computationally unfeasible when n is as large as 10^(15)
A further observation is that when k is large, the count factor of ⌊n/k⌋ does not change often.
(For example, for k ϵ { ⌊n/2⌋ + 1, n }, this count is always 1.)
So we can calculate the squared divisor sum for many numbers at a time.
This is helpful for k >√(n), and we can bring the run time from O(n) down to O(√(n)).
For a given count of m = ⌊n/k⌋ , which integer values of k yield this m?
By the definition of floor, m ≤ ⌊n/k⌋ , so m * k ≤ n, and k ≤ n/m, thus k ≤ ⌊n/k⌋.
Also by defnition, m > n/k -1, so m*k > n - k, and k * (m+1) > n, and k > n/(m+1), so k > ⌊n/(m+1)⌋
Together, we have: ⌊n/(m+1)⌋ < k ≤ ⌊n/m⌋.
Now we have the result that any k ϵ ( ⌊n/(m+1)⌋, ⌊n/m⌋ ] will give the same as ⌊n/k⌋ = m.
Let k₁ = ⌊n/(m+1)⌋ and k₂ = ⌊n/m⌋.
Now each k ϵ (k1, k2] will contribute m * k² to the answer.
Sum of squares from k₁ to k₂ is k₂*(k₂+1)*(2*k₂+1)/6 - k₁*(k₁+1)*(2*k₁+1)/6
For each m= ⌊n/k⌋ we have its
So for k < √n :
We use the initial way where SIGMA2 = Σ ⌊n/k⌋ * k²
This requires √n iterations.
For k ≥ √n :
Now we can iterate m from 1 to √n and keep adding its contribution to the answer
This requires another √n iterations.
In total, we use 2 *√n iterations ≈ 6.3 * 10⁷ when n = 10^(15) , which is computationally feasible.
Conclusion
There are very few people who have solved all the problems in the archive. Since your code is expected to run in less than a minute, you would learn a lot about the optimisations you could do to speed your code up. So if you want to improve your coding skills or are interested in challenging math problems, I would recommend you to check out this website. The registrations and problems are all completely free.
Website Link: projecteuler.net
An Article By: Coding and Logic Team
DISCLAIMER
Shaastra TechShots’ publications contain information, opinions and data that Shaastra TechShots considers to be accurate based on the date of their creation and verified sources available at that time. It does not constitute either a personalized opinion or a general opinion of Shaastra or IIT Madras. The information provided comes from the best sources, however, Shaastra TechShots cannot be held responsible for any errors or omissions that may emerge.