Solución fundamental de la ecuación de Pell

28

Dado un número entero positivo n que no es un cuadrado, encuentre la solución fundamental (x,y) de la ecuación de Pell asociada

x2ny2=1

Detalles

  • El fundamental es un par de enteros satisfacen la ecuación donde es mínima y positiva. (Siempre existe la solución trivial que no se cuenta).(x,y)x,yx(x,y)=(1,0)
  • Puede suponer que no es un cuadrado.n

Ejemplos

 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

Secuencias relevantes de OEIS: A002350 A002349 A033313 A033317

falla
fuente
Sorprendido de que todavía no haya ningún desafío con la ecuación de Pell, ya que es bastante conocido, pensé. Al menos, recuerdo haberlo usado a veces con los desafíos del Proyecto Euler.
Kevin Cruijssen
@Fatalize " Se puede suponer que no es un cuadradon ". Sin embargo, probablemente sería más claro si los casos de prueba omitieran esas palabras.
Kevin Cruijssen
2
@KevinCruijssen Lo consideré, pero pensé que sería más confuso omitir algunos de los ns. (Por cierto, también me sorprendió, pero tuve este desafío en el sandbox durante aproximadamente un año)
falla
Relacionado: projecteuler.net/problem=66
steenbergh

Respuestas:

16

Piet , 612 codeles

Toma n de la entrada estándar. Salidas y luego x , separadas por espacios.

Codel talla 1: Programa de ecuaciones de Pell con codel talla 1

Codel tamaño 4, para facilitar la visualización: Programa de ecuaciones de Pell con codel talla 1

Explicación

Echa un vistazo a esta traza NPiet , que muestra el programa que calcula la solución para un valor de entrada de 99.

No estoy seguro de si alguna vez había oído hablar de la ecuación de Pell antes de este desafío, así que obtuve todo lo siguiente de Wikipedia; específicamente, estas secciones de tres artículos:

Básicamente, lo que hacemos es esto:

  1. Obtenga n de la entrada estándar.
  2. Encuentra nincrementando un contador hasta que su cuadrado excedan, luego decremente una vez. (Este es el primer bucle que puedes ver en la traza, en la parte superior izquierda)
  3. Configure algunas variables para calcular x e y partir de la fracción continua de n .
  4. Comprueba si x e y ajustan a la ecuación de Pell todavía. Si lo hacen, muestre los valores (esta es la rama hacia abajo aproximadamente 2/3 del camino) y luego salga (corriendo hacia el bloque rojo en el extremo izquierdo).
  5. De lo contrario, actualice las variables de forma iterativa y regrese al paso 4. (Este es el bucle ancho a la derecha, de regreso a la parte inferior y reincorporándose no a la mitad).

Francamente, no tengo idea de si un enfoque de fuerza bruta sería más corto, ¡y no voy a intentarlo! Bien, entonces lo intenté.

Tim Pederick
fuente
9

Piet , 184 codeles

Esta es la alternativa de fuerza bruta que dije (en mi otra respuesta ) que no quería escribir. Me lleva más de 2 minutos calcular la solución para n = 13. Realmente no quiero probarlo en n = 29 ... pero verifica cada n hasta 20, así que estoy seguro de que es correcto.

Al igual que esa otra respuesta, esto toma n de las entradas y salidas estándar y luego x , separadas por espacios.

Codel talla 1: Programa de ecuaciones de Pell (variante de fuerza bruta) con tamaño de códel 1

Codel tamaño 4, para facilitar la visualización: Programa de ecuaciones de Pell (variante de fuerza bruta) con códel tamaño 4

Explicación

Aquí está la traza NPiet para un valor de entrada de 5.

Esta es la fuerza bruta más brutal, iterando sobre x e y . Otras soluciones pueden iterar sobre x luego calculary=x21n , pero son débiles .

