# Diophantine equation

Author: Andrei Osipov

https://projecteuler.net/problem=66

Consider quadratic Diophantine equations of the form: x² – D×y² = 1

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

2² – 3×1²= 1

9² – 5×4²= 1

5² – 6×2²= 1

8² – 7×3²= 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.

The following algorithm was used for the solution: https://en.wikipedia.org/wiki/Chakravala_method

Source code: prob066-andreoss.pl

```use v6;

subset NonSquarable where *.sqrt !%% 1;

sub next-triplet([\a,\b,\k], \N) {

# finding minimal l
1 .. N.sqrt.floor
==> grep  -> \l { (a + b * l) %% k } \
==> sort  -> \l { abs(l ** 2 - N)  } \
==> my @r;

my \l = @r.shift;

(a * l + N * b) / abs(k)
, (a + b * l)     / abs(k)
, (l ** 2 - N )   / k
}

sub simple-solution(NonSquarable \N) {

my \$a = N.sqrt.floor;
my \$b = 1;
my \$k = \$a ** 2 - N;

\$a, \$b, \$k;
}

sub chakravala(NonSquarable \N) {
# Start with a solution for a² - N b² = k

my (\$a, \$b, \$k) = simple-solution N;

(\$a,\$b,\$k) = next-triplet [\$a,\$b,\$k], N
while \$k != 1;

\$a, \$b, \$k;
}

1 .. 1000
==> grep NonSquarable                \
==> map -> \D { [D, chakravala D] }  \
==> sort * ==> my @x;

say @x.pop;

```