Podstawowe rozwiązanie równania Pell

28

Biorąc pod uwagę pewną dodatnią liczbę całkowitą n która nie jest kwadratem, znajdź podstawowe rozwiązanie (x,y) powiązanego równania Pell

x2ny2=1

Detale

  • Podstawowa (x,y) to para liczb całkowitych x,y spełniających równanie, gdzie x jest minimalna i dodatnia. (Zawsze istnieje trywialne rozwiązanie (x,y)=(1,0) które nie jest liczone.)
  • Możesz założyć, że n nie jest kwadratem.

Przykłady

 n           x    y
 1           -    -
 2           3    2
 3           2    1
 4           -    -
 5           9    4
 6           5    2
 7           8    3
 8           3    1
 9           -    -
10          19    6
11          10    3
12           7    2
13         649    180
14          15    4
15           4    1
16           -    -
17          33    8
18          17    4
19         170    39
20           9    2
21          55    12
22         197    42
23          24    5
24           5    1
25           -    -
26          51    10
27          26    5
28         127    24
29        9801    1820
30          11    2
31        1520    273
32          17    3
33          23    4
34          35    6
35           6    1
36           -    -
37          73    12
38          37    6
39          25    4
40          19    3
41        2049    320
42          13    2
43        3482    531
44         199    30
45         161    24
46       24335    3588
47          48    7
48           7    1
49           -    -
50          99    14
51          50    7
52         649    90
53       66249    9100
54         485    66
55          89    12
56          15    2
57         151    20
58       19603    2574
59         530    69
60          31    4
61  1766319049    226153980
62          63    8
63           8    1
64           -    -
65         129    16
66          65    8
67       48842    5967
68          33    4
69        7775    936
70         251    30
71        3480    413
72          17    2
73     2281249    267000
74        3699    430
75          26    3
76       57799    6630
77         351    40
78          53    6
79          80    9
80           9    1
81           -    -
82         163    18
83          82    9
84          55    6
85      285769    30996
86       10405    1122
87          28    3
88         197    21
89      500001    53000
90          19    2
91        1574    165
92        1151    120
93       12151    1260
94     2143295    221064
95          39    4
96          49    5
97    62809633    6377352
98          99    10
99          10    1

Odpowiednie sekwencje OEIS: A002350 A002349 A033313 A033317

wada
źródło
Zaskoczony, że równanie Pell nie stanowi jeszcze żadnego wyzwania, ponieważ pomyślałem, że jest dość dobrze znany. Przynajmniej pamiętam używanie go czasami z wyzwaniami Project Euler.
Kevin Cruijssen
@ Fatalizuj „ Możesz założyć, że nie jest kwadratem.n ” Prawdopodobnie byłoby jednak jaśniejsze, gdyby przypadki testowe pominęły te imho.
Kevin Cruijssen
2
@KevinCruijssen Rozważyłem to, ale pomyślałem, że bardziej mylące byłoby pominięcie niektórych z nich n. (przy okazji byłem również zaskoczony, ale miałem wyzwanie w piaskownicy przez około rok)
flawr
Powiązane: projecteuler.net/problem=66
steenbergh

Odpowiedzi:

16

Piet , 612 kodów

Pobiera n ze standardowego wejścia. Wyprowadza y, a następnie x , rozdzielone spacjami.

Rozmiar kodu 1: Pell's equation program with codel size 1

Rozmiar kodu 4, dla łatwiejszego oglądania: Pell's equation program with codel size 1

Wyjaśnienie

Sprawdź ten ślad NPiet , który pokazuje program obliczający rozwiązanie dla wartości wejściowej 99.

Nie jestem pewien, czy kiedykolwiek słyszałem o równaniu Pella przed tym wyzwaniem, więc otrzymałem wszystkie następujące informacje z Wikipedii; w szczególności te sekcje trzech artykułów:

