Solution fondamentale de l'équation de Pell

28

Étant donné un entier positif n qui n'est pas un carré, trouvez la solution fondamentale (x,y) de l' équation de Pell associée

x2ny2=1

Détails

  • Le fondamental (x,y) est une paire d'entiers x,y satisfaisant l'équation où x est minimal et positif. (Il y a toujours la solution triviale (x,y)=(1,0) qui n'est pas comptée.)
  • Vous pouvez supposer que n n'est pas un carré.

Exemples

 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

Séquences OEIS pertinentes: A002350 A002349 A033313 A033317

flawr
la source
Surpris qu'il n'y ait pas encore de défi avec l'équation de Pell, car c'est assez bien connu, pensais-je. Au moins, je me souviens de l'avoir utilisé parfois avec des défis de Project Euler.
Kevin Cruijssen
@Fatalize " Vous pouvez supposer que n'est pas un carré.n " Ce serait probablement plus clair si les cas de test omettaient ces imho, cependant.
Kevin Cruijssen
2
@KevinCruijssen J'ai considéré cela, mais j'ai pensé qu'il serait plus déroutant d'omettre certains des ns. (btw j'étais aussi surpris mais j'ai eu ce défi dans le bac à sable pendant environ un an)
flawr
EN RELATION

Réponses:

16

Piet , 612 codels

Prend n de l'entrée standard. Sorties y puis x , séparées par des espaces.

Codel taille 1: Programme d'équation de Pell avec taille de codel 1

Codel taille 4, pour une visualisation plus aisée: Programme d'équation de Pell avec taille de codel 1

Explication

Découvrez cette trace NPiet , qui montre le programme calculant la solution pour une valeur d'entrée de 99.

Je ne sais pas si j'avais déjà entendu parler de l'équation de Pell avant ce défi, alors j'ai obtenu tout ce qui suit de Wikipedia; plus précisément, ces sections de trois articles:

Fondamentalement, ce que nous faisons est le suivant:

  1. Obtenez n partir de l'entrée standard.
  2. Trouver nen incrémentant un compteur jusqu'à ce que son carré dépassen , puis en le décrémentant une fois. (Il s'agit de la première boucle que vous pouvez voir dans la trace, en haut à gauche.)
  3. Configurez quelques variables pour calculer x et y partir de la fraction continue de n .
  4. Vérifiez si x et y correspondent encore à l'équation de Pell. Si c'est le cas, sortez les valeurs (il s'agit de la branche descendante sur 2/3 du chemin), puis quittez (en courant dans le bloc rouge à l'extrême gauche).
  5. Sinon, mettez à jour les variables de manière itérative et revenez à l'étape 4. (Il s'agit de la boucle large vers la droite, en arrière en bas et en rejoignant pas tout à fait à mi-chemin.)

Je n'ai franchement aucune idée si une approche par force brute serait ou non plus courte, et je ne suis pas sur le point de l'essayer! D'accord, je l'ai donc essayé.

Tim Pederick
la source
9

Piet , 184 codels

C'est l'alternative de force brute que j'ai dit (dans mon autre réponse ) que je ne voulais pas écrire. Il faut plus de 2 minutes pour calculer la solution pour n = 13. Je ne veux vraiment pas l'essayer sur n = 29 ... mais il vérifie pour chaque n jusqu'à 20, donc je suis sûr que c'est correct.

Comme cette autre réponse, cela prend n de l'entrée standard et sort y puis x , séparés par des espaces.

Codel taille 1: Programme d'équation de Pell (variante de force brute) avec taille de codel 1

Codel taille 4, pour une visualisation plus aisée: Programme d'équation de Pell (variante de force brute) avec taille de codel 4

Explication

Voici la trace NPiet pour une valeur d'entrée de 5.

C'est la force brute la plus brutale, itérant sur x et y . D'autres solutions pourraient itérer sur x puis calculer y=x21n , mais ce sont desmauviettes.

En partant de x=2 et y=1 , cela vérifie si x et y ont encore résolu l'équation. Si c'est le cas (la fourche en bas près de la droite), il sort les valeurs et quitte.

