# Project Euler- Problem 66

• Python
Gold Member
Consider quadratic Diophantine equations of the form:

x2 – Dy2 = 1

For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

Any idea how to solve this ?

I made a code but its slow. I find some information about the general solution but I didnt understand it much.

http://mathworld.wolfram.com/PellEquation.html

Python:
import time
start = time.perf_counter()
Number = [i for i in range(2,1001)]
Sq1 = [i**2 for i in range(2,int(1001**0.5))]
for i in Sq1:
Number.remove(i)

D_high_values =[]
x_initial = 3
for D in Number:
for x in range(2,10**5):
y = ((x**2-1)/D)
k = str(y**0.5)
if k[-1] == "0" and k[-2] ==".":   #testing if the square root is integer
if x_initial < x:
x_initial = x
break
else:
D_high_values.append(D)   #collecting values that have larger x value then 10**5

print(D_high_values)
print(x_initial)   #highest minimal x up to 10**5
end = time.perf_counter()
print("Time to solve:",end-start)

I noticed that theres 427 -D- values which their minimal x values are larger then 10**5. So I dont think brute force can give the solution.

Homework Helper
You wrote it wrong, you said ##D = 13 \to x = 6492## but it's ##D = 13 \to x = 649##. I get that x = 3042 is the worst x. I'll look tomorrow at your code to see if I can see something wrong with it. I can't promise anything because I don't know Python at all.

Gold Member
You wrote it wrong, you said ##D = 13 \to x = 6492## but it's ##D = 13 \to x = 649##. I get that x = 3042 is the worst x. I'll look tomorrow at your code to see if I can see something wrong with it. I can't promise anything because I don't know Python at all.
Code:
D,x,y
2 3 2.0
3 2 1.0
5 9 4.0
6 5 2.0
7 8 3.0
8 3 1.0
10 19 6.0
11 10 3.0
12 7 2.0
13 649 180.0
14 15 4.0
15 4 1.0
17 33 8.0
18 17 4.0
19 170 39.0
20 9 2.0
21 55 12.0
22 197 42.0
23 24 5.0
24 5 1.0
26 51 10.0
27 26 5.0
28 127 24.0
29 9801 1820.0
30 11 2.0
31 1520 273.0

Are you sure you checked it right? I also checked before I posted it is working nice.

Okay sure. Love to hear some thoughts. But about how can I improve the code or whats the right mathematical approach I am more interested about them.

Gold Member
For what it's worth: problem 67 is an interesting one... problem 66: I marked "skip"

Arman777
Gold Member
For what it's worth: problem 67 is an interesting one... problem 66: I marked "skip"
It seemes that I ll skip too. With brute force its not possible I guess. Theres x solutions up to 10**9-10**10 maybe even more.

I thought dividing the numbers: like solving x in range for 10**5 to 10**7 for example and then if theres still any D left I ll increase the x range to 10**7, 10**9
But it doesnt help.

I guess problem 64-65-66 might be linked together.

I solved max path sum I, but i had to look up on the net to grasp the idea about how can I approach the problem. And then I wrote the code... It s a good question indeed. So i ll just use the same code. If it does not I might think somethink else

Gold Member
I solved max path sum I, but i had to look up on the net to grasp the idea about how can I approach the problem. And then I wrote the code... It s a good question indeed. So i ll just use the same code. If it does not I might think somethink else

It could be worth another thread, depending on what pitfalls you run into. I happen to like problems related to optimization and also path(/graph) exploration so I enjoyed 67.

Arman777
Homework Helper
Code:
D,x,y
2 3 2.0
3 2 1.0
5 9 4.0
6 5 2.0
7 8 3.0
8 3 1.0
10 19 6.0
11 10 3.0
12 7 2.0
13 649 180.0
14 15 4.0
15 4 1.0
17 33 8.0
18 17 4.0
19 170 39.0
20 9 2.0
21 55 12.0
22 197 42.0
23 24 5.0
24 5 1.0
26 51 10.0
27 26 5.0
28 127 24.0
29 9801 1820.0
30 11 2.0
31 1520 273.0

Are you sure you checked it right? I also checked before I posted it is working nice.

Okay sure. Love to hear some thoughts. But about how can I improve the code or whats the right mathematical approach I am more interested about them.

I'm getting the same numbers as you now. D = 61 is proving particularly difficult. I'll let you know if I find the answer.

Gold Member
I'm getting the same numbers as you now. D = 61 is proving particularly difficult. I'll let you know if I find the answer.
Yes its larger then 10**8. I also noticed that. It takes much time to check it and there might be other numbers like that.

Gold Member
It could be worth another thread, depending on what pitfalls you run into. I happen to like problems related to optimization and also path(/graph) exploration so I enjoyed 67.
I can share my code.

Homework Helper
I've found the answer to D = 61: x = 1766319049, y = 226153980. This took around 20 minutes to generate. If there are 430 of these, that could take 6 days to solve. What this needs is a multithreaded approach where each thread searches for another D value. I only have a dual core, but with a 16 thread machine it could go pretty quick.

I don't want to describe how I did this because this is supposed to be a challenge. But I don't use a binary search. This is all I will say.

Last edited:
Arman777
Gold Member
Well yes probably.. Have you looked the site that I shared ...I agree that this problem cannot be solved in brute force

Homework Helper
Well yes probably.. Have you looked the site that I shared ...I agree that this problem cannot be solved in brute force

Oh right, it explains how to find the answer. I wondered how 16000 people solved it.

Gold Member
Oh right, it explains how to find the answer. I wondered how 16000 people solved it.
Can you turn it to the code ? I didnt understand the explanation. I solved the PE problem 64-65 and if it is connected to them i might solve this.

Homework Helper
Can you turn it to the code ? I didn't understand the explanation. I solved the PE problem 64-65 and if it is connected to them i might solve this.

I've coded it now and the answer I get is very odd. I get that D = 661 is maximal with x=16421658242965910275055840472270471049. I've no way to corroborate it. Coding it was not so difficult, you code the algorithm on that page and it works.

Hint: calculate pn and qn.

Gold Member
I've coded it now and the answer I get is very odd. I get that D = 661 is maximal with x=16421658242965910275055840472270471049. I've no way to corroborate it. Coding it was not so difficult, you code the algorithm on that page and it works.

Hint: calculate pn and qn.
I didnt understand those things thats why I asked the question here.