Grundlegende Lösung der Pell-Gleichung

28

Finden Sie bei einer positiven ganzen Zahl n , die kein Quadrat ist, die fundamentale Lösung (x,y) der zugehörigen Pell-Gleichung

x2ny2=1

Einzelheiten

  • Die Grundzahl (x,y) ist ein Paar ganzer Zahlen x,y die die Gleichung erfüllen, in der x minimal und positiv ist. (Es gibt immer die einfache Lösung (x,y)=(1,0) die nicht gezählt wird.)
  • Sie können annehmen, dass n kein Quadrat ist.

Beispiele

 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

Relevante OEIS-Sequenzen: A002350 A002349 A033313 A033317

fehlerhaft
quelle
Überrascht, dass es mit der Pell-Gleichung noch keine Herausforderung gibt, da sie ziemlich bekannt ist, dachte ich. Zumindest erinnere ich mich daran, es manchmal bei Project Euler-Herausforderungen verwendet zu haben.
Kevin Cruijssen
@Fatalize " Sie können davon ausgehen, dass kein Quadrat ist.n " Wäre wahrscheinlich klarer, wenn die Testfälle diese imho jedoch weglassen würden.
Kevin Cruijssen
2
@ KevinCruijssen Ich dachte darüber nach, aber ich dachte, es wäre verwirrender, einige der ns wegzulassen . (Übrigens war ich auch überrascht, aber ich hatte diese Herausforderung für etwa ein Jahr im Sandkasten)
Fehler
Siehe auch

Antworten:

16

Piet , 612 Codels

Nimmt n von der Standardeingabe. Gibt y und dann x mit Leerzeichen aus.

Codel Größe 1: Pells Gleichungsprogramm mit Codelgröße 1

Codel Größe 4, zur leichteren Anzeige: Pells Gleichungsprogramm mit Codelgröße 1

Erläuterung

Schauen Sie sich diesen NPiet-Trace an , in dem das Programm die Lösung für einen Eingabewert von 99 berechnet.

Ich bin mir nicht sicher, ob ich vor dieser Herausforderung jemals von Pell's Gleichung gehört hatte, daher habe ich alle folgenden Informationen von Wikipedia erhalten. Insbesondere diese Abschnitte von drei Artikeln:

Grundsätzlich machen wir Folgendes:

  1. Holen Sie sich n von der Standardeingabe.
  2. Finden Sie ndurch Inkrementieren eines Zählers, bis sein Quadratnüberschreitet, und anschließendes einmaliges Dekrementieren. (Dies ist die erste Schleife, die Sie in der Kurve oben links sehen können.)
  3. Richten Sie einige Variablen für die Berechnung ein x undy aus dem fortgesetzten Bruchteil vonn .
  4. Überprüfen Sie, ob x und y Pells Gleichung übereinstimmen. Wenn dies der Fall ist, geben Sie die Werte aus (dies ist der Abwärtszweig, der ungefähr 2/3 des Weges kreuzt) und beenden Sie den Vorgang (indem Sie in den roten Block ganz links laufen).
  5. Wenn nicht, aktualisieren Sie die Variablen iterativ und kehren Sie zu Schritt 4 zurück.

Ich habe ehrlich gesagt keine Ahnung, ob ein Brute-Force-Ansatz kürzer wäre oder nicht, und ich werde es nicht versuchen! Okay, also habe ich es versucht.

Tim Pederick
quelle
9

Piet , 184 Codels

Dies ist die Brute-Force-Alternative, die ich (in meiner anderen Antwort ) gesagt habe und die ich nicht schreiben wollte. Die Berechnung der Lösung für n dauert mehr als 2 Minuten = 13 . Ich möchte sie wirklich nicht mit n = 29 testen, aber sie überprüft alle n bis zu 20, sodass ich zuversichtlich bin, dass sie korrekt ist.

Wie bei dieser anderen Antwort wird n von den Standardeingaben und -ausgaben übernommen y und dann x durch Leerzeichen getrennt.

Codel Größe 1: Pells Gleichungsprogramm (Brute-Force-Variante) mit Codelgröße 1

Codel Größe 4, zur leichteren Anzeige: Pells Gleichungsprogramm (Brute-Force-Variante) mit Codelgröße 4

Erläuterung

Hier ist die NPiet-Kurve für einen Eingabewert von 5.

Dies ist die brutalste Brute-Force-Methode, die sowohl über x als auch über y iteriert . Andere Lösungen können über x iterieren und dann y = berechneny=x21n , aber sie sindWeicheier .

Ausgehend von x=2 und y=1 wird geprüft, ob x und y die Gleichung noch gelöst haben. Wenn dies der Fall ist (die Gabel unten rechts), werden die Werte ausgegeben und der Vorgang wird beendet.

