( relacionado )
Un Triple pitagórico es una lista (a, b, c)
que satisface la ecuación a 2 + b 2 = c 2 .
Un Triple pitagórico primitivo (PPT) es aquel donde a
, b
y c
son todos primos (es decir, el único divisor común entre los tres elementos es 1
). Por ejemplo, el (3, 4, 5)
triángulo rectángulo es un famoso Triple pitagórico primitivo.
El reto
- Dada la entrada
n
, salida deln
th PPT O, - Dada entrada
n
, salida los primerosn
PPT.
Hay varias formas de ordenar estos PPT para formar una lista bien ordenada, para determinar cuál es el n
th. Puede elegir el orden que desee, siempre que pueda probar (informalmente está bien) que su algoritmo puede generar todos los PPT únicos posibles. Por ejemplo, su código no debe generar ambos (3,4,5)
y, (4,3,5)
dado que son duplicados del mismo triple, uno u otro, por favor.
Del mismo modo, si su código está indexado a cero o uno está bien, siempre que indique cuál está utilizando.
Ejemplos
Para los ejemplos a continuación, estoy usando una indexación, generando el n
PPT y ordenando por el más pequeño c
, luego el más pequeño a
, luego el más pequeño b
.
n | output
1 | (3, 4, 5)
2 | (5, 12, 13)
5 | (20, 21, 29)
12| (48, 55, 73)
Reglas
- La entrada y la salida se pueden dar en cualquier formato conveniente .
- En su envío, indique cómo se ordenan sus entradas y si sus entradas están indexadas a 0 o indexadas a 1.
- Su pedido elegido no puede crear duplicados.
- Un programa completo o una función son aceptables. Si es una función, puede devolver el resultado en lugar de imprimirlo.
- Si es posible, incluya un enlace a un entorno de prueba en línea para que otras personas puedan probar su código.
- Las lagunas estándar están prohibidas.
- Este es el código de golf, por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).
fuente
Respuestas:
Jalea ,
2725 bytes2 bytes gracias a Jonathan Allan.
Pruébalo en línea!
Emite los primeros
n
triples indexados en 1[b, a, c]
, ordenados por aumentob
y luegoa
.Utiliza el algoritmo de Wikipedia :
Esto genera todos los triples primitivos para todos los pares coprimos únicos de enteros impares
m > n > 0
.Explicación
fuente
g/Ị$Ðf
->g/ÐṂ
para guardar dos bytes (ya que el mínimo mcd es 1 y siempre habrá al menos una de esas entradas).+2ḶḤ‘Œc
con un²Rm2Œc
mensaje que no funcionará para una entrada de1
:(²ḶḤ‘Œc
fue uno de los primeros en los que pensé).MATL , 36 bytes
La entrada está basada en 1. El orden de salida garantiza que cada triple aparezca exactamente una vez. El orden se explica a continuación. La explicación requiere profundizar un poco en cómo funciona el programa.
El código sigue aumentando un contador
k
en un ciclo, comenzando en1
. Para cadak
genera todos los pares cona = 1,...,k
,b = 1,...,k
,a < b
, y picos aquellas que dan una Pitágoras triple conc <= k
. Los pares se obtienen en orden de aumentob
, luegoa
.Cada par se divide por su mcd. Los pares resultantes (posiblemente duplicados) están dispuestos como una matriz de dos columnas. Esta matriz se concatena verticalmente con una matriz similar que contiene los resultados acumulados obtenidos para valores menores de
k
. Las filas de la matriz se deduplican de manera estable. Esto elimina dos tipos de duplicados:Pares que se han encontrado más de una vez para la corriente
k
(como3,4
, que también resulta de6,8
cuando se divide por su mcd);Pares que ya se encontraron con los más pequeños
k
.De hecho, cada iteración
k
encuentra todos los pares que ya se encontraron para las iteraciones anteriores. Pero puede encontrarlos en un orden diferente . Por ejemplo,k=25
encontrará el triple7,24,25
y no20,21,29
(porquec
no puede excederk
). Más adelante, la iteraciónk=29
encontrará ambos, pero con20,21,29
antes7,24,25
(el orden aumentab
, entoncesa
). Es por eso que, en lugar de mantener todos los pares encontrados para el últimok
, los agregamos a los anteriores y deduplicamos de manera estable. Hacerlo asegura que el orden sea el mismo para cualquier entradan
.Lo anterior garantiza que cada triple pitagórico primitivo finalmente aparecerá, y aparecerá solo una vez. Para la entrada
n
, el ciclok
finaliza cuandon
se han obtenido al menos triples válidos; y luego eln
enésimo triple es la salida.Pruébalo en línea!
O use este código modificado para ver los primeros
n
triples:Pruébalo en línea!
fuente
Haskell , 98 bytes
Pruébalo en línea!
Cómo funciona
Esto interpreta los dígitos bijectivos de base 3 de n como un camino hacia abajo del árbol de los triples pitagóricos primitivos . Se ejecuta sin buscar en operaciones O (log n ).
fuente
Jalea ,
1918 bytesEl programa toma un índice n basado en 1 e imprime los primeros n PPTs [c, b, a] en orden lexicográfico.
Esta es una solución O (64 n ) , por lo que TIO se atragantará con las entradas 4 y superiores. Trabajaré para hacerlo más rápido.
Pruébalo en línea!
Versión alternativa, O (n 3 ), probablemente válida
Para encontrar el n º triplete - [c n , b n , un n ] - la solución anterior supone que c n ≤ 4 n , que es fácil de verificar. Sin embargo, A020882 demuestra que c n ~ 2πn , por lo que hay una k tal que c n ≤ kn para todo n .
Si podemos tomar k = 7 , la solución a continuación también es válida (y mucho, mucho más rápido).
Pruébalo en línea!
Cómo funciona
fuente
JavaScript (ES7),
106105103 bytesEmite el enésimo PPT. Los resultados están indexados en 1 y ordenados por el valor de b .
Manifestación
Mostrar fragmento de código
fuente
MATL , 63 bytes
Pruébalo en línea!
Una lección de golf salió terriblemente mal. Lo publico de todos modos porque me pregunto si hay formas de jugar mejor al golf.
Basé esto en esta página de Wikipedia en combinación con la fórmula de Euclides, para generar constructivamente todos los triples en lugar de enfoques de prueba y error.
Primero, los pares coprimos impares se generan como un árbol ternario. Esto se realiza como una multiplicación de matriz grande, que representa la mayor parte del recuento de bytes. Luego, se aplica la fórmula de Euclides, posiblemente también de una manera muy perdida de bytes. Si alguien tiene consejos para estas dos partes, me encantaría escucharlos.
Tenga en cuenta que, para guardar bytes, este programa genera un árbol con la misma profundidad que la entrada, en lugar de hacerlo
log3(n)
. Además, se generan elementos secundarios para cada fila en lugar de solo para la última fila del árbol, y luego se filtran nuevamente conXu
. Esto en cuanto a un enfoque constructivo eficiente.fuente
Haskell, 65 bytes
Indexación basada en 0. Para un determinado
c
, seb
ejecuta hastac
ya
hastab
, por lo quec > b > a
siempre se mantiene.Pruébalo en línea!
fuente
Pitón,
67504846 BytesUsando las fórmulas encontradas en wikipedia,
a=m*n, b=(m^2-n^2)/2, c=(m^2+n^2)/2
donde
m>n>0
em
yn
son coprimes e impares. Aqui esta el codigo-17 bytes gracias a @Martin Ender
Pruébalo en línea
Funciona siempre que el valor de la
n
variable en la ecuación sea 1, lo que significa quem
simplemente es cualquier otro valor impar, en este caso,3+2*n
donden
está el número del triple pitagórico primitivo. Esto nos permite asumir el valor de 1 para todos losn
valores.fuente
a
(y si lo hiciera, podría deshacerse de los dos espacios allí). Tampoco estoy seguro de por qué estáprint
allí, simplemente podría devolver los valores de la propia lambda.Casco , 18 bytes
Pruébalo en línea!
-4 bytes gracias a Zgarb, con inspiración de Dennis
Enfoque de fuerza bruta súper lenta, no funcionará en TIO para entradas mayores de 1. Puede probar una versión más manejable, limitada a a, b≤200 aquí
Explicación
fuente
c
? en ese caso, esta solución necesitaría ser reparadac
. Esta solución de 18 bytes (que usa otro truco de Dennis) funciona independientemente.Mathematica, 89 bytes
utilizando Solve ordenado por c
Mathematica, 124 bytes
fuente
R (+ números), 88 bytes
Para usar un generador incorporado para generar los números, se necesita una cantidad sorprendente de bytes para obtener lo que queremos. El incorporado toma dos argumentos
c1
yc2
, y devuelve los trillizos que tienenc >= c1 & c <= c2
. Esto hace que sea un poco molesto llegar aln
enésimo triplete. Esto seguirá aumentandoc2
1 a la vez hasta que la salida tenga suficientes filas.fuente
PHP , 273 bytes
t($n)
devuelve una matriz de [a, b, c] al ordenara < b < c
Pruébalo en línea! (el código también es legible allí)
fuente
C, 158 bytes
Creo que esta es mi primera presentación aquí, por lo que probablemente puedas hacerlo mejor.
Y versión sin golf:
Para a 2 + b 2 = c 2 , el orden aumenta c luego aumenta a .
No puede haber el doble de PPT que b es al menos a en este algoritmo.fuente
Gelatina ,
2725 bytesEsta es una implementación del enfoque de árbol de la respuesta de Haskell @ AndersKaseorg , con un orden de ramificación diferente. El programa usa indexación basada en 0 y toma datos de STDIN.
Pruébalo en línea!
Fondo
Como se menciona en la página de Wikipedia Árbol de triples pitagóricos primitivos , cada PPT se puede obtener multiplicando repetidamente a la izquierda el vector de fila (3, 4, 5) por matrices con ciertas propiedades.
En cada iteración, el resultado anterior se puede multiplicar por A , B o C , que se pueden elegir de la siguiente manera.
Cuando A , B y C son fijos, cada PPT se puede obtener de una manera única.
Cómo funciona
fuente
APL (NARS), 90 caracteres, 180 bytes
si el argumento de la función anterior es ⍵, la función anterior devolvería el elemento del índice ⍵ (basado en 1) de la matriz tiene elementos triples pitagóricos (a, b, c) donde a <= b <= c y esa matriz es orden primero para a, (el lado más corto), luego para b (el otro lado no es hipotenusa). Habría algo mal porque no se ve donde ordeno para b también ... prueba:
Está relacionado con http://oeis.org/A020884 y http://oeis.org/A020884/b020884.txt
A020884: Patas cortas ordenadas de triángulos pitagóricos primitivos.
No sé si es correcto, parece que la función da el resultado correcto del primer lado del triángulo hasta 1000, pero no sé por el resto, y es posible que algún triple no sea correcto incluso <1000.
fuente
JavaScript, 101 bytes
Según la fórmula de Euclides, todos los triples pitagóricos primitivos se pueden generar a partir de enteros
m
yn
conm>n>0
,m+n
impargcd(m,n)==1
( Wikipedia )Esta función enumera todos los
m,n
pares que incrementan m a partir dem=2
y disminuyenn
en 2 a partir dem-1
(por lo quem+n
es extraño)Menos golf
Prueba
fuente