A partir de x=2 e y=1 , esto verifica si x y y hemos resuelto la ecuación todavía. Si tiene (la bifurcación en la parte inferior cerca de la derecha), genera los valores y sale.

Si no, continúa a la izquierda, donde y se incrementa y se compara con x . (Luego hay un giro de dirección para seguir el camino en zig-zag).

Esta última comparación es donde el camino se divide alrededor de la mitad izquierda. Si son iguales, x se incrementa e y se vuelve a establecer en 1. Y volvemos a verificar si todavía es una solución.

Todavía tengo algunos espacios en blanco disponibles, así que tal vez veré si puedo incorporar ese cálculo de raíz cuadrada sin ampliar el programa.

Tim Pederick
fuente
2
Jaja, estoy de acuerdo con los débiles que usan raíces cuadradas: D
flawr
6

Brachylog , 16 bytes

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

Pruébalo en línea!

Explicación

;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)
Fatalizar
fuente
5

Pari / GP , 34 bytes

PARI / GP casi tiene una función incorporada para esto: quadunitda la unidad fundamental del campo cuadrático Q(D), dondeDes eldiscriminantedel campo. En otras palabras,quadunit(4*n)resuelve la ecuación de Pellx2ny2=±1. Entonces tengo que tomar el cuadrado cuando su norma es1.

No sé qué algoritmo usa, pero incluso funciona cuando n no está libre de cuadrados.

Las respuestas se dan en el formulario x + y*w, donde wdenota n .

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

Pruébalo en línea!

alephalpha
fuente
4

Wolfram Language (Mathematica) , 46 bytes

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

Pruébalo en línea!

J42161217
fuente
1
¿Es seguro que esto siempre encuentra la solución fundamental ?
Greg Martin
@GregMartin sí, lo es. Esto siempre encuentra la primera solución (mínima). En este caso, esto siempre devuelve {1,0}. Es por eso que tenemos que elegir x> 1 y obtener la segunda solución (fundamental)
J42161217
1
Me gustaría que eso sea cierto, pero nada en la documentación parece indicar que ...
Greg Martin
@ GregMartin He usado esta función muchas veces y ya sabía cómo funcionaba. Mi única preocupación era omitir la primera solución y eso me costó esos 5 bytes adicionales. Puede escribir fácilmente un programa y probarlo (solo para confirmar millones de resultados)
J42161217
4

05AB1E , 17 16 14 bytes

Salvó un byte gracias a Kevin Cruijssen .
Salidas[y, x]

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

Pruébalo en línea!

Explicación

∞                 # 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
fuente
Y me ganaste otra vez ... también tenía un byte de 17, pero no funcionó porque Ųestá molesto con decimales ...>. <De todos modos, puedes eliminar ambos ,y agregar un final (no, la coma no es el mismo; p) para guardar un byte.
Kevin Cruijssen
@KevinCruijssen: ¡Gracias! Sí, también fui por Ųprimera vez notando que no funcionó como se esperaba.
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 gracias a @Arnauld .
-1 byte gracias a @ OlivierGrégoire .

Pruébalo en línea.

Explicación:

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
fuente
1
72 bytes , cambiando na a double, y xa int, jugando en el hecho de que x*x-1es igual a (-x-1)*(-x+1).
Olivier Grégoire
Bueno, en realidad estoy jugando con el hecho de que (x+1)*(x+1)-1es igual a -x*-(x+2), para ser completamente correcto.
Olivier Grégoire
3

R, 66 56 54 53 52 47 45 bytes

un programa completo

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

-1 -2 gracias a @Giuseppe

-7 gracias a @Giuseppe y @Robin Ryder -2 @JAD

