Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Python Project Euler- Problem 66

  1. Sep 15, 2018 #1
    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

    Code (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.
     
  2. jcsd
  3. Sep 15, 2018 #2

    verty

    User Avatar
    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.
     
  4. Sep 15, 2018 #3
    Code (Text):

    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.
     
  5. Sep 15, 2018 #4

    StoneTemplePython

    User Avatar
    Science Advisor
    Gold Member

    For what it's worth: problem 67 is an interesting one... problem 66: I marked "skip"
     
  6. Sep 15, 2018 #5
    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
     
  7. Sep 15, 2018 #6

    StoneTemplePython

    User Avatar
    Science Advisor
    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.
     
  8. Sep 16, 2018 at 2:22 AM #7

    verty

    User Avatar
    Homework Helper

    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.
     
  9. Sep 16, 2018 at 2:26 AM #8
    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.
     
  10. Sep 16, 2018 at 2:28 AM #9
    I can share my code.
     
  11. Sep 16, 2018 at 4:52 AM #10

    verty

    User Avatar
    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: Sep 16, 2018 at 5:03 AM
  12. Sep 16, 2018 at 4:56 AM #11
    Well yes probably.. Have you looked the site that I shared ...I agree that this problem cannot be solved in brute force
     
  13. Sep 16, 2018 at 5:04 AM #12

    verty

    User Avatar
    Homework Helper

    Oh right, it explains how to find the answer. I wondered how 16000 people solved it.
     
  14. Sep 16, 2018 at 5:11 AM #13
    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.
     
  15. Sep 16, 2018 at 6:46 AM #14

    verty

    User Avatar
    Homework Helper

    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.
     
  16. Sep 16, 2018 at 7:35 AM #15
    I didnt understand those things thats why I asked the question here.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted