# 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 *[2] ==> my @x; say @x.pop[0];