Wenn nicht, geht es links weiter, wo y inkrementiert und mit x verglichen wirdx . (Dann gibt es einige Richtungswechsel, um dem Zick-Zack-Pfad zu folgen.)

Bei diesem letzten Vergleich teilt sich der Pfad in der Mitte der linken Seite. Wenn sie gleich sind,x inkrementiert undy auf 1 zurückgesetzt. Wir werden dann erneut prüfen, ob es sich um eine Lösung handelt.

Ich habe noch etwas Leerraum zur Verfügung, also werde ich vielleicht sehen, ob ich diese Quadratwurzelberechnung einbauen kann, ohne das Programm zu vergrößern.

Tim Pederick
quelle
2
Haha, ich stimme den Weichlingen zu , die Quadratwurzeln verwenden: D
flawr
6

Brachylog , 16 Bytes

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

Probieren Sie es online!

Erläuterung

;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)
Tödlich
quelle
5

Pari / GP , 34 Bytes

PARI / GP hat dafür fast eine eingebaute: quadunitGibt die Grundeinheit des quadratischen Feldes Q(D), wobeiDdieDiskriminantedes Feldes ist. Mit anderen Worten,quadunit(4*n)löst die Pellsche Gleichungx2-ny2=±1. Also muss ich das Quadrat nehmen, wenn seine Norm-1.

Ich weiß nicht, welchen Algorithmus er verwendet, aber er funktioniert auch, wenn n nicht quadratfrei ist.

Die Antworten werden in der Form gegeben x + y*w, wo wBezeichnet n .

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

Probieren Sie es online!

Alephalpha
quelle
4

Wolfram Language (Mathematica) , 46 Byte

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

Probieren Sie es online!

J42161217
quelle
1
Ist sichergestellt, dass dies immer die grundsätzliche Lösung findet?
Greg Martin
@ GregMartin ja, es ist. Dies findet immer die erste (minimale) Lösung. In diesem Fall wird immer {1,0} zurückgegeben. Deshalb müssen wir x> 1 wählen und die zweite (grundlegende) Lösung erhalten
J42161217
1
Ich möchte, dass das stimmt, aber nichts in der Dokumentation scheint darauf hinzudeuten, dass ...
Greg Martin
@ GregMartin Ich habe diese Funktion viele Male benutzt und wusste bereits, wie es funktioniert. Meine einzige Sorge war, die erste Lösung zu überspringen, und das kostete mich diese 5 zusätzlichen Bytes. Sie können ganz einfach ein Programm schreiben und testen (nur um Millionen von Ergebnissen zu bestätigen)
J42161217
4

05AB1E , 17 16 14 Bytes

Dank Kevin Cruijssen ein Byte gespart .
Ausgänge[y, x]

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

Probieren Sie es online!

Erläuterung

∞                 # 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
quelle
Und Sie schlugen mich , um es wieder .. hatte ein 17 byter als gut, aber es hat nicht funktioniert , weil Ųmit Dezimalzahlen abgehört wird ..>. <Wie dem auch sei, Sie beide entfernen ,und einen hinteren hinzufügen (nein, sind die Kommas nicht die p) um ein Byte zu speichern.
Kevin Cruijssen
@ KevinCruijssen: Danke! Ja, ich habe auch zum Ųersten Mal gemerkt, dass es nicht wie erwartet funktioniert hat.
Emigna
4

Java 8, 74 73 72 Bytes

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

-1 Byte danke an @Arnauld .
-1 Byte danke an @ OlivierGrégoire .

Probieren Sie es online aus.

Erläuterung:

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
quelle
1
72 Bytes , indem nzu a doubleund xzu a gewechselt wird und intauf der Tatsache gespielt x*x-1wird , dass gleich ist (-x-1)*(-x+1).
Olivier Grégoire
Naja, ich spiele eigentlich damit, dass (x+1)*(x+1)-1das gleich -x*-(x+2)ist, um ganz richtig zu sein.
Olivier Grégoire
3

R, 66 56 54 53 52 47 45 Bytes

ein volles Programm

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

-1 -2 danke an @Giuseppe

-7 danke an @Giuseppe & @Robin Ryder -2 @JAD

Zahiro Mor
quelle
1
Verwenden Sie .5anstelle von0.5
Giuseppe
5
46 Bytes . Das Ermitteln des kleinsten Werts von xentspricht dem Ermitteln des kleinsten Werts von y. Auf diese Weise können Sie 2 Bytes sparen, da das Ausdrücken xvon ykürzer als umgekehrt ist, und 4 Bytes, indem Sie den Trick verwenden, Tder bei 1 initialisiert wird.
Robin Ryder,
1
@RobinRyder Sie benötigen eine möglicherweise +Tam Ende , um sicherzustellen , dass , wenn y==1es zurückkehrt 1statt , TRUEaber ich bin nicht ganz sicher.
Giuseppe
3
@ Giuseppe Gut gesehen! Du hast recht. Das sind 47 Bytes
Robin Ryder
1
Scheint auf n = 61 (dem dummen großen Testfall) aufgrund zahlreicher Probleme zu scheitern. Ich denke, es ist in Ordnung, Sprachbeschränkungen zuzulassen, nur um die Ausnahme zu bemerken.
CriminallyVulgar
3

