# How Does One Solve the Minimal X for Pell's Equation with D Up to 1000?

• Python
• Arman777
In summary: I'm not sure if it's "the answer". I'll have to keep looking.I figured it out. I don't think the answer is unique. I'm not sure what the question is asking for.I figured it out. I don't think the answer is unique. I'm not sure what the question is asking for.Okay. I ll look at the question once again.
Arman777
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 there's 427 -D- values which their minimal x values are larger then 10**5. So I don't think brute force can give the solution.

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.

verty said:
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 what's the right mathematical approach I am more interested about them.

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

Arman777
StoneTemplePython said:
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 there's still any D left I ll increase the x range to 10**7, 10**9
But it doesn't 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

Arman777 said:
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
Arman777 said:
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 what's 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.

verty said:
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.

StoneTemplePython said:
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.

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
Well yes probably.. Have you looked the site that I shared ...I agree that this problem cannot be solved in brute force

Arman777 said:
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.

verty said:
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.

Arman777 said:
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.

verty said:
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 that's why I asked the question here.

## 1. What is "Project Euler - Problem 66"?

"Project Euler - Problem 66" is a mathematical problem from the Project Euler website, which is a collection of challenging mathematical and computational problems that require problem-solving skills and programming knowledge to solve.

## 2. What is the objective of "Project Euler - Problem 66"?

The objective of "Project Euler - Problem 66" is to find the minimal value of the largest solution to the Pell equation x² – Dy² = 1, where D is a given non-square integer.

## 3. How do you approach solving "Project Euler - Problem 66"?

The most common approach to solving "Project Euler - Problem 66" is by using the Chakravala method, an ancient Indian algorithm for solving Pell's equation, which involves finding a sequence of fractions that approximate the solution.

## 4. What is the significance of "Project Euler - Problem 66"?

"Project Euler - Problem 66" has significance in the fields of number theory and cryptography, as finding the largest solutions to Pell's equation has applications in both areas.

## 5. Are there any resources available to aid in solving "Project Euler - Problem 66"?

Yes, there are various resources available, such as online forums and discussion boards, where mathematicians and programmers share their approaches and solutions to "Project Euler - Problem 66." Additionally, there are also mathematical software and programming languages that can be used to solve the problem.

• Programming and Computer Science
Replies
5
Views
1K
• Programming and Computer Science
Replies
97
Views
7K
• Programming and Computer Science
Replies
1
Views
2K
• Programming and Computer Science
Replies
4
Views
4K
• Programming and Computer Science
Replies
4
Views
911
• Programming and Computer Science
Replies
17
Views
2K
• Programming and Computer Science
Replies
4
Views
1K
• Programming and Computer Science
Replies
4
Views
604
• Calculus
Replies
1
Views
928
• Calculus and Beyond Homework Help
Replies
2
Views
382