Dengan beberapa bilangan bulat positif yang bukan kuadrat, temukan solusi fundamental dari persamaan Pell yang terkait
Detail
- Yang mendasar adalah sepasang bilangan bulat memenuhi persamaan di mana minimal, dan positif. (Selalu ada solusi sepele yang tidak dihitung.)
- Anda dapat mengasumsikan bahwa bukan kotak.
Contohnya
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
s. (btw saya juga terkejut tapi saya punya tantangan ini di kotak pasir selama sekitar satu tahun)Jawaban:
Piet , 612 kode
Mengambil n dari input standar. Output y lalu x , dipisahkan oleh spasi.
Ukuran codel 1:
Ukuran codel 4, untuk lebih mudah dilihat:
Penjelasan
Lihat jejak NPiet ini , yang menunjukkan program menghitung solusi untuk nilai input 99.
Saya tidak yakin apakah saya pernah mendengar persamaan Pell sebelum tantangan ini, jadi saya mendapatkan semua yang berikut dari Wikipedia; khususnya, bagian dari tiga artikel ini:
Pada dasarnya, yang kami lakukan adalah ini:
Terus terang saya tidak tahu apakah pendekatan brute-force akan lebih pendek, dan saya tidak akan mencobanya!Oke, jadi saya mencobanya.sumber
Piet , 184 kode
Ini adalah alternatif kekerasan yang saya katakan (dalam jawaban saya yang lain ) yang tidak ingin saya tulis. Butuh lebih dari 2 menit untuk menghitung solusi untuk n = 13. Saya benar-benar tidak ingin mencobanya pada n = 29 ... tetapi memeriksa untuk setiap n hingga 20, jadi saya yakin itu benar.
Seperti jawaban lainnya, ini mengambil n dari input dan output standar y lalu x , dipisahkan oleh spasi.
Ukuran codel 1:
Ukuran codel 4, untuk lebih mudah dilihat:
Penjelasan
Inilah jejak NPiet untuk nilai input 5.
Ini adalah kekuatan brutal yang paling brutal, iterasi padax dan y . Solusi lain mungkin beralih lebih dari x dan kemudian menghitung y=x2−1n−−−−√ , tapi merekalemah.
Mulai darix=2 dan y=1 , ini memeriksa apakah x dan y belum menyelesaikan persamaan. Jika memiliki (garpu di bagian bawah dekat kanan), ia mengeluarkan nilai dan keluar.
Jika tidak, terus ke kiri, di manay bertambah dan dibandingkan dengan x . (Lalu ada beberapa arah yang memutar-mutar untuk mengikuti jalur zig-zag.)
Perbandingan terakhir ini adalah di mana jalan terbelah di sekitar kiri tengah. Jika mereka sama,x bertambah dan y diatur kembali ke 1. Dan kita kembali untuk memeriksa apakah itu solusi.
Saya masih memiliki beberapa spasi putih, jadi mungkin saya akan melihat apakah saya dapat memasukkan perhitungan root-root tanpa memperbesar program.
sumber
Brachylog , 16 byte
Cobalah online!
Penjelasan
sumber
Pari / GP , 34 byte
PARI / GP hampir memiliki built-in untuk ini:Q(D−−√) , di manaD adalahdiskriminandi lapangan. Dengan kata lain,x2−n⋅y2=±1 . Jadi saya harus mengambil kotak ketika normanya adalah−1 .
quadunit
memberikan unit dasar dari kuadrat lapanganquadunit(4*n)
selesaikan persamaan PellSaya tidak tahu algoritma apa yang digunakannya, tetapi bahkan berfungsi ketikan tidak bebas persegi.
Jawaban diberikan dalam bentukn−−√ .
x + y*w
, di manaw
menunjukkanCobalah online!
sumber
Bahasa Wolfram (Mathematica) , 46 byte
Cobalah online!
sumber
05AB1E,
171614 bytesSaved a byte thanks to Kevin Cruijssen.
Outputs
[y, x]
Try it online!
Explanation
sumber
Ų
is bugged with decimals.. >.< Anyway, you can remove both,
and add a trailing‚
(no, the comma's are not the same ;p) to save a byte.Ų
first noticing that it didn't work as expected.Java 8,
747372 bytes-1 byte thanks to @Arnauld.
-1 byte thanks to @OlivierGrégoire.
Try it online.
Explanation:
sumber
n
to adouble
, andx
to anint
, playing on the fact thatx*x-1
is equal to(-x-1)*(-x+1)
.(x+1)*(x+1)-1
is equal to-x*-(x+2)
, to be entirely correct.R,
66565453524745 bytesa full program
-1 -2thanks to @Giuseppe-7 thanks to @Giuseppe & @Robin Ryder -2 @JAD
sumber
.5
instead of0.5
x
is equivalent to finding the smallest value ofy
. This allows you to save 2 bytes because expressingx
in terms ofy
is shorter than the other way around, and 4 bytes by using the trick of usingT
which is initialized at 1.+T
at the end to make sure that wheny==1
it returns1
instead ofTRUE
but I'm not entirely sure.Jelly, 40 bytes
Try it online!
An alternative Jelly answer, less golfy but more efficient algorithmically when x and y are large. This finds the convergents of the regular continued fraction that approximate the square root of n, and then checks which solve the Pell equation. Now correctly finds the period of the regular continued fraction.
Thanks to @TimPederick, I’ve also implemented an integer-based solution which should handle any number:
Jelly, 68 bytes
Try it online!
For example, the solution for 1234567890 has 1936 and 1932 digits for the numerator and denominator respectively.
sumber
JavaScript (ES7), 47 bytes
Try it online!
Below is an alternate 49-byte version which keeps track ofx²−1 directly instead of squaring x at each iteration:
Try it online!
Or we can go the non-recursive way for 50 bytes:
Try it online!
sumber
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:
Note: TI-BASIC is a tokenized language. Character count does not equal byte count.
sumber
MATL, 17 bytes
Try it online!
Explanation
The code keeps increasing a counter k = 1, 2, 3, ... For each k, solutions x, y with 1 ≤ x ≤ k, 1 ≤ y ≤ k are searched. The process when some solution if found.
This procedure is guaranteed to find only one solution, which is precisely the fundamental one. To see why, note that
As a consequence of 1 and 2,
sumber
Python 2, 49 bytes
Try it online!
Finds
x
as the smallest number above 1 wherex % sqrt(n) <= 1/x
. Then, findsy
fromx
asy = floor(x / sqrt(n))
.sumber
Haskell, 46 bytes
A straightforward brute force search. This makes use of the fact that a fundamental solution(x,y) satisfying x2−ny2=1 must have y≤x .
Try it online!
sumber
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.
sumber
Jelly, 15 bytes
Try it online!
A full program that takes a single argument
n
and returns a tuple ofx, y
.sumber
Husk, 12 bytes
Try it online!
Explanation
sumber
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.
sumber
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)
sumber
Groovy, 53 bytes
Try it online!
Port of Kevin Cruijssen's Java and C# answers
sumber
Pyth, 15 bytes
Try it online here. Output is
x
theny
separated by a newline.sumber
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!
sumber
><>, 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.sumber
C# (Visual C# Interactive Compiler), 69 bytes
Try it online!
sumber
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!
sumber
Python 2, 64 bytes
Try it online!
Returns
(x, y)
.sumber