Gelee , 40 Bytes

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

Probieren Sie es online!

Eine alternative Gelee-Antwort, die weniger golfen, aber algorithmisch effizienter ist, wenn x und y groß sind. Dies findet die Konvergenten des regulären fortgesetzten Bruchs, die sich der Quadratwurzel von n annähern, und überprüft dann, welche die Pell-Gleichung lösen. Findet nun korrekt die Periode des regulären fortgesetzten Bruchs.

Dank @TimPederick habe ich auch eine ganzzahlige Lösung implementiert, die mit jeder Zahl umgehen kann:

Jelly , 68 Bytes

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

Probieren Sie es online!

Zum Beispiel hat die Lösung für 1234567890 1936 und 1932 Ziffern für den Zähler bzw. Nenner.

Nick Kennedy
quelle
Nett! Ich habe in meiner Antwort den gleichen Ansatz gewählt. Ich lese kein Gelee, deshalb bin ich mir nicht sicher, warum Sie Probleme mit 61 haben. Speichern Sie jede Konvergenz als ein Paar von ganzen Zahlen (Zähler und Nenner)?
Tim Pederick
@ TimPederick Ja. Nicht sicher, wo das Problem auftritt
Nick Kennedy
Ich habe versucht zu lernen, wie das funktioniert, damit ich beim Debuggen helfen kann, aber ich konnte einfach nicht meinen Kopf darum wickeln! Das einzige , was ich vorschlagen kann , den Boden von irgendwelchen Schwimmer nimmt, da (wenn dies tut den gleichen Algorithmus wie ich verwenden) alle Zwischenwerte als ganze Zahlen sowieso kommen sollte.
Tim Pederick
@ TimPederick Es war Gleitkomma-Ungenauigkeit. Ich habe jetzt dafür gesorgt, dass es aufhört, nach einer weiteren Fortsetzung der fortgesetzten Fraktion zu suchen, sobald sie die Periode erreicht. Dies funktioniert bis zu 150, aber darüber hinaus stoße ich wieder auf Gleitkomma-Genauigkeitsfehler, z. B. bei 151
Nick Kennedy,
@TimPederick Problematisch ist auch die Generierung des fortgesetzten Bruchs, nicht die Konvergenten, die mit ganzzahliger Arithmetik durchgeführt werden.
Nick Kennedy
2

JavaScript (ES7), 47 Byte

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

Probieren Sie es online!

Unten finden Sie eine alternative 49-Byte- Version, die den Überblick behältx²-1 direkt statt quadrieren x bei jeder Iteration:

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

Probieren Sie es online!

Oder wir gehen den nicht-rekursiven Weg für 50 Bytes :

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

Probieren Sie es online!

Arnauld
quelle
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

Eingabe ist n.
Ausgabe ist eine Liste, deren Werte entsprechen(x,y).

Verwendet die Gleichung y=x2-1n zum x2die fundamentale Lösung zu berechnen.
Die jetzige(x,y) Paar für diese Gleichung ist eine grundlegende Lösung iff ymod1=0.

Beispiele:

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

Erläuterung:

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"

Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.

Tau
quelle
2

MATL , 17 Bytes

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

Probieren Sie es online!

Erläuterung

Der Code erhöht ständig einen Zähler k = 1, 2, 3, ... Für jedes k werden Lösungen x , y mit 1 ≤ xk , 1 ≤ yk gesucht. Der Prozess, wenn eine Lösung gefunden wird.

Bei diesem Verfahren wird garantiert nur eine Lösung gefunden, und zwar genau die grundlegende. Um zu sehen warum, beachte das

  1. Jede Lösung x > 0, y > 0 für n > 1 erfüllt x > y .
  2. Wenn x , y eine Lösung ist und x ', y ' eine andere Lösung ist, müssen xx ' und yy ' sein.

Als Folge von 1 und 2,

  • Wenn die Prozedur bei einem bestimmten k stoppt , gibt es nur eine Lösung für dieses k , da bei zwei Lösungen eine davon früher gefunden worden wäre und der Prozess mit einem kleineren k gestoppt worden wäre .
  • Diese Lösung ist die grundlegende, denn auch hier hätte man früher eine Lösung mit kleinerem x gefunden.

