Project Euler Problem 66

http://projecteuler.net/problem=66

Diophantine equation

Problem 66

Consider quadratic Diophantine equations of the form:

x² – Dy² = 1

For example, when D=13, the minimal solution in x is 649² – 13180² = 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:

3² – 22² = 1
2² – 31² = 1
9² – 54² = 1
5² – 62² = 1
8² – 73² = 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.

Answer:

661

Racket

#lang racket
; x^2 – Dy^2 = 1
(define result 0)
(define pmax 0)

(for ([D (in-range 2 1001)]) 
  (define limit (exact-floor (sqrt D)))
  (unless (= (sqr limit) D)   
    (let* ([m 0] [d 1] [a limit] [numm1 1] [num a] [denm1 0] [den 1])
      (let loop ()
        (unless (= 1 (- (sqr num) (* D den den)))
          (set! m (- (* d a) m))
          (set! d (exact-floor (/ (- D (sqr m)) d)))
          (set! a (exact-floor (/ (+ limit m) d)))
          (define numm2 numm1)
          (set! numm1 num)
          (define denm2 denm1)
          (set! denm1 den)
          (set! num (+ (* a numm1) numm2))
          (set! den (+ (* a denm1) denm2))
          (loop)))
      (displayln (list D num))
      (when (> num pmax)
        (set! pmax num)
        (set! result D)))))
(displayln result)