Project Euler- Problem 66

  • Python
  • Thread starter Arman777
  • Start date
  • #1
1,735
138

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
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
1,735
138
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.
 
  • #4
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,145
546
For what it's worth: problem 67 is an interesting one... problem 66: I marked "skip"
 
  • #5
1,735
138
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
 
  • #6
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,145
546
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.
 
  • #7
verty
Homework Helper
2,164
198
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.
 
  • #8
1,735
138
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
1,735
138
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
verty
Homework Helper
2,164
198
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:
  • #11
1,735
138
Well yes probably.. Have you looked the site that I shared ...I agree that this problem cannot be solved in brute force
 
  • #12
verty
Homework Helper
2,164
198
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
1,735
138
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
verty
Homework Helper
2,164
198
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
1,735
138
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.
 

Related Threads on Project Euler- Problem 66

  • Last Post
Replies
5
Views
444
  • Last Post
Replies
4
Views
751
Replies
7
Views
464
  • Last Post
4
Replies
97
Views
4K
  • Last Post
Replies
8
Views
4K
Replies
13
Views
1K
Replies
31
Views
3K
Replies
9
Views
12K
  • Last Post
Replies
13
Views
18K
Top