`       % 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
quelle
2

Python 2 , 49 Bytes

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

Probieren Sie es online!

Findet xals kleinste Zahl über 1 wo x % sqrt(n) <= 1/x. Dann findet man yab xwie y = floor(x / sqrt(n)).

xnor
quelle
2

Haskell , 46 Bytes

Eine unkomplizierte Brute-Force-Suche. Dies nutzt die Tatsache, dass eine grundlegende Lösung(x,y) befriedigend x2-ny2=1 haben müssen yx.

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

Probieren Sie es online!

fehlerhaft
quelle
Es scheint , wie Sie ändern müssen , num xin y<-[1..n]so dass Sie berechnen können f 13.
Christian Sievers
@ChristianSievers Danke für den Hinweis, ich habe ihn korrigiert!
Fehler
1

C # (Visual C # Interactive Compiler), 70 bis 69 Byte

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

Port meiner Java 8 Antwort , gibt aber ein Tupel anstelle eines Strings aus, um Bytes zu sparen.

Probieren Sie es online aus.

Kevin Cruijssen
quelle
1

Gelee , 15 Bytes

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

Probieren Sie es online!

Ein vollständiges Programm, das ein einzelnes Argument verwendet nund ein Tupel von zurückgibt x, y.

Nick Kennedy
quelle
1

Schale , 12 Bytes

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

Probieren Sie es online!

Erläuterung

ḟΛ¤ȯ=→*⁰□π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
quelle
1

MathGolf , 12 Bytes

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

Probieren Sie es online!

Ich werfe einen Hagel Mary, wenn es um die Ausgabe-Formatierung geht. Wenn es nicht erlaubt ist, habe ich eine Lösung, die 1 Byte länger ist. Das Ausgabeformat ist x.0y, wo .0ist das Trennzeichen zwischen den beiden Zahlen.

Erläuterung

ö       ▼      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)

Ich habe mich von der 05AB1E-Antwort von Emigna inspirieren lassen, konnte aber einige Verbesserungen feststellen. Wenn das von mir gewählte Trennzeichen nicht zulässig ist, fügen Sie vor dem letzten Byte ein Leerzeichen für eine Byteanzahl von 13 ein.

maxb
quelle
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

Oberhalb es 2 Funktionen sqrti Funktion sind, die den Boden Quadratwurzel und Pell Funktion zurückkehren würde Zilde für Fehler finden würden, und basiert die Seite zu lesen http://mathworld.wolfram.com/PellEquation.html würde es die algo verwenden für die wissen sqrt einer Zahl trhu fahren Bruch fort (selbst wenn ich ein algo für know sqrt unter Verwendung der Newtonmethode benutze) und stoppen, wenn es p und q so findet, dass

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

Prüfung:

  ⎕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│
└~────────────────────────────────────────────────┘

Es gibt ein Limit für Zyklen in der Schleife in der Funktion sqrti und ein Limit für Zyklen für die Schleife in der Funktion Pell, beide für die mögliche Fallnummer sind zu groß oder laufen nicht zusammen ... (Ich weiß nicht, ob sqrti alle möglichen Eingaben konvergieren und ebenso die Pell-Funktion)

RosLuP
quelle
0

Pyth, 15 Bytes

fsIJ@ct*TTQ2 2J

Probieren Sie es hier online aus . Die Ausgabe wird xdann ydurch einen Zeilenumbruch getrennt.

Sok
quelle
0

Wolfram Language (Mathematica) , 41 Bytes

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

ist das 3-Byte-Unicode-Zeichen # 221A. Gibt die Lösung in der Reihenfolge (y, x) anstelle von (x, y) aus. Funktioniert wie gewohnt mit dem Imperfekt //.und seinen begrenzten Iterationen nur bei Eingaben, bei denen der wahre Wert von yhöchstens 65538 beträgt.

Probieren Sie es online!

Greg Martin
quelle
0

> <> 45 Bytes

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

Probieren Sie es online!

Brute-Force-Algorithmus, der von x=2oben nach oben sucht y=x-1und in jeder Schleife dekrementiert und xbei yErreichen von 0 inkrementiert. Auf die Ausgabe xfolgt yeine durch eine neue Zeile getrennte Zeile.

Sok
quelle
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)

Probieren Sie es online!

Erläuterung

Rohe Gewalt. Verwenden

x<ichich
als obere Suchgrenze, die deutlich unter der bestimmten Obergrenze der fundamentalen Lösung der Pellschen Gleichung liegt
xich!

Dieser Code würde auch in Python 2 ausgeführt. Die Funktion range () in Python 2 erstellt jedoch eine Liste anstelle eines Generators wie in Python 3 und ist daher immens ineffizient.


Mit weniger Zeit und Speicher könnte man ein Listenverständnis anstelle des Iterators verwenden und 3 Bytes wie folgt sparen:

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]

Probieren Sie es online!

Jitse
quelle