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

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.
  • #1
Arman777
Insights Author
Gold Member
2,168
192
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.
 
Technology news on Phys.org
  • #2
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.
 
  • #3
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.
 
  • #4
For what it's worth: problem 67 is an interesting one... problem 66: I marked "skip"
 
  • Like
Likes Arman777
  • #5
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
 
  • #6
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.
 
  • Like
Likes Arman777
  • #7
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.
 
  • #8
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.
 
  • #9
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.
 
  • #10
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:
  • Like
Likes Arman777
  • #11
Well yes probably.. Have you looked the site that I shared ...I agree that this problem cannot be solved in brute force
 
  • #12
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.
 
  • #13
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.
 
  • #14
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.
 
  • #15
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.

Similar threads

  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
3
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
Replies
4
Views
1K
  • Programming and Computer Science
Replies
4
Views
604
Replies
1
Views
928
  • Calculus and Beyond Homework Help
Replies
2
Views
382
Back
Top