Zahiro Mor
fuente
1
usar en .5lugar de0.5
Giuseppe
55
46 bytes . Encontrar el valor más pequeño de xes equivalente a encontrar el valor más pequeño de y. Esto le permite guardar 2 bytes porque expresar xen términos de yes más corto que al revés, y 4 bytes usando el truco de usar Tque se inicializa en 1.
Robin Ryder
1
@RobinRyder es posible que necesite un +Tal final para asegurarse de que cuando y==1regrese en 1lugar de, TRUEpero no estoy completamente seguro.
Giuseppe
3
@Giuseppe Bien visto! Tienes razón. Eso hace 47 bytes
Robin Ryder
1
Parece fallar en n = 61 (el caso de prueba grande y tonto) debido a problemas de gran número. Creo que está bien permitir límites de idioma, solo señalando la excepción.
CriminallyVulgar
3

Jalea , 40 bytes

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

Pruébalo en línea!

Una respuesta alternativa de Jelly, menos golfosa pero más eficiente algorítmicamente cuando x e y son grandes. Esto encuentra los convergentes de la fracción continua regular que se aproxima a la raíz cuadrada de n, y luego comprueba qué resuelve la ecuación de Pell. Ahora encuentra correctamente el período de la fracción continua regular.

Gracias a @TimPederick, también he implementado una solución basada en enteros que debería manejar cualquier número:

Jalea , 68 bytes

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

Pruébalo en línea!

Por ejemplo, la solución para 1234567890 tiene 1936 y 1932 dígitos para el numerador y el denominador, respectivamente.

Nick Kennedy
fuente
¡Agradable! Tomé el mismo enfoque en mi respuesta. No leo Jelly, así que no estoy seguro de por qué tienes problemas con 61. ¿Estás almacenando cada convergente como un par de enteros (numerador y denominador)?
Tim Pederick
@TimPederick Sí. No estoy seguro de dónde surge el problema
Nick Kennedy
Traté de aprender cómo funciona esto para poder ayudar a depurarlo, ¡pero no pude entenderlo! Lo único que puedo sugerir toma la palabra de los flotadores, ya que (si esto lo hace usar el mismo algoritmo que el mío) todos los valores intermedios deben salir como enteros de todos modos.
Tim Pederick
@TimPederick Era imprecisión de coma flotante. Ahora he hecho que deje de buscar una mayor continuación de la fracción continua una vez que alcanza el período. Esto funciona hasta 150, pero por encima de eso, creo que nuevamente me encuentro con errores de precisión de coma flotante en, por ejemplo, 151
Nick Kennedy
@TimPederick también es la generación de la fracción continua que es problemática, no los convergentes que se hacen con aritmética de enteros.
Nick Kennedy
2

JavaScript (ES7), 47 bytes

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

Pruébalo en línea!

x²1x

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

Pruébalo en línea!

O podemos seguir el camino no recursivo por 50 bytes :

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

Pruébalo en línea!

Arnauld
fuente
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

La entrada es n .
La salida es una lista cuyos valores corresponden a(x,y)

y=x21n parax2para calcular la solución fundamental.
Elparactual(x,y)para esa ecuación es una solución fundamental siymod1=0

Ejemplos:

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

Explicación:

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"

Nota: TI-BASIC es un lenguaje tokenizado. El recuento de caracteres hace es igual al recuento de bytes.

Tau
fuente
2

MATL , 17 bytes

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

Pruébalo en línea!

Explicación

El código sigue aumentando un contador k = 1, 2, 3, ... Para cada k , se buscan soluciones x , y con 1 ≤ xk , 1 ≤ yk . El proceso cuando se encuentra alguna solución.

Se garantiza que este procedimiento encontrará solo una solución, que es precisamente la fundamental. Para ver por qué, tenga en cuenta que

  1. Cualquier solución x > 0, y > 0 para n > 1 satisface x > y .
  2. Si x , y es una solución y x ', y ' es una solución diferente, entonces necesariamente xx ' e yy '.

Como consecuencia de 1 y 2,

  • Cuando el procedimiento se detiene en una k dada , solo existe una solución para esa k , porque si hubiera dos soluciones, una de ellas se habría encontrado antes, y el proceso se habría detenido con una k más pequeña .
  • Esta solución es fundamental, porque, de nuevo, si hubiera una solución con una x menor , se habría encontrado antes.

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

Python 2 , 49 bytes

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

Pruébalo en línea!

Se encuentra xcomo el número más pequeño arriba de 1 donde x % sqrt(n) <= 1/x. Luego, encuentra ydesde xcomo y = floor(x / sqrt(n)).

xnor
fuente
2

Haskell , 46 bytes

(x,y)x2ny2=1yx

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

Pruébalo en línea!

falla
fuente
Parece que es necesario cambiar na xen y<-[1..n]lo que puede calcular f 13.
Christian Sievers
@ChristianSievers ¡Gracias por señalarlo, lo corregí!
falla
1

C # (compilador interactivo de Visual C #), 70 69 bytes

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

El puerto de mi respuesta Java 8 , pero genera una tupla en lugar de una cadena para guardar bytes.

Pruébalo en línea.

Kevin Cruijssen
fuente
1

Jalea , 15 bytes

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

Pruébalo en línea!

Un programa completo que toma un solo argumento ny devuelve una tupla de x, y.

Nick Kennedy
fuente
1

Casco , 12 bytes

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

Pruébalo en línea!

Explicación

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

MathGolf , 12 bytes

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

Pruébalo en línea!

Estoy lanzando un Ave María cuando se trata del formato de salida. Si no está permitido, tengo una solución que es 1 byte más. El formato de salida es x.0y, donde .0está el separador entre los dos números.

Explicación

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

Me inspiré en la respuesta 05AB1E de Emigna, pero pude encontrar algunas mejoras. Si el separador que elegí no está permitido, agregue un espacio antes del último byte para un recuento de bytes de 13.

maxb
fuente
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

Arriba hay 2 funciones, la función sqrti que encontraría la raíz cuadrada del piso y la función pell devolvería a Zilde por error, y se basa en leer la página http://mathworld.wolfram.com/PellEquation.html usaría el algoritmo para conocer el sqrt de un número trhu continuar fracción (incluso si uso un algoritmo para saber sqrt utilizando el método newton) y se detiene cuando encuentra p y q tal que

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

Prueba:

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

Hay un límite para los ciclos en el bucle en la función sqrti, y un límite para los ciclos para el bucle en la función Pell, ambos para el número de caso posible son demasiado grandes o algo no convergen ... (No sé si sqrti converger todas las entradas posibles y lo mismo la función Pell también)

RosLuP
fuente
0

Pyth, 15 bytes

fsIJ@ct*TTQ2 2J

Pruébelo en línea aquí . La salida es xa continuación yseparado por un salto de línea.

Sok
fuente
0

Wolfram Language (Mathematica) , 41 bytes

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

es el carácter Unicode de 3 bytes # 221A. Emite la solución en el orden (y, x) en lugar de (x, y). Como es habitual con el imperfecto //.y sus iteraciones limitadas, solo funciona en entradas donde el valor verdadero de yes como máximo 65538.

Pruébalo en línea!

Greg Martin
fuente
0

> <> , 45 bytes

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

Pruébalo en línea!

Algoritmo de fuerza bruta, buscando desde x=2arriba, con y=x-1y disminuyendo en cada bucle, incrementando xcuando yalcanza 0. La salida es xseguida por y, separada por una nueva línea.

Sok
fuente
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)

Pruébalo en línea!

Explicación

x<ii
xi!

Este código también se ejecutaría en Python 2. Sin embargo, la función range () en Python 2 crea una lista en lugar de un generador como en Python 3 y, por lo tanto, es inmensamente ineficiente.


Con tiempo y memoria inifinte, uno podría usar una comprensión de la lista en lugar del iterador y guardar 3 bytes de esta manera:

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]

Pruébalo en línea!

Jitse
fuente