Finden Sie bei einer positiven ganzen Zahl , die kein Quadrat ist, die fundamentale Lösung der zugehörigen Pell-Gleichung
Einzelheiten
- Die Grundzahl ist ein Paar ganzer Zahlen die die Gleichung erfüllen, in der minimal und positiv ist. (Es gibt immer die einfache Lösung die nicht gezählt wird.)
- Sie können annehmen, dass 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
code-golf
math
number-theory
abstract-algebra
polynomials
fehlerhaft
quelle
quelle
n
s wegzulassen . (Übrigens war ich auch überrascht, aber ich hatte diese Herausforderung für etwa ein Jahr im Sandkasten)Antworten:
Piet , 612 Codels
Nimmt n von der Standardeingabe. Gibt y und dann x mit Leerzeichen aus.
Codel Größe 1:
Codel Größe 4, zur leichteren Anzeige:
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:
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.quelle
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:
Codel Größe 4, zur leichteren Anzeige:
Erläuterung
Hier ist die NPiet-Kurve für einen Eingabewert von 5.
Dies ist die brutalste Brute-Force-Methode, die sowohl überx als auch über y iteriert . Andere Lösungen können über x iterieren und dann y = √ berechneny=x2−1n−−−−√ , aber sie sindWeicheier .
Ausgehend vonx=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, woy 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.
quelle
Brachylog , 16 Bytes
Probieren Sie es online!
Erläuterung
quelle
Pari / GP , 34 Bytes
PARI / GP hat dafür fast eine eingebaute:Q(D−−√) , wobeiD dieDiskriminantedes Feldes ist. Mit anderen Worten,x2- n ⋅ y2= ± 1 . Also muss ich das Quadrat nehmen, wenn seine Norm- 1 .
quadunit
Gibt die Grundeinheit des quadratischen Feldesquadunit(4*n)
löst die Pellsche GleichungIch weiß nicht, welchen Algorithmus er verwendet, aber er funktioniert auch, wennn nicht quadratfrei ist.
Die Antworten werden in der Form gegebenn--√ .
x + y*w
, wow
BezeichnetProbieren Sie es online!
quelle
Wolfram Language (Mathematica) , 46 Byte
Probieren Sie es online!
quelle
05AB1E ,
171614 BytesDank Kevin Cruijssen ein Byte gespart .
Ausgänge
[y, x]
Probieren Sie es online!
Erläuterung
quelle
Ų
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.Ų
ersten Mal gemerkt, dass es nicht wie erwartet funktioniert hat.Java 8,
747372 Bytes-1 Byte danke an @Arnauld .
-1 Byte danke an @ OlivierGrégoire .
Probieren Sie es online aus.
Erläuterung:
quelle
n
zu adouble
undx
zu a gewechselt wird undint
auf der Tatsache gespieltx*x-1
wird , dass gleich ist(-x-1)*(-x+1)
.(x+1)*(x+1)-1
das gleich-x*-(x+2)
ist, um ganz richtig zu sein.R,
66565453524745 Bytesein volles Programm
-1 -2danke an @Giuseppe-7 danke an @Giuseppe & @Robin Ryder -2 @JAD
quelle
.5
anstelle von0.5
x
entspricht dem Ermitteln des kleinsten Werts vony
. Auf diese Weise können Sie 2 Bytes sparen, da das Ausdrückenx
vony
kürzer als umgekehrt ist, und 4 Bytes, indem Sie den Trick verwenden,T
der bei 1 initialisiert wird.+T
am Ende , um sicherzustellen , dass , wenny==1
es zurückkehrt1
statt ,TRUE
aber ich bin nicht ganz sicher.Gelee , 40 Bytes
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
Probieren Sie es online!
Zum Beispiel hat die Lösung für 1234567890 1936 und 1932 Ziffern für den Zähler bzw. Nenner.
quelle
JavaScript (ES7), 47 Byte
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:
Probieren Sie es online!
Oder wir gehen den nicht-rekursiven Weg für 50 Bytes :
Probieren Sie es online!
quelle
TI-BASIC,
444241 BytesEingabe istn . ( x , y) .
Ausgabe ist eine Liste, deren Werte entsprechen
Verwendet die Gleichungy= x2- 1n----√ zum x ≥ 2 die fundamentale Lösung zu berechnen. ( x , y) Paar für diese Gleichung ist eine grundlegende Lösung iff ymod 1 = 0 .
Die jetzige
Beispiele:
Erläuterung:
Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.
quelle
MATL , 17 Bytes
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 ≤ x ≤ k , 1 ≤ y ≤ k 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
Als Folge von 1 und 2,
quelle
Python 2 , 49 Bytes
Probieren Sie es online!
Findet
x
als kleinste Zahl über 1 wox % sqrt(n) <= 1/x
. Dann findet many
abx
wiey = floor(x / sqrt(n))
.quelle
Haskell , 46 Bytes
Eine unkomplizierte Brute-Force-Suche. Dies nutzt die Tatsache, dass eine grundlegende Lösung( x , y) befriedigend x2- n y2= 1 haben müssen y≤ x .
Probieren Sie es online!
quelle
n
umx
iny<-[1..n]
so dass Sie berechnen könnenf 13
.C # (Visual C # Interactive Compiler),
70 bis69 BytePort meiner Java 8 Antwort , gibt aber ein Tupel anstelle eines Strings aus, um Bytes zu sparen.
Probieren Sie es online aus.
quelle
Gelee , 15 Bytes
Probieren Sie es online!
Ein vollständiges Programm, das ein einzelnes Argument verwendet
n
und ein Tupel von zurückgibtx, y
.quelle
Schale , 12 Bytes
Probieren Sie es online!
Erläuterung
quelle
MathGolf , 12 Bytes
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.0
ist das Trennzeichen zwischen den beiden Zahlen.Erläuterung
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.
quelle
APL (NARS), 906 Bytes
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
Prüfung:
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)
quelle
Groovy , 53 Bytes
Probieren Sie es online!
Portierung der Java- und C # -Antworten von Kevin Cruijssen
quelle
Pyth, 15 Bytes
Probieren Sie es hier online aus . Die Ausgabe wird
x
danny
durch einen Zeilenumbruch getrennt.quelle
Wolfram Language (Mathematica) , 41 Bytes
√
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 vony
höchstens 65538 beträgt.Probieren Sie es online!
quelle
> <> 45 Bytes
Probieren Sie es online!
Brute-Force-Algorithmus, der von
x=2
oben nach oben suchty=x-1
und in jeder Schleife dekrementiert undx
beiy
Erreichen von 0 inkrementiert. Auf die Ausgabex
folgty
eine durch eine neue Zeile getrennte Zeile.quelle
C # (Visual C # Interactive Compiler) , 69 Byte
Probieren Sie es online!
quelle
Python 3 , 75 Bytes
Probieren Sie es online!
Erläuterung
Rohe Gewalt. Verwendenx < iich als obere Suchgrenze, die deutlich unter der bestimmten Obergrenze der fundamentalen Lösung der Pellschen Gleichung liegt x ≤ i !
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
Probieren Sie es online!
quelle
Python 2 , 64 Bytes
Probieren Sie es online!
Rückgabe
(x, y)
.quelle