Let us jump right into Problem 108 of Project Euler which reads
In the following equation x, y, and n are positive integers.
For n = 4 there are exactly three distinct solutions:
What is the least value of n for which the number of distinct solutions exceeds one-thousand?
NOTE: This problem is an easier version of problem 110; it is strongly advised that you solve this one first.
We could possibly brute force, but my guess is that it would take a rather long time to do so. So instead I started fiddling around with the equation to get some insight into the problem.
Starting with the original
we can see that both x and y needs to be greater than n since they both need to be non-negative. This means that we can express the equation as
where , meaning that they are integers strictly larger than zero.
Putting this on a common denominator gives us
So both s and r are divisors of n^2, which also means that all divisor pairs of will give us a solution to the problem. However, only half of the divisor pairs will give a unique solution since you can simply swap r and s and get a solution as well.
So if d(n) is a function giving us the number of divisors of n, we are looking for the first n such that d(n^2) / 2 > 1000. All numbers have an even number of divisors unless is a divisor of n. In that case the number will have an odd number of divisors. I wont prove this, but I will leave it for you to figure out. In our case we have which is also a divisor, therefore we are looking for a solution to which have (d(n^2) + 1) / 2 > 1000, where the division is an integer division.
Finding divisors
The huge task in this exercise is to actually find the smallest number with many divisors. In Problem 12 we were asked to find the number of divisors of a number. Where we established that we could use the prime factorization to find the number of divisors such that if we have the number N we have
and then the number of divisors will be
However, we can cheat a bit so instead of factoring we will factor and the number of factors of will then be
since we have that
This will help us significantly since it is much easier to factor a smaller number.
The algorithm I use for prime factorization requires a list of prime numbers, so I started probing around to figure out what I needed. I found that (2357111317)^2 has 2187 divisors, which is more than the 1999 we need in order to solve the problem, so we can set the upperlimit of the prime list to 17, and if a number have a prime factor larger than 17, that is not the number we are looking for anyway.
Coding the solution
I have changed the divisor counting function as described above, which resulted in the C# code
private long NoDSquared(long number, long[] primelist) { long nod = 1; long exponent; long remain = number; for (int i = 0; i < primelist.Length; i++) { // In case there is a remainder this is a prime factor as well // The exponent of that factor is 1 if (primelist[i] * primelist[i] > number) { return nod * 2; } exponent = 1; while (remain % primelist[i] == 0) { exponent+=2; remain = remain / primelist[i]; } nod *= exponent; //If there is no remainder, return the count if (remain == 1) { return nod; } } return nod; }
and then the main loop for the code is
long n = 1; long result = 0; long limit = 1000; while (true) { if ((NoDSquared(n, primes) + 1) / 2 > limit) { result = n; break; } n++; }
Nothing more to say than we should run the code which on my computer gives me the result
The first n with more than 1000 solutions is 180180
and the time
Solution took 31,0487 ms
Wrapping up
While this most certainly solved problem 108 within the time limit, it is far from fast enough for Problem 110, so we will be revisiting this problem soon enough.
You can find the complete source code here as always.
Hello, nice solution I solved this on the third or fourth try. I used this approach: I found the the number we are looking for must be very composite (lot of factors) so I made some test, some tries and finally found solution.
P.S this is very stupid factorization metod but it was from my beginings
Your pages show very well with the MathML. I wonder whether you ca let me know what sort of software that you are using to get the Math symbols right. Thanks.
Hi Robert
I use wordpress as you probably have figured out and to render the math I use the optimized latex plugin
How would you solve Diophantine equation a*c1+b*c2+c*c3+d*c4+…+i*c9=n?
Consider the equation: 1/x + 1/y= 1/6
Acc. to you,
6=2^1 * 3^1
So, No. of distinct possible are= (1+1) * (1+1)
= 4
But following solution are possible: (7,42) (8,24) (9,18) (10,15) (12,12)
These are 5 solutions.
Please clear my doubt and correct me where I am wrong.
You can use this formula. http://math.stackexchange.com/questions/977926/dfrac1a-dfrac1b-dfrac1c-a-b-c-in-mathbbn-with-no-common-factor-fi/977944#977944
@Manas Srivastava
According to Kristian, the number of distinct possibilities is floor((d(n^2) + 1) / 2), which for 6 becomes floor([(2*a2 + 1)*(2*a3 + 1) + 1]/2) = 5.
Note that a2 and a3 are both 1.
2187 is simply 3^7 , the number of divisors of any number that’s a product of 7 different prime factors, following the formula you quoted.
I think you were well on the way to solving this problem without any code whatsoever.
2*3*5*7*11*13*17 > 2^4 *3*5*7*11*13*17 > 2^2 * 3^2 * 5*7*11*13*17
3^7 == 3^5 * (2*4+1) > 3^4 * (2*2+1) * (2*2+1) > 1999
when i find analysis’s Kristan i try it in hackkerank but i only earn 50 d 🙂 , i used miller rabin but still wrong with testcacse
5,7,8,9,11.
https://www.hackerrank.com/contests/projecteuler/challenges/euler108/problem?h_r=profile
I think this analysis’s Kristan “n^2=rs ” have relate to analysis’s pytagor
rs=[(r+s)/2]^2 – [(r-s)/2]^2=n^2
-> (2*n)^2+(r-s)^2=(r+s)^2 , and i do not know it help everything lighting up ?
help me about :
https://www.hackerrank.com/contests/projecteuler/challenges/euler108/problem?h_r=profile