1 ! Copyright (C) 2023 Giftpflanze.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: kernel math math.functions math.order
4 project-euler.common ranges sequences ;
7 ! https://projecteuler.net/problem=66
12 ! Consider quadratic Diophantine equations of the form:
15 ! For example, when D = 13, the minimal solution in x is
16 ! 649² - 13 × 180² = 1.
18 ! It can be assumed that there are no solutions in positive
19 ! integers when D is square.
21 ! By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we
22 ! obtain the following:
29 ! Hence, by considering minimal solutions in x for D <= 7, the
30 ! largest x is obtained when D = 5.
32 ! Find the value of D <= 1000 in minimal solutions of x for
33 ! which the largest value of x is obtained.
39 ! https://www.isibang.ac.in/~sury/chakravala.pdf
44 ! x' ≡ -x (mod |m|), x' < sqrt(N) < x'+|m|
49 :: chakravala ( n x p q m -- n x' p' q' m' )
50 n sqrt ceiling >integer :> upper-bound
51 upper-bound m abs - :> lower-bound
52 x neg m abs rem :> reminder
53 lower-bound reminder - :> distance
54 reminder distance m abs / ceiling 0 max m abs * + :> x'
57 p x' * n q * + m abs /
61 :: minimal-x ( D -- x )
62 D sqrt floor >integer :> p0
65 [ dup 1 = ] [ chakravala ] do until 2drop 2nip ;
68 1000 [1..b] [ perfect-square? ] reject
69 [ minimal-x ] supremum-by ;