Solusi Fundamental dari Persamaan Pell

28

Dengan beberapa bilangan bulat positif n yang bukan kuadrat, temukan solusi fundamental (x,y) dari persamaan Pell yang terkait

x2ny2=1

Detail

  • Yang mendasar (x,y) adalah sepasang bilangan bulat x,y memenuhi persamaan di mana x minimal, dan positif. (Selalu ada solusi sepele (x,y)=(1,0) yang tidak dihitung.)
  • Anda dapat mengasumsikan bahwa n 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

Urutan OEIS yang relevan: A002350 A002349 A033313 A033317

cacat
sumber
Terkejut bahwa belum ada tantangan dengan persamaan Pell, karena itu cukup terkenal menurut saya. Setidaknya, saya ingat kadang menggunakannya dengan tantangan Project Euler.
Kevin Cruijssen
@Fatalize " Anda dapat mengasumsikan bahwa bukan kotak.n " Mungkin akan lebih jelas jika kasus uji dihilangkan imho tersebut.
Kevin Cruijssen
2
@KevinCruijssen saya menganggap itu, tapi saya pikir akan lebih membingungkan untuk menghilangkan beberapa ns. (btw saya juga terkejut tapi saya punya tantangan ini di kotak pasir selama sekitar satu tahun)
flawr
Terkait: projecteuler.net/problem=66
steenbergh

Jawaban:

16

Piet , 612 kode

Mengambil n dari input standar. Output y lalu x , dipisahkan oleh spasi.

Ukuran codel 1: Program persamaan Pell dengan ukuran codel 1

Ukuran codel 4, untuk lebih mudah dilihat: Program persamaan Pell dengan ukuran codel 1

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:

  1. Dapatkan n dari input standar.
  2. Temukan ndengan menambah penghitung hingga kuadratnya melebihin , lalu menguranginya satu kali. (Ini adalah loop pertama yang dapat Anda lihat di jejak, di kiri atas.)
  3. Siapkan beberapa variabel untuk menghitung x dan y dari fraksi lanjutan n .
  4. Periksa apakah x dan y cocok dengan persamaan Pell. Jika mereka melakukannya, output nilai-nilai (ini adalah cabang ke bawah sekitar 2/3 dari jalan melintasi) dan kemudian keluar (dengan berlari ke blok merah di paling kiri).
  5. Jika tidak, perbarui variabel secara iteratif dan kembali ke langkah 4. (Ini adalah loop lebar ke kanan, kembali melintasi bagian bawah, dan bergabung kembali tidak cukup setengah jalan.)

Terus terang saya tidak tahu apakah pendekatan brute-force akan lebih pendek, dan saya tidak akan mencobanya! Oke, jadi saya mencobanya.

Tim Pederick
sumber
9

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: Program persamaan Pell (varian brute-force) dengan ukuran codel 1

Ukuran codel 4, untuk lebih mudah dilihat: Program persamaan Pell (varian brute-force) dengan ukuran codel 4

Penjelasan

Inilah jejak NPiet untuk nilai input 5.

Ini adalah kekuatan brutal yang paling brutal, iterasi pada x dan y . Solusi lain mungkin beralih lebih dari x dan kemudian menghitung y=x21n , tapi merekalemah.

Mulai dari x=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 mana y 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.

Tim Pederick
sumber
2
Haha Saya setuju tentang para pengecut yang menggunakan akar kuadrat: D
flawr
6

Brachylog , 16 byte

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

Cobalah online!

Penjelasan

;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)
Fatalisasi
sumber
5

Pari / GP , 34 byte

PARI / GP hampir memiliki built-in untuk ini: quadunitmemberikan unit dasar dari kuadrat lapangan Q(D), di manaDadalahdiskriminandi lapangan. Dengan kata lain,quadunit(4*n)selesaikan persamaan Pellx2ny2=±1. Jadi saya harus mengambil kotak ketika normanya adalah1.

Saya tidak tahu algoritma apa yang digunakannya, tetapi bahkan berfungsi ketika n tidak bebas persegi.

Jawaban diberikan dalam bentuk x + y*w, di mana wmenunjukkan n .

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

Cobalah online!

alephalpha
sumber
4

Bahasa Wolfram (Mathematica) , 46 byte

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

Cobalah online!

J42161217
sumber
1
Apakah yakin bahwa ini selalu menemukan solusi mendasar ?
Greg Martin
@GregMartin yes, it is.This always finds the first (minimum) solution. In this case this always returns {1,0}. That is why we have to choose x>1 and get the second (fundamental) solution
J42161217
1
I would like that to be true, but nothing in the documentation seems to indicate that....
Greg Martin
@GregMartin I have used this function many times and already knew how it worked. My only concern was to skip the first solution and that cost me those 5 extra bytes. You can easily write a program and test it (just to confirm millions of results)
J42161217
4

