Biorąc pod uwagę pewną dodatnią liczbę całkowitą która nie jest kwadratem, znajdź podstawowe rozwiązanie powiązanego równania Pell
Detale
- Podstawowa to para liczb całkowitych spełniających równanie, gdzie jest minimalna i dodatnia. (Zawsze istnieje trywialne rozwiązanie które nie jest liczone.)
- Możesz założyć, że 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
n
. (przy okazji byłem również zaskoczony, ale miałem wyzwanie w piaskownicy przez około rok)Odpowiedzi:
Piet , 612 kodów
Pobiera n ze standardowego wejścia. Wyprowadza y, a następnie x , rozdzielone spacjami.
Rozmiar kodu 1:
Rozmiar kodu 4, dla łatwiejszego oglądania:
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:
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.źródło
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:
Rozmiar kodu 4, dla łatwiejszego oglądania:
Wyjaśnienie
Tutaj jest ślad NPiet dla wartości wejściowej 5.
Jest to najbardziej brutalna brutalna siła, powtarzająca się zarówno nax jak i y . Inne rozwiązania mogą iterować powyżej x a następnie obliczyć y=x2−1n−−−−√ , ale oni są mięczakami .
Począwszy odx=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, gdziey 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.
źródło
Brachylog , 16 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Pari / GP , 34 bajty
PARI / GP prawie ma wbudowany do tego:Q(D−−√) , gdzieD jestdyskryminatorempola. Innymi słowy,x2−n⋅y2=±1 . Więc muszę wziąć kwadrat, gdy jego normą jest−1 .
quadunit
daje podstawową jednostkę z kwadratowego polaquadunit(4*n)
rozwiązuje równanie PellaNie wiem, jakiego algorytmu używa, ale działa nawet, gdyn nie jest kwadratem.
Odpowiedzi są podane w formien−−√ .
x + y*w
, w którejw
oznaczaWypróbuj online!
źródło
Wolfram Language (Mathematica) , 46 bajtów
Wypróbuj online!
źródło
05AB1E ,
171614 bajtówOszczędność bajtu dzięki Kevinowi Cruijssenowi .
Wyjścia
[y, x]
Wypróbuj online!
Wyjaśnienie
źródło
Ų
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.Ų
raz pierwszy zauważyłem, że to nie działało zgodnie z oczekiwaniami.Java 8,
747372 bajty-1 bajt dzięki @Arnauld .
-1 bajt dzięki @ OlivierGrégoire .
Wypróbuj online.
Wyjaśnienie:
źródło
n
nadouble
aix
naint
, grając na fakcie, któryx*x-1
jest równy(-x-1)*(-x+1)
.(x+1)*(x+1)-1
jest równy-x*-(x+2)
, aby być całkowicie poprawnym.R,
66565453524745 bajtówpełny program
-1 -2dzięki @Giuseppe-7 dzięki @Giuseppe i @Robin Ryder -2 @JAD
źródło
.5
zamiast0.5
x
jest równoważne znalezieniu najmniejszej wartościy
. Pozwala to zaoszczędzić 2 bajty, ponieważ wyrażaniex
w kategoriachy
jest krótsze niż na odwrót, i 4 bajty przy użyciu sztuczki polegającej na użyciu,T
która jest inicjowana o 1.+T
na końcu, aby upewnić się, że kiedyy==1
powróci1
zamiast,TRUE
ale nie jestem do końca pewien.Galaretka , 40 bajtów
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
Wypróbuj online!
Na przykład rozwiązanie dla 1234567890 ma odpowiednio 1936 i 1932 cyfry dla licznika i mianownika.
źródło
JavaScript (ES7), 47 bajtów
Wypróbuj online!
Poniżej znajduje się alternatywna 49-bajtowa wersja, która śledzix ² - 1 bezpośrednio zamiast kwadratu x at each iteration:
Try it online!
Or we can go the non-recursive way for 50 bytes:
Try it online!
źródło
TI-BASIC,
444241 bytesInput isn .(x,y) .
Output is a list whose values correspond to
Uses the equationy=x2−1n−−−−√ for x≥2 to calculate the fundamental solution.(x,y) pair for that equation is a fundamental solution iff ymod1=0 .
The current
Examples:
Explanation:
Uwaga: TI-BASIC jest językiem tokenizowanym. Liczba znaków nie jest równa liczbie bajtów.
źródło
MATL , 17 bajtów
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 ≤ x ≤ k , 1 ≤ y ≤ k . 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
As a consequence of 1 and 2,
źródło
Python 2 , 49 bajtów
Wypróbuj online!
Znajduje się
x
jako najmniejsza liczba powyżej 1 gdziex % sqrt(n) <= 1/x
. Następnie stwierdza,y
zx
coy = floor(x / sqrt(n))
.źródło
Haskell , 46 bajtów
Proste wyszukiwanie brutalnej siły. Wykorzystuje to fakt, że jest to podstawowe rozwiązanie(x,y) satisfying x2−ny2=1 must have y≤x .
Try it online!
źródło
n
tox
iny<-[1..n]
so you can computef 13
.C# (Visual C# Interactive Compiler),
7069 bytesPort of my Java 8 answer, but outputs a tuple instead of a string to save bytes.
Try it online.
źródło
Jelly, 15 bytes
Try it online!
A full program that takes a single argument
n
and returns a tuple ofx, y
.źródło
Husk, 12 bytes
Try it online!
Explanation
źródło
MathGolf, 12 bytes
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
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.
źródło
APL(NARS), 906 bytes
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
Test:
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)
źródło
Groovy, 53 bytes
Try it online!
Port of Kevin Cruijssen's Java and C# answers
źródło
Pyth, 15 bytes
Try it online here. Output is
x
theny
separated by a newline.źródło
Wolfram Language (Mathematica), 41 bytes
√
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 ofy
is at most 65538.Try it online!
źródło
><>, 45 bytes
Try it online!
Brute force algorithm, searching from
x=2
upwards, withy=x-1
and decrementing on each loop, incrementingx
wheny
reaches 0. Output isx
followed byy
, separated by a newline.źródło
C# (Visual C# Interactive Compiler), 69 bytes
Try it online!
źródło
Python 3, 75 bytes
Try it online!
Explanation
Brute force. Usingx<ii as an upper search bound, which is well below the definite upper limit of the fundamental solution to Pell's equation x≤i!
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
Try it online!
źródło
Python 2, 64 bytes
Try it online!
Returns
(x, y)
.źródło