Zasadniczo to, co robimy, to:

  1. Uzyskaj n ze standardowego wejścia.
  2. Znajdź nzwiększając licznik, aż jego kwadrat przekroczyn, a następnie zmniejsz go raz. (Jest to pierwsza pętla, którą można zobaczyć w śladzie w lewym górnym rogu).
  3. Ustawić pewne zmienne obliczania x i y od ułamka z n .
  4. Sprawdź, czy x i y zmieścić jeszcze Równanie Pella. Jeśli tak, wypisz wartości (jest to gałąź skierowana w dół około 2/3 drogi w poprzek), a następnie wyjdź (wpadając na czerwony blok po lewej stronie).
  5. Jeśli nie, iteracyjnie zaktualizuj zmienne i wróć do kroku 4. (Jest to szeroka pętla z prawej strony, z powrotem na dole i łącząca się niezupełnie w połowie).

Szczerze mówiąc, nie mam pojęcia, czy podejście z użyciem siły brutalnej byłoby krótsze i nie zamierzam tego próbować! Okej, więc spróbowałem.

Tim Pederick
źródło
9

Piet , 184 kody

To jest brutalna alternatywa, którą powiedziałem (w innej odpowiedzi ), że nie chcę pisać. Obliczenie rozwiązania dla n = 13. zajmuje ponad 2 minuty. Naprawdę nie chcę go wypróbowywać n = 29 ... ale sprawdza się dla każdego n do 20, więc jestem pewien, że jest poprawny.

Podobnie jak w przypadku innej odpowiedzi, bierze to n ze standardowych wejść i wyjść y a następnie x , rozdzielone spacjami.

Rozmiar kodu 1: Pell's equation program (brute-force variant) with codel size 1

Rozmiar kodu 4, dla łatwiejszego oglądania: Pell's equation program (brute-force variant) with codel size 4

Wyjaśnienie

Tutaj jest ślad NPiet dla wartości wejściowej 5.

Jest to najbardziej brutalna brutalna siła, powtarzająca się zarówno na x jak i y . Inne rozwiązania mogą iterować powyżej x a następnie obliczyć y=x21n , ale oni są mięczakami .

Począwszy od x=2 i y=1 , sprawdza, czy x i y rozwiązały równanie. Jeśli tak (widelec u dołu po prawej stronie), wyświetla wartości i wychodzi.

Jeśli nie, kontynuuje się w lewo, gdzie y jest zwiększane i porównywane z x . (Potem kręci się trochę w kierunku zygzakowatej ścieżki).

To ostatnie porównanie jest miejscem, w którym ścieżka rozdziela się wokół środkowego lewego rogu. Jeśli są równe, x jest zwiększane, y jest ustawiane z powrotem na 1. I wracamy do sprawdzania, czy jest to jeszcze rozwiązanie.

Nadal mam trochę białych znaków, więc może zobaczę, czy mogę uwzględnić obliczenia pierwiastkowe bez powiększania programu.

Tim Pederick
źródło
2
Haha Zgadzam się z wimpsami, które używają pierwiastków kwadratowych: D
flawr
6

Brachylog , 16 bajtów

;1↔;Ċz×ᵐ-1∧Ċ√ᵐℕᵐ

Wypróbuj online!

Wyjaśnienie

;1↔                Take the list [1, Input]
   ;Ċz             Zip it with a couple of two unknown variables: [[1,I],[Input,J]]
      ×ᵐ           Map multiply: [I, Input×J]
        -1         I - Input×J must be equal to 1
          ∧        (and)
           Ċ√ᵐ     We are looking for the square roots of these two unknown variables
              ℕᵐ   And they must be natural numbers
                   (implicit attempt to find values that match those constraints)
Fatalizować
źródło
5

Pari / GP , 34 bajty

PARI / GP prawie ma wbudowany do tego: quadunitdaje podstawową jednostkę z kwadratowego pola Q(D), gdzieDjestdyskryminatorempola. Innymi słowy,quadunit(4*n)rozwiązuje równanie Pellax2ny2=±1. Więc muszę wziąć kwadrat, gdy jego normą jest1 .

