Dado un número entero positivo que no es un cuadrado, encuentre la solución fundamental de la ecuación de Pell asociada
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).
- Puede suponer que no es un cuadrado.
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
n
s. (Por cierto, también me sorprendió, pero tuve este desafío en el sandbox durante aproximadamente un año)Respuestas:
Piet , 612 codeles
Toma n de la entrada estándar. Salidas y luego x , separadas por espacios.
Codel talla 1:
Codel tamaño 4, para facilitar la visualización:
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:
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é.fuente
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:
Codel tamaño 4, para facilitar la visualización:
Explicación
Aquí está la traza NPiet para un valor de entrada de 5.
Esta es la fuerza bruta más brutal, iterando sobrex e y . Otras soluciones pueden iterar sobre x luego calculary=x2−1n−−−−√ , pero son débiles .
A partir dex=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, dondey 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.
fuente
Brachylog , 16 bytes
Pruébalo en línea!
Explicación
fuente
Pari / GP , 34 bytes
PARI / GP casi tiene una función incorporada para esto:Q(D−−√) , dondeD es eldiscriminantedel campo. En otras palabras,x2−n⋅y2=±1 . Entonces tengo que tomar el cuadrado cuando su norma es−1 .
quadunit
da la unidad fundamental del campo cuadráticoquadunit(4*n)
resuelve la ecuación de PellNo sé qué algoritmo usa, pero incluso funciona cuandon no está libre de cuadrados.
Las respuestas se dan en el formularion−−√ .
x + y*w
, dondew
denotaPruébalo en línea!
fuente
Wolfram Language (Mathematica) , 46 bytes
Pruébalo en línea!
fuente
05AB1E ,
171614 bytesSalvó un byte gracias a Kevin Cruijssen .
Salidas
[y, x]
Pruébalo en línea!
Explicación
fuente
Ų
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.Ų
primera vez notando que no funcionó como se esperaba.Java 8,
747372 bytes-1 byte gracias a @Arnauld .
-1 byte gracias a @ OlivierGrégoire .
Pruébalo en línea.
Explicación:
fuente
n
a adouble
, yx
aint
, jugando en el hecho de quex*x-1
es igual a(-x-1)*(-x+1)
.(x+1)*(x+1)-1
es igual a-x*-(x+2)
, para ser completamente correcto.R,
66565453524745 bytesun programa completo
-1 -2gracias a @Giuseppe-7 gracias a @Giuseppe y @Robin Ryder -2 @JAD
fuente
.5
lugar de0.5
x
es equivalente a encontrar el valor más pequeño dey
. Esto le permite guardar 2 bytes porque expresarx
en términos dey
es más corto que al revés, y 4 bytes usando el truco de usarT
que se inicializa en 1.+T
al final para asegurarse de que cuandoy==1
regrese en1
lugar de,TRUE
pero no estoy completamente seguro.Jalea , 40 bytes
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
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.
fuente
JavaScript (ES7), 47 bytes
Pruébalo en línea!
Pruébalo en línea!
O podemos seguir el camino no recursivo por 50 bytes :
Pruébalo en línea!
fuente
TI-BASIC,
444241 bytesLa entrada esn . (x,y)
La salida es una lista cuyos valores corresponden a
Elparactual
Ejemplos:
Explicación:
Nota: TI-BASIC es un lenguaje tokenizado. El recuento de caracteres hace es igual al recuento de bytes.
fuente
MATL , 17 bytes
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 ≤ x ≤ k , 1 ≤ y ≤ k . 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
Como consecuencia de 1 y 2,
fuente
Python 2 , 49 bytes
Pruébalo en línea!
Se encuentra
x
como el número más pequeño arriba de 1 dondex % sqrt(n) <= 1/x
. Luego, encuentray
desdex
comoy = floor(x / sqrt(n))
.fuente
Haskell , 46 bytes
Pruébalo en línea!
fuente
n
ax
eny<-[1..n]
lo que puede calcularf 13
.C # (compilador interactivo de Visual C #),
7069 bytesEl puerto de mi respuesta Java 8 , pero genera una tupla en lugar de una cadena para guardar bytes.
Pruébalo en línea.
fuente
Jalea , 15 bytes
Pruébalo en línea!
Un programa completo que toma un solo argumento
n
y devuelve una tupla dex, y
.fuente
Casco , 12 bytes
Pruébalo en línea!
Explicación
fuente
MathGolf , 12 bytes
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.0
está el separador entre los dos números.Explicación
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.
fuente
APL (NARS), 906 bytes
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
Prueba:
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)
fuente
Groovy , 53 bytes
Pruébalo en línea!
Las respuestas Java y C # del puerto de Kevin Cruijssen
fuente
Pyth, 15 bytes
Pruébelo en línea aquí . La salida es
x
a continuacióny
separado por un salto de línea.fuente
Wolfram Language (Mathematica) , 41 bytes
√
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 dey
es como máximo 65538.Pruébalo en línea!
fuente
> <> , 45 bytes
Pruébalo en línea!
Algoritmo de fuerza bruta, buscando desde
x=2
arriba, cony=x-1
y disminuyendo en cada bucle, incrementandox
cuandoy
alcanza 0. La salida esx
seguida pory
, separada por una nueva línea.fuente
C # (compilador interactivo de Visual C #) , 69 bytes
Pruébalo en línea!
fuente
Python 3 , 75 bytes
Pruébalo en línea!
Explicación
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
Pruébalo en línea!
fuente
Python 2 , 64 bytes
Pruébalo en línea!
Las devoluciones
(x, y)
.fuente