05AB1E, 17 16 14 bytes

Saved a byte thanks to Kevin Cruijssen.
Outputs [y, x]

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

Try it online!

Explanation

∞                 # 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
sumber
And you beat me to it again.. had a 17 byter as well, but it didn't work because Ų 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.
Kevin Cruijssen
@KevinCruijssen: Thanks! Yeah I also went for Ų first noticing that it didn't work as expected.
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 thanks to @Arnauld.
-1 byte thanks to @OlivierGrégoire.

Try it online.

Explanation:

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
sumber
1
72 bytes, by changing n to a double, and x to an int, playing on the fact that x*x-1 is equal to (-x-1)*(-x+1).
Olivier Grégoire
Well, I'm actually playing on the fact that (x+1)*(x+1)-1 is equal to -x*-(x+2), to be entirely correct.
Olivier Grégoire
3

R, 66 56 54 53 52 47 45 bytes

a full program

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

-1 -2 thanks to @Giuseppe

-7 thanks to @Giuseppe & @Robin Ryder -2 @JAD

Zahiro Mor
sumber
1
use .5 instead of 0.5
Giuseppe
5
46 bytes. Finding the smallest value of x is equivalent to finding the smallest value of y. This allows you to save 2 bytes because expressing x in terms of y is shorter than the other way around, and 4 bytes by using the trick of using T which is initialized at 1.
Robin Ryder
1
@RobinRyder you might need a +T at the end to make sure that when y==1 it returns 1 instead of TRUE but I'm not entirely sure.
Giuseppe
3
@Giuseppe Well spotted! You are right. That makes it 47 bytes
Robin Ryder
1
Seems to fail on n=61 (the silly large test case) due to big number issues. I think it's fine to allow for language limits, just noting the exception.
CriminallyVulgar
3

Jelly, 40 bytes

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

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

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

Try it online!

For example, the solution for 1234567890 has 1936 and 1932 digits for the numerator and denominator respectively.

Nick Kennedy
sumber
Nice! I took the same approach in my answer. I don't read Jelly, so I'm not sure why you're having problems with 61. Are you storing each convergent as a pair of integers (numerator and denominator)?
Tim Pederick
@TimPederick Yes. Not sure where the issue arises
Nick Kennedy
I tried learning how this works so I could help debug it, but I just couldn't wrap my head around it! Only thing I can suggest is taking the floor of any floats, since (if this does use the same algorithm as mine) all intermediate values should come out as integers anyway.
Tim Pederick
@TimPederick It was floating point inaccuracy. I’ve now made it stop looking for further continuation of the continued fraction once it reaches the period. This works up to 150, but above that I think again I run into floating point accuracy errors at e.g. 151
Nick Kennedy
@TimPederick also it’s the generation of the continued fraction that’s problematic, not the convergents which are done with integer arithmetic.
Nick Kennedy
2

JavaScript (ES7), 47 bytes

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

Try it online!

Below is an alternate 49-byte version which keeps track of x²1 directly instead of squaring 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
sumber
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"

Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

Tau
sumber
2

MATL, 17 bytes

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

Try it online!

Explanation

The code keeps increasing a counter k = 1, 2, 3, ... For each k, solutions x, y with 1 ≤ xk, 1 ≤ yk 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

  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.
  • This solution is the fundamental one, because, again, if there were a solution with smaller x it would have been found earlier.

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

Python 2, 49 bytes

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

Try it online!

Finds x as the smallest number above 1 where x % sqrt(n) <= 1/x. Then, finds y from x as y = floor(x / sqrt(n)).

xnor
sumber
2

Haskell, 46 bytes

A straightforward brute force search. This makes use of the fact that a fundamental solution (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
sumber
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
sumber
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
sumber
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
sumber
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
sumber
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
sumber
0

Groovy, 53 bytes

n->x=1;for(y=0.1d;y%1>0;)y=((++x*x-1)/n)**0.5;x+" "+y

Try it online!

Port of Kevin Cruijssen's Java and C# answers

Expired Data
sumber
0

Pyth, 15 bytes

fsIJ@ct*TTQ2 2J

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

Sok
sumber
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
sumber
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
sumber
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
sumber
0

Python 2, 64 bytes

f=lambda n,x=2,y=1:x*x-n*y*y-1and f(n,x+(x==y),y*(y<x)+1)or(x,y)

Try it online!

Returns (x, y).

Erik the Outgolfer
sumber