Nie wiem, jakiego algorytmu używa, ale działa nawet, gdy n nie jest kwadratem.

Odpowiedzi są podane w formie x + y*w, w której woznacza n .

n->(a=quadunit(4*n))*a^(norm(a)<0)

Wypróbuj online!

alephalpha
źródło
4

Wolfram Language (Mathematica) , 46 bajtów

FindInstance[x^2-y^2#==1&&x>1,{x,y},Integers]&

Wypróbuj online!

J42161217
źródło
1
Czy jest pewne, że zawsze znajdzie to podstawowe rozwiązanie?
Greg Martin
@GregMartin tak, to prawda. To zawsze znajduje pierwsze (minimalne) rozwiązanie. W takim przypadku zawsze zwraca {1,0}. Dlatego musimy wybrać x> 1 i uzyskać drugie (podstawowe) rozwiązanie
J42161217
1
Chciałbym, żeby to była prawda, ale nic w dokumentacji nie wydaje się wskazywać, że ...
Greg Martin
@GregMartin Korzystałem z tej funkcji wiele razy i już wiedziałem, jak to działa. Moją jedyną troską było pominięcie pierwszego rozwiązania, co kosztowało mnie te 5 dodatkowych bajtów. Możesz łatwo napisać program i przetestować go (tylko w celu potwierdzenia milionów wyników)
J42161217
4

05AB1E , 17 16 14 bajtów

Oszczędność bajtu dzięki Kevinowi Cruijssenowi .
Wyjścia[y, x]

∞.Δn*>t©1%_}®‚

Wypróbuj online!

Wyjaśnienie

∞                 # from the infinite list of numbers [1 ...]
 .Δ        }      # find the first number that returns true under
   n              # square
    *             # multiply with input
     >            # increment
      t©          # sqrt (and save to register as potential x)
        1%        # modulus 1
          _       # logical negation
            ®‚    # pair result (y) with register (x)
Emigna
źródło
I znów mnie pobiłaś ... miał również 17 bajtów, ale to nie działało, ponieważ Ųjest obciążone cyframi po przecinku ..>. <W każdym razie możesz usunąć oba ,i dodać znak końca (nie, przecinki nie są to samo; p) aby zapisać bajt.
Kevin Cruijssen
@KevinCruijssen: Dzięki! Tak, po Ųraz pierwszy zauważyłem, że to nie działało zgodnie z oczekiwaniami.
Emigna
4

Java 8, 74 73 72 bajty

n->{int x=1;var y=.1;for(;y%1>0;)y=Math.sqrt(-x*~++x/n);return x+" "+y;}

-1 bajt dzięki @Arnauld .
-1 bajt dzięki @ OlivierGrégoire .

Wypróbuj online.

Wyjaśnienie:

n->{                 // Method with double parameter and string return-type
  int x=1;           //  Integer `x`, starting at 1
  var y=.1;          //  Double `y`, starting at 0.1
  for(;y%1>0;)       //  Loop as long as `y` contains decimal digits:
    y=               //   Set `y` to:
      Math.sqrt(     //    The square-root of:
        -x*          //     Negative `x`, multiplied by
           ~++x      //     `(-x-2)` (or `-(x+1)-1)` to be exact)
                     //     (because we increase `x` by 1 first with `++x`)
               /n);  //     Divided by the input
  return x+" "+y;}   //  After the loop, return `x` and `y` with space-delimiter as result
Kevin Cruijssen
źródło
1
72 bajty , zmieniając nna doubleai xna int, grając na fakcie, który x*x-1jest równy (-x-1)*(-x+1).
Olivier Grégoire
Cóż, właściwie gram na fakcie, że (x+1)*(x+1)-1jest równy -x*-(x+2), aby być całkowicie poprawnym.
Olivier Grégoire
3

R, 66 56 54 53 52 47 45 bajtów

pełny program

n=scan();while((x=(1+n*T^2)^.5)%%1)T=T+1;x;+T

-1 -2 dzięki @Giuseppe

-7 dzięki @Giuseppe i @Robin Ryder -2 @JAD

Zahiro Mor
źródło
1
użyj .5zamiast0.5
Giuseppe
5
46 bajtów . Znalezienie najmniejszej wartości xjest równoważne znalezieniu najmniejszej wartości y. Pozwala to zaoszczędzić 2 bajty, ponieważ wyrażanie xw kategoriach yjest krótsze niż na odwrót, i 4 bajty przy użyciu sztuczki polegającej na użyciu, Tktóra jest inicjowana o 1.
Robin Ryder
1
@RobinRyder możesz potrzebować +Tna końcu, aby upewnić się, że kiedy y==1powróci 1zamiast, TRUEale nie jestem do końca pewien.
Giuseppe
3
@Giuseppe Dobrze zauważony! Masz rację. Czyni to 47 bajtów
Robin Ryder
1
Wydaje się, że zawodzi n = 61 (głupiutki przypadek testowy) z powodu dużej liczby problemów. Myślę, że dopuszcza się ograniczenia językowe, zwracając uwagę na wyjątek.
CriminallyVulgar
3

Galaretka , 40 bajtów

½©%1İ$<®‘¤$п¹;Ḋ$LḂ$?Ḟṭ@ṫ-ṚZæ.ʋ¥ƒØ.,U¤-ị

Wypróbuj online!

Alternatywna odpowiedź Jelly, mniej golfowa, ale bardziej wydajna algorytmicznie, gdy xiy są duże. Znajduje to zbieżności regularnej ciągłej frakcji, która przybliża pierwiastek kwadratowy z n, a następnie sprawdza, które rozwiązują równanie Pell. Teraz poprawnie znajduje okres regularnego ciągłego ułamka.

Dzięki @TimPederick wdrożyłem również rozwiązanie oparte na liczbach całkowitych, które powinno obsługiwać dowolną liczbę:

Galaretka , 68 bajtów

U×_ƭ/;²®_$÷2ị$}ʋ¥µ;+®Æ½W¤:/$$
¹©Æ½Ø.;ÇƬṪ€F¹;Ḋ$LḂ$?ṭ@ṫ-ṚZæ.ʋ¥ƒØ.,U¤-ị

Wypróbuj online!

Na przykład rozwiązanie dla 1234567890 ma odpowiednio 1936 i 1932 cyfry dla licznika i mianownika.

Nick Kennedy
źródło
Miły! W odpowiedzi podjąłem to samo podejście. Nie czytam Galaretki, więc nie jestem pewien, dlaczego masz problemy z 61. Czy przechowujesz każdą zbieżną jako parę liczb całkowitych (licznik i mianownik)?
Tim Pederick
@TimPederick Tak. Nie jestem pewien, gdzie pojawia się problem
Nick Kennedy
Próbowałem dowiedzieć się, jak to działa, więc mogłem pomóc w debugowaniu, ale po prostu nie mogłem się obejść! Jedyne co mogę zasugerować jest zabierania głosu wszelkich pływaków, ponieważ (jeśli nie używać tego samego algorytmu, jak moje) wszystkie wartości pośrednie powinny wychodzić jako liczby całkowite i tak.
Tim Pederick
@TimPederick To była niedokładność zmiennoprzecinkowa. Teraz sprawiłem, że przestało szukać dalszej kontynuacji kontynuowanej frakcji, kiedy osiągnie ten okres. Działa to do 150, ale powyżej wydaje mi się, że znów napotykam błędy dokładności zmiennoprzecinkowej np. 151
Nick Kennedy
@ TimPederick problematyczne jest również generowanie ciągłego ułamka, a nie zbieżności wykonywane za pomocą arytmetyki liczb całkowitych.
Nick Kennedy
2