Sinon, il continue à gauche, où y est incrémenté et comparé à x . (Ensuite, il y a un virage directionnel pour suivre le chemin en zigzag.)

Cette dernière comparaison est l'endroit où le chemin se divise vers le milieu à gauche. S'ils sont égaux, x est incrémenté et y est remis à 1. Et nous revenons à vérifier si c'est encore une solution.

J'ai encore des espaces disponibles, alors je vais peut-être voir si je peux incorporer ce calcul de racine carrée sans agrandir le programme.

Tim Pederick
la source
2
Haha je suis d'accord sur les mauviettes qui utilisent des racines carrées: D
flawr
6

Brachylog , 16 octets

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

Essayez-le en ligne!

Explication

;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)
Fatalize
la source
5

Pari / GP , 34 octets

PARI / GP a presque un intégré pour cela: quadunitdonne l' unité fondamentale du champ quadratique Q(), oùest lediscriminantdu champ. En d'autres termes,quadunit(4*n)résout l'équation de PellX2-ny2=±1. Je dois donc prendre le carré lorsque sa norme est-1.

n is not square-free.

x + y*wwn

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

Essayez-le en ligne!

alephalpha
la source
4

Wolfram Language (Mathematica) , 46 octets

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

Essayez-le en ligne!

J42161217
la source
1
Is it assured that this always finds the fundamental solution?
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
J'aimerais que cela soit vrai, mais rien dans la documentation ne semble indiquer que ...
Greg Martin
@GregMartin J'ai utilisé cette fonction plusieurs fois et je savais déjà comment elle fonctionnait. Ma seule préoccupation était de sauter la première solution et cela m'a coûté ces 5 octets supplémentaires. Vous pouvez facilement écrire un programme et le tester (juste pour confirmer des millions de résultats)
J42161217
4

05AB1E, 17 16 14 bytes

Un octet enregistré grâce à Kevin Cruijssen .
Les sorties[y, x]

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

Essayez-le en ligne!

Explication

∞                 # 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
la source
Et vous m'avez battu à nouveau .. avait un 17 octets également, mais cela n'a pas fonctionné car il Ųest buggé avec des décimales ..>. <Quoi qu'il en soit, vous pouvez supprimer les deux ,et ajouter une fin (non, les virgules ne sont pas les idem; p) pour enregistrer un octet.
Kevin Cruijssen
@KevinCruijssen: Merci! Oui, je suis également allé pour la Ųpremière fois en remarquant que cela ne fonctionnait pas comme prévu.
Emigna
4

Java 8, 74 73 72 octets

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
la source
1
72 octets , en changeantn 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
la source
1
utiliser .5au lieu de0.5
Giuseppe
5
46 octets . Trouver la plus petite valeur de xéquivaut à trouver la plus petite valeur de y. Cela vous permet d'économiser 2 octets car l'expression xen termes de yest plus courte que l'inverse, et 4 octets en utilisant l'astuce d'utilisation Tqui est initialisée à 1.
Robin Ryder
1
@RobinRyder vous pourriez avoir besoin d'un +Tà la fin pour vous assurer que lorsqu'il y==1reviendra 1au lieu de TRUEmais je ne suis pas tout à fait sûr.
Giuseppe
3
@Giuseppe Bien repéré! Vous avez raison. Cela fait 47 octets
Robin Ryder
1
Semble échouer sur n = 61 (le grand cas de test stupide) en raison de problèmes de grand nombre. Je pense que c'est bien de permettre des limites de langue, juste en notant l'exception.
CriminallyVulgar
3

Gelée , 40 octets

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

Essayez-le en ligne!

Une réponse alternative à Jelly, moins golfique mais plus efficace algorithmiquement lorsque x et y sont grands. Ceci trouve les convergents de la fraction continue régulière qui se rapprochent de la racine carrée de n, puis vérifie qui résout l'équation de Pell. Trouve maintenant correctement la période de la fraction continue régulière.

Grâce à @TimPederick, j'ai également implémenté une solution basée sur des nombres entiers qui devrait gérer n'importe quel nombre:

Gelée , 68 octets

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

Essayez-le en ligne!

Par exemple, la solution pour 1234567890 comporte respectivement 1936 et 1932 chiffres pour le numérateur et le dénominateur.

Nick Kennedy
la source
Agréable! J'ai adopté la même approche dans ma réponse. Je ne lis pas Jelly, donc je ne sais pas pourquoi vous rencontrez des problèmes avec 61. Stockez-vous chaque convergent comme une paire d'entiers (numérateur et dénominateur)?
Tim Pederick
@TimPederick Oui. Je ne sais pas où le problème se pose
Nick Kennedy
J'ai essayé d'apprendre comment cela fonctionne pour que je puisse l'aider à le déboguer, mais je ne pouvais tout simplement pas m'en occuper! La seule chose que je peux suggérer prend la parole de tous les flotteurs, puisque (si cela n'utiliser le même algorithme que le mien) toutes les valeurs intermédiaires devraient sortir des entiers de toute façon.
Tim Pederick
@TimPederick C'était une inexactitude en virgule flottante. Je l'ai maintenant fait cesser de chercher une poursuite de la fraction continue une fois qu'elle atteint la période. Cela fonctionne jusqu'à 150, mais au-dessus de cela, je pense encore une fois que je rencontre des erreurs de précision en virgule flottante, par exemple 151
Nick Kennedy
@TimPederick c'est aussi la génération de la fraction continue qui pose problème, pas les convergents qui se font avec l'arithmétique entière.
Nick Kennedy
2

JavaScript (ES7), 47 octets

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

Essayez-le en ligne!

Voici une autre version de 49 octets qui garde une trace deX²-1 directement au lieu de la quadrature X à chaque itération:

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

Essayez-le en ligne!

Ou nous pouvons suivre la voie non récursive pour 50 octets :

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

Essayez-le en ligne!

Arnauld
la source
2

TI-BASIC,  44  42 41 octets

Ans→N:"√(N⁻¹(X²-1→Y₁:1→X:Repeat not(fPart(Ans:X+1→X:Y₁:End:{X,Ans

L'entrée est n.
La sortie est une liste dont les valeurs correspondent à(X,y).

Utilise l'équation y=X2-1n pour X2pour calculer la solution fondamentale.
Le courant(X,y) paire pour cette équation est une solution fondamentale ssi ymod1=0.

Exemples:

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

Explication:

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"

Remarque: TI-BASIC est un langage à jetons. Le nombre de caractères n'est pas égal au nombre d'octets.

Tau
la source
2

MATL , 17 octets

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

Essayez-le en ligne!

Explication

Le code continue d'augmenter un compteur k = 1, 2, 3, ... Pour chaque k , les solutions x , y avec 1 ≤ xk , 1 ≤ yk sont recherchées. Le processus lorsqu'une solution est trouvée.

Cette procédure est garantie de ne trouver qu'une seule solution, qui est précisément la solution fondamentale. Pour voir pourquoi, notez que

  1. Toute solution x > 0, y > 0 pour n > 1 satisfait x > y .
  2. Si x , y est une solution et x ', y ' est une solution différente, alors nécessairement xx ' et yy '.

En conséquence de 1 et 2,

  • Lorsque la procédure s'arrête à un k donné , une seule solution existe pour ce k , car s'il y avait deux solutions, l'une d'entre elles aurait été trouvée plus tôt et le processus se serait arrêté avec un k plus petit .
  • Cette solution est fondamentale, car, encore une fois, s'il y avait une solution avec un x plus petit, elle aurait été trouvée plus tôt.

`       % 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
la source
2

Python 2 , 49 octets

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

Essayez-le en ligne!

Trouve xcomme le plus petit nombre au-dessus de 1 où x % sqrt(n) <= 1/x. Ensuite, trouve à ypartir de xas y = floor(x / sqrt(n)).

xnor
la source
2

Haskell , 46 octets

Une recherche simple de force brute. Cela utilise le fait qu'une solution fondamentale(X,y) satisfaisant X2-ny2=1 doit avoir yX.

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

Essayez-le en ligne!

flawr
la source
Il semble que vous avez besoin de changer npour xen y<-[1..n]afin que vous puissiez calculer f 13.
Christian Sievers
@ChristianSievers Merci de l'avoir signalé, je l'ai corrigé!
flawr
1

C # (Visual C # Interactive Compiler), 70 69 octets

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

Port de ma réponse Java 8 , mais génère un tuple au lieu d'une chaîne pour enregistrer les octets.

Essayez-le en ligne.

Kevin Cruijssen
la source
1

Gelée , 15 octets

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

Essayez-le en ligne!

Un programme complet qui prend un seul argument net renvoie un tuple de x, y.

Nick Kennedy
la source
1

Husk , 12 octets

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

Essayez-le en ligne!

Explication

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

MathGolf , 12 octets

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

Essayez-le en ligne!

Je lance un Je vous salue Marie en ce qui concerne le formatage de sortie. Si ce n'est pas autorisé, j'ai une solution qui fait 1 octet de plus. Le format de sortie est x.0y, où.0 est le séparateur entre les deux nombres.

Explication

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

Je me suis inspiré de la réponse 05AB1E d'Emigna, mais j'ai pu trouver des améliorations. Si le séparateur que j'ai choisi n'est pas autorisé, ajoutez un espace avant le dernier octet pour un nombre d'octets de 13.

maxb
la source
1

APL (NARS), 906 octets

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

Ci-dessus, il y a 2 fonctions sqrti qui trouveraient la racine carrée du plancher et la fonction pell retournerait Zilde pour erreur, et est basée sur la lecture de la page http://mathworld.wolfram.com/PellEquation.html, elle utiliserait l'algo pour connaître la sqrt d'un nombre trhu continue la fraction (même si j'utilise un algo pour connaître sqrt en utilisant la méthode newton) et s'arrête quand il trouve p et q tel que

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

Tester:

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

Il y a une limite pour les cycles dans la boucle dans la fonction sqrti, et une limite pour les cycles dans la boucle dans la fonction Pell, les deux pour le nombre possible de cas sont trop gros ou algo ne convergent pas ... (Je ne sais pas si sqrti faire converger toutes les entrées possibles et la même fonction Pell aussi)

RosLuP
la source
0

Pyth, 15 octets

fsIJ@ct*TTQ2 2J

Essayez-le en ligne ici . La sortie est xensuite yséparée par une nouvelle ligne.

Sok
la source
0

Wolfram Language (Mathematica) , 41 octets

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

est le caractère Unicode à 3 octets # 221A. Sort la solution dans l'ordre (y, x) au lieu de (x, y). Comme d'habitude avec l'imparfait //.et ses itérations limitées, ne fonctionne que sur les entrées où la vraie valeur dey est au plus 65538.

Essayez-le en ligne!

Greg Martin
la source
0

> <> , 45 octets

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

Essayez-le en ligne!

Algorithme de force brute, recherche x=2vers le haut, avec y=x-1et décrémentation sur chaque boucle, incrémentation xlorsqu'elle yatteint 0. La sortie est xsuivie de y, séparée par une nouvelle ligne.

Sok
la source
0

Python 3 , 75 octets

lambda i:next((x,y)for x in range(2,i**i)for y in range(x)if~-x**2==i*y**2)

Essayez-le en ligne!

Explication

Force brute. En utilisant

X<jeje
comme limite de recherche supérieure, qui est bien en dessous de la limite supérieure définie de la solution fondamentale de l'équation de Pell
Xje!

Ce code s'exécuterait également en Python 2. Cependant, la fonction range () en Python 2 crée une liste au lieu d'un générateur comme en Python 3 et est donc extrêmement inefficace.


Avec du temps et de la mémoire inifinte, on pourrait utiliser une compréhension de liste au lieu de l'itérateur et économiser 3 octets comme ceci:

Python 3 , 72 octets

lambda i:[(x,y)for x in range(i**i)for y in range(x)if~-x**2==i*y**2][1]

Essayez-le en ligne!

Jitse
la source