丢番图方程

作者：Andrei Osipov

https://projecteuler.net/problem=66

考虑以下形式的二次丢番图方程：x² – D×y² = 1

例如，当 D=13 时，x 的最小解为 649² – 13×180² = 1。

可以假设当 D 是平方数时，在正整数中没有解。

通过找到 D = {2, 3, 5, 6, 7} 时 x 的最小解，我们得到以下结果

3² – 2×2²= 1

2² – 3×1²= 1

9² – 5×4²= 1

5² – 6×2²= 1

8² – 7×3²= 1

因此，通过考虑 D ≤ 7 时 x 的最小解，当 D=5 时，得到最大的 x。

求出 D ≤ 1000 时，x 的最小解中 x 取最大值时的 D 值。

解决方案中使用了以下算法：https://en.wikipedia.org/wiki/Chakravala_method

源代码：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];