JavaScript (ES7), 47 bajtów

n=>(g=x=>(y=((x*x-1)/n)**.5)%1?g(x+1):[x,y])(2)

Wypróbuj online!

Poniżej znajduje się alternatywna 49-bajtowa wersja, która śledzix²-1 bezpośrednio zamiast kwadratu x at each iteration:

n=>[(g=x=>(y=(x/n)**.5)%1?1+g(x+=k+=2):2)(k=3),y]

Try it online!

Or we can go the non-recursive way for 50 bytes:

n=>eval('for(x=1;(y=((++x*x-1)/n)**.5)%1;);[x,y]')

Try it online!

Arnauld
źródło
2

TI-BASIC,  44  42 41 bytes

Ans→N:"√(N⁻¹(X²-1→Y₁:1→X:Repeat not(fPart(Ans:X+1→X:Y₁:End:{X,Ans

Input is n.
Output is a list whose values correspond to (x,y).

Uses the equation y=x21n for x2 to calculate the fundamental solution.
The current (x,y) pair for that equation is a fundamental solution iff ymod1=0.

Examples:

6
               6
prgmCDGF12
           {5 2}
10
              10
prgmCDGF12
          {19 6}
13
              13
prgmCDGF12
       {649 180}

Explanation:

Ans→N:"√(N⁻¹(X²+1→Y₁:1→X:Repeat not(fPart(Ans:X+1→X:Y₁:End:{X,Ans  ;full logic

Ans→N                                                              ;store the input in "N"
      "√(N⁻¹(X²+1→Y₁                                               ;store the aforementioned
                                                                   ; equation into the first
                                                                   ; function variable
                     1→X                                           ;store 1 in "X"
                         Repeat not(fPart(Ans          End         ;loop until "Ans" is
                                                                   ; an integer
                                              X+1→X                ;increment "X" by 1
                                                    Y₁             ;evaluate the function
                                                                   ; stored in this variable
                                                                   ; at "X" and leave the
                                                                   ; result in "Ans"
                                                           {X,Ans  ;create a list whose
                                                                   ; values contain "X" and
                                                                   ; "Ans" and leave it in
                                                                   ; "Ans"
                                                                   ;implicitly print "Ans"

Uwaga: TI-BASIC jest językiem tokenizowanym. Liczba znaków nie jest równa liczbie bajtów.

Tau
źródło
2

MATL , 17 bajtów

`@:Ut!G*-!1=&fts~

Wypróbuj online!

Wyjaśnienie

Kod stale zwiększa licznik k = 1, 2, 3, ... Dla każdego k przeszukuje się rozwiązania x , y z 1 ≤ xk , 1 ≤ yk . Proces, gdy jakieś rozwiązanie, jeśli zostanie znalezione.

Ta procedura gwarantuje znalezienie tylko jednego rozwiązania, które jest dokładnie fundamentalne. Aby zobaczyć dlaczego, zauważ to

  1. Any solution x>0, y>0 for n>1 satisfies x>y.
  2. If x,y is a solution and x',y' is a different solution then necessarily xx' and yy'.

As a consequence of 1 and 2,

  • When the procedure stops at a given k, only one solution exists for that k, because if there were two solutions one of them would been found earlier, and the process would have stopped with a smaller k.
  • To rozwiązanie jest fundamentalne, ponieważ ponownie, gdyby istniało rozwiązanie o mniejszym x , byłoby znalezione wcześniej.

`       % Do...while
  @:U   %   Push row vector [1^2, 2^2, ..., k^2] where k is the iteration index
  t!    %   Duplicate and transpose. Gives the column vector [1^2; 2^2; ...; k^2]
  G*    %   Multiply by input n, element-wise. Gives [n*1^2; n*2^2; ...; n*k^2]
  -     %   Subtract with broadcast. Gives a square matrix of size n
  !     %   Transpose, so that x corresponds to row index and y to column index
  1=&f  %   Push row and column indices of all entries that equal 1. There can
        %   only be (a) zero such entries, in which case the results are [], [],
        %   or (b) one such entry, in which case the results are the solution x, y
  ts~   %   Duplicate, sum, negate. This gives 1 in case (a) or 0 in case (b)
        % End (implicit). Proceed with next iteration if top of the stack is true;
        % that is, if no solution was found.
        % Display (implicit). The stack contains copies of [], and x, y on top.
        % The empty array [] is not displayed
Luis Mendo
źródło
2

Python 2 , 49 bajtów

a=input()**.5
x=2
while x%a*x>1:x+=1
print x,x//a

Wypróbuj online!

Znajduje się xjako najmniejsza liczba powyżej 1 gdzie x % sqrt(n) <= 1/x. Następnie stwierdza, yz xco y = floor(x / sqrt(n)).

xnor
źródło
2

Haskell , 46 bajtów

Proste wyszukiwanie brutalnej siły. Wykorzystuje to fakt, że jest to podstawowe rozwiązanie(x,y) satisfying x2ny2=1 must have yx.

f n=[(x,y)|x<-[1..],y<-[1..x],x^2-n*y^2==1]!!0

Try it online!

flawr
źródło
It seems like you need to change n to x in y<-[1..n] so you can compute f 13.
Christian Sievers
@ChristianSievers Thanks for pointing it out, I corrected it!
flawr
1

C# (Visual C# Interactive Compiler), 70 69 bytes

n=>{int x=1;var y=.1;for(;y%1>0;)y=Math.Sqrt(-x*~++x/n);return(x,y);}

Port of my Java 8 answer, but outputs a tuple instead of a string to save bytes.

Try it online.

Kevin Cruijssen
źródło
1

Jelly, 15 bytes

‘ɼ²×³‘½µ⁺%1$¿;®

Try it online!

A full program that takes a single argument n and returns a tuple of x, y.

Nick Kennedy
źródło
1

Husk, 12 bytes

ḟΛ¤ȯ=→*⁰□π2N

Try it online!

Explanation

ḟΛ¤ȯ=→*⁰□π2N  Input is n, accessed through ⁰.
           N  Natural numbers: [1,2,3,4,..
         π2   2-tuples, ordered by sum: [[1,1],[1,2],[2,1],[1,3],[2,2],..
ḟ             Find the first that satisfies this:
 Λ             All adjacent pairs x,y satisfy this:
  ¤     □       Square both: x²,y²
   ȯ  *⁰        Multiply second number by n: x²,ny²
     →          Increment second number: x²,ny²+1
    =           These are equal.
Zgarb
źródło
1

MathGolf, 12 bytes

ökî²*)_°▼Þ√î

Try it online!

I'm throwing a Hail Mary when it comes to the output formatting. If it's not allowed, I have a solution which is 1 byte longer. The output format is x.0y, where .0 is the separator between the two numbers.

Explanation

ö       ▼      do-while-true with popping
 k             read integer from input
  î²           index of current loop (1-based) squared
    *          multiply the two
     )         increment (gives the potential x candidate
      _        duplicate TOS
       °       is perfect square
         Þ     discard everything but TOS
          √    square root
           î   index of previous loop (1-based)

I took some inspiration from Emigna's 05AB1E answer, but was able to find some improvements. If the separator I chose is not allowed, add a space before the last byte for a byte count of 13.

maxb
źródło
1

APL(NARS), 906 bytes

r←sqrti w;i;c;m
m←⎕ct⋄⎕ct←0⋄r←1⋄→3×⍳w≤3⋄r←2⋄→3×⍳w≤8⋄r←w÷2⋄c←0
i←⌊(2×r)÷⍨w+r×r⋄→3×⍳1≠×r-i⋄r←i⋄c+←1⋄→2×⍳c<900⋄r←⍬
⎕ct←m

r←pell w;a0;a;p;q2;p2;t;q;P;P1;Q;c;m
   r←⍬⋄→0×⍳w≤0⋄a0←a←sqrti w⋄→0×⍳a≡⍬⋄m←⎕ct⋄⎕ct←0⋄Q←p←1⋄c←P←P1←q2←p2←0⋄q←÷a
L: t←p2+a×p⋄p2←p⋄p←t
   t←q2+a×q
   :if c≠0⋄q2←q⋄:endif
   q←t           
   P←(a×Q)-P
   →Z×⍳Q=0⋄Q←Q÷⍨w-P×P
   →Z×⍳Q=0⋄a←⌊Q÷⍨a0+P
   c+←1⋄→L×⍳(1≠Qׯ1*c)∧c<10000
   r←p,q
   :if c=10000⋄r←⍬⋄:endif
Z: ⎕ct←m

Above there are 2 functions sqrti function that would find the floor square root and pell function would return Zilde for error, and is based reading the page http://mathworld.wolfram.com/PellEquation.html it would use the algo for know the sqrt of a number trhu continue fraction (even if i use one algo for know sqrt using newton method) and stop when it find p and q such that

 p^2-w*q^2=1=((-1)^c)*Qnext

Test:

  ⎕fmt pell 1x
┌0─┐
│ 0│
└~─┘
  ⎕fmt pell 2x
┌2───┐
│ 3 2│
└~───┘
  ⎕fmt pell 3x
┌2───┐
│ 2 1│
└~───┘
  ⎕fmt pell 5x
┌2───┐
│ 9 4│
└~───┘
  ⎕fmt pell 61x
┌2────────────────────┐
│ 1766319049 226153980│
└~────────────────────┘
  ⎕fmt pell 4x
┌0─┐
│ 0│
└~─┘
  ⎕fmt pell 7373x
┌2───────────────────────────────────────────────────────────┐
│ 146386147086753607603444659849 1704817376311393106805466060│
└~───────────────────────────────────────────────────────────┘
  ⎕fmt pell 1000000000000000000000000000002x
┌2────────────────────────────────────────────────┐
│ 1000000000000000000000000000001 1000000000000000│
└~────────────────────────────────────────────────┘

There is a limit for cycles in the loop in sqrti function, and a limit for cycles for the loop in Pell function, both for the possible case number are too much big or algo not converge... (I don't know if sqrti converge every possible input and the same the Pell function too)

RosLuP
źródło
0

Pyth, 15 bytes

fsIJ@ct*TTQ2 2J

Try it online here. Output is x then y separated by a newline.

Sok
źródło
0

Wolfram Language (Mathematica), 41 bytes

{1//.y_/;!NumberQ[x=√(y^2#+1)]:>y+1,x}&

is the 3-byte Unicode character #221A. Outputs the solution in the order (y,x) instead of (x,y). As usual with the imperfect //. and its limited iterations, only works on inputs where the true value of y is at most 65538.

Try it online!

Greg Martin
źródło
0

><>, 45 bytes

11v
+$\~:1
:}/!?:-1v?=1-*}:{*:@:{*:
$  naon;>

Try it online!

Brute force algorithm, searching from x=2 upwards, with y=x-1 and decrementing on each loop, incrementing x when y reaches 0. Output is x followed by y, separated by a newline.

Sok
źródło
0

Python 3, 75 bytes

lambda i:next((x,y)for x in range(2,i**i)for y in range(x)if~-x**2==i*y**2)

Try it online!

Explanation

Brute force. Using

x<ii
as an upper search bound, which is well below the definite upper limit of the fundamental solution to Pell's equation
xi!

This code would also run in Python 2. However, the range() function in Python 2 creates a list instead of a generator like in Python 3 and is thus immensely inefficient.


With inifinte time and memory, one could use a list comprehension instead of the iterator and save 3 bytes like so:

Python 3, 72 bytes

lambda i:[(x,y)for x in range(i**i)for y in range(x)if~-x**2==i*y**2][1]

Try it online!

Jitse
źródło