Triples pitagóricos primitivos

29

( 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, by cson 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 del nth PPT O,
  • Dada entrada n, salida los primeros nPPT.

Hay varias formas de ordenar estos PPT para formar una lista bien ordenada, para determinar cuál es el nth. 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 nPPT 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 por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).
AdmBorkBork
fuente
Relacionado
millas
2
A103606 .
millas
¿Cuál es el mayor aporte que tenemos que soportar? ¿Podemos suponer que se ajusta a las capacidades de nuestro idioma de elección?
Sr. Xcoder
1
@ Mr.Xcoder Sí; esa es una suposición segura estándar, a menos que esté usando eso para explotar una laguna (por ejemplo, el lenguaje solo admite números de 1 bit) para hacer que el problema sea trivial.
AdmBorkBork
2
Encontré la respuesta a mi pregunta: a y b deben ser coprimos y esto es suficiente pruebawiki.org/wiki/…
edc65

Respuestas:

12

Jalea , 27 25 bytes

2 bytes gracias a Jonathan Allan.

²IH;Pµ;ÆḊ
+2ḶḤ‘Œcg/ÐṂÇ€Ṣḣ

Pruébalo en línea!

Emite los primeros ntriples indexados en 1 [b, a, c], ordenados por aumento by luegoa .

Utiliza el algoritmo de Wikipedia :

a = mn, b = (m² - n²) / 2, c = (m² + n²) / 2

Esto genera todos los triples primitivos para todos los pares coprimos únicos de enteros impares m > n > 0 .

Explicación

+2ḶḤ‘Œcg/ÐṂÇ€Ṣḣ    Main link. Argument: n
+2                   Add 2 to n, to get enough results.
  Ḷ                  Get integers [0, 1, ..., n+1].
   Ḥ                 Double to get [0, 2, ..., 2n+2].
    ‘                Increment to get [1, 3, ..., 2n+3].
     Œc              Get all ordered pairs [[1, 3], [1, 5], ..., [2n+1, 2n+3]].
       g/            GCD of each pair.
         ÐṂ          Grab the pairs with minimal GCD (which is 1).
           ǀ        Call the helper link on each pair to get the triples.
             Ṣ       Sort the triples first by a, then by b, then by c.
              ḣ      Get the last n.

²IH;Pµ;ÆḊ    Helper link. Argument: pair [m, n]
²              Square to get [m², n²].
 I             Increments: get [m²-n²].
  H            Halve: get [(m²-n²)/2], i.e. [b].
    P          Product: get mn, i.e. a.
   ;           Append to get [b, a].
     µ         Begin a new monadic chain with argument [b, a].
       ÆḊ      Get the length of the vector, i.e. c.
      ;        Append to get [b, a, c].
PurkkaKoodari
fuente
Esa es una muy buena explicación. ¡Gracias!
AdmBorkBork
g/Ị$Ðf-> g/ÐṂpara guardar dos bytes (ya que el mínimo mcd es 1 y siempre habrá al menos una de esas entradas).
Jonathan Allan
También se puede guardar otro byte (aunque lo hace menos eficiente) reemplazándolo +2ḶḤ‘Œccon un ²Rm2Œcmensaje que no funcionará para una entrada de 1:(
Jonathan Allan
@ JonathanAllan Gracias por el mínimo. Probé muchos rangos de 2 bytes, pero desafortunadamente ninguno era lo suficientemente grande. ( ²ḶḤ‘Œcfue uno de los primeros en los que pensé).
PurkkaKoodari
8

MATL , 36 bytes

`@:Ut&+wmR&fZd1Mhw/vXutnGE<]GY)t&2|h

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 ken un ciclo, comenzando en 1. Para cada kgenera todos los pares con a = 1,...,k, b = 1,...,k, a < b, y picos aquellas que dan una Pitágoras triple con c <= k. Los pares se obtienen en orden de aumento b, 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:

  1. Pares que se han encontrado más de una vez para la corriente k(como 3,4, que también resulta de 6,8cuando se divide por su mcd);

  2. Pares que ya se encontraron con los más pequeños k.

De hecho, cada iteración kencuentra todos los pares que ya se encontraron para las iteraciones anteriores. Pero puede encontrarlos en un orden diferente . Por ejemplo, k=25encontrará el triple 7,24,25y no 20,21,29(porque cno puede exceder k). Más adelante, la iteración k=29encontrará ambos, pero con 20,21,29 antes 7,24,25 (el orden aumenta b, entonces a). Es por eso que, en lugar de mantener todos los pares encontrados para el último k, los agregamos a los anteriores y deduplicamos de manera estable. Hacerlo asegura que el orden sea el mismo para cualquier entrada n.

Lo anterior garantiza que cada triple pitagórico primitivo finalmente aparecerá, y aparecerá solo una vez. Para la entrada n, el ciclo kfinaliza cuando nse han obtenido al menos triples válidos; y luego el nenésimo triple es la salida.

Pruébalo en línea!

O use este código modificado para ver los primeros ntriples:

`@:Ut&+wmR&fZd1Mhw/vXutnGE<]G:Y)tU&2sX^h

Pruébalo en línea!

Luis Mendo
fuente
1
Buena explicación
AdmBorkBork
5

Jalea , 19 18 bytes

*g/²_/
4*œc3UṢÇÐḟḣ

El 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).

*g/²_/
×7œc3UṢÇÐḟḣ

Pruébalo en línea!

Cómo funciona

4*œc3UṢÇÐḟḣ  Main link. Argument: n

4*           Compute 4**n, the n-th power of 4.
  œc3        Take all 3-combinations of the set {1, ..., 4**n}, each sorted in
             ascending order. The triples themselves are sorted lexicographically.
     U       Upend; reverse each triple [a, b, c], yielding [c, b, a].
      Ṣ      Sort the descending triples lexicographically. This ensures that their
             order is independent of n.
       ÇÐḟ   Keep only triples for which the helper link returns a falsy value.
          ḣ  Dyadic head; take the first n triples.


*g/²_/       Helper link. Argument: [c, b, a]

 g/          Reduce [c, b, a] by greatest common divisor, yielding g.
*            Elevate the integers to that power, computing [c**g, b**g, a**g].
   ²         Square, yielding [c**2g, b**2g, a**2g].
    _/       Reduce by subtraction, yielding c**2g - b**2g - a**2g.
             Fermat's Last Theorem assures that this difference will be non-zero
             whenever g > 1, so this yields 0 iff g = 1 and c² = a² = b².
Dennis
fuente
4

JavaScript (ES7), 106 105 103 bytes

Emite el enésimo PPT. Los resultados están indexados en 1 y ordenados por el valor de b .

n=>(g=(a,b)=>b?g(b,a%b):a,F=a=>(x=a*a+b*b,c=x**.5|0)*c-x*g(a,g(b,c))||--n?F(a-b?a+1:!++b):[a,b,c])(b=1)

Manifestación

Arnauld
fuente
4

MATL , 63 bytes

3lvi:"t"[HlHllO;aOlOHl]!@Y*2eh]]!XuGY)&*tt[lO;Oa]*ssD2)ED2Xy*ss

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 con Xu. Esto en cuanto a un enfoque constructivo eficiente.

3lv % Push root node of ternary tree
i:" % Generate a tree of depth of input (WAY too large, but golfy)
t"  % loop over all nodes (golfier than looping over last tree row)
[HlHllO;aOlOHl]! % Matrix to generate three children of current node
@Y* % Multiply with current node to get children
2e  % Reshape to get node pairs
h]] % Append to tree, exit loops
!Xu % Remove duplicates (more efficient to do it before last ] but golfier this way)
GY) % Select n-th odd coprime pair
&*tt % Multiply with it's own transpose to get [m²,m*n;m*n,n²]
[lO;Oa]*ssD % Sum of matrix multiplication = m²-n² to get a
2)ED % Second element doubled for b=2mn
2Xy*ss % Sum of matrix multiplication with identify matrix to get c=m²+n²
Sanchises
fuente
3

Haskell, 65 bytes

([(a,b,c)|c<-[5..],b<-[1..c],gcd c b<2,a<-[1..b],a^2+b^2==c^2]!!)

Indexación basada en 0. Para un determinado c, se bejecuta hasta cy ahasta b, por lo que c > b > asiempre se mantiene.

Pruébalo en línea!

nimi
fuente
3

Pitón, 67 50 48 46 Bytes

Usando las fórmulas encontradas en wikipedia,

a=m*n, b=(m^2-n^2)/2, c=(m^2+n^2)/2

donde m>n>0e my nson coprimes e impares. Aqui esta el codigo

lambda n:[3+2*n,~-(3+2*n)**2-1/2,-~(3+2*n)**2/2]

-17 bytes gracias a @Martin Ender

Pruébalo en línea

Funciona siempre que el valor de la nvariable en la ecuación sea 1, lo que significa que msimplemente es cualquier otro valor impar, en este caso, 3+2*ndonde nestá el número del triple pitagórico primitivo. Esto nos permite asumir el valor de 1 para todos los nvalores.

Professor_Joykill
fuente
Bienvenido a PPCG! Las funciones sin nombre están bien, por lo que no necesita asignar el lambda a(y si lo hiciera, podría deshacerse de los dos espacios allí). Tampoco estoy seguro de por qué está printallí, simplemente podría devolver los valores de la propia lambda.
Martin Ender
"puedes probar (informalmente está bien) que tu algoritmo puede generar cada PPT único posible". Pero este método solo genera aquellos en los que la hipotenusa es 1 más larga que una pierna. Nunca genera 8,15,17, por ejemplo.
Rosie F
2

Casco , 18 bytes

↑üOf§=F⌋ȯ¬Ḟ-m□ΠR3N

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

↑üOf§=F⌋ȯ¬Ḟ-m□ΠR3N
              ΠR3N   Get all triples of natural numbers
   f                 Keep only those triples where
      F⌋                their GCD
    §=                  is equal to
        ȯ¬Ḟ-m□          the logical negation of c²-b²-a²
 üO                  Remove duplicates by their sorted version
↑                    Get the first <input> values of this sequence
León
fuente
20 bytes combinando el mapa y el filtro, incluso más lento.
Zgarb
@ Zgarb gracias! Me las arreglé para jugar al golf un byte extra :)
Leo
18 bytes con el truco de resta de la respuesta de Dennis's Jelly.
Zgarb
@Zgarb agradable! Aunque tengo una duda: ¿podría haber dos triples diferentes con el mismoc ? en ese caso, esta solución necesitaría ser reparada
Leo
Hmm, en realidad hay muchos triples con lo mismo c. Esta solución de 18 bytes (que usa otro truco de Dennis) funciona independientemente.
Zgarb
1

Mathematica, 89 bytes

utilizando Solve ordenado por c

SortBy[{a,b,c}/.Solve[a^2+b^2==c^2&&GCD[a,b]==1&&0<a<b<c<9#,{a,b,c},Integers],Last][[#]]&

Mathematica, 124 bytes

(s={};Table[If[IntegerQ[c=Sqrt[a^2+b^2]]&&GCD[a,b]==1,AppendTo[s,{a,b,c}]],{a,9#},{b,9#}];SortBy[Union[Sort/@s],Last][[#]])&
J42161217
fuente
1

R (+ números), 88 bytes

n=scan();while(all(nrow(T)<n))T=numbers::pythagorean_triples(5,5+(F<-F+1));T[n,3:5]

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 c1y c2, y devuelve los trillizos que tienen c >= c1 & c <= c2. Esto hace que sea un poco molesto llegar al nenésimo triplete. Esto seguirá aumentandoc2 1 a la vez hasta que la salida tenga suficientes filas.

JAD
fuente
1

PHP , 273 bytes

function t($n){$x=[];for($c=3;;$c++)for($b=2;$b<$c;$b++)for($a=2;$a<$b;$a++)if(d($a,$b,$c)&&$a**2+$b**2==$c**2){$x[]=[$a,$b,$c];if(--$n==0)return $x;}}function d($a,$b,$c){for($i=2;$i<$a;$i++)if($a%$i==0&&$b%$i==0||$a%$i==0&&$c%$i==0||$b%$i==0&&$c%$i==0)return 0;return 1;}
  • t($n) devuelve una matriz de [a, b, c] al ordenar a < b < c
  • Devuelve un índice basado en cero

Pruébalo en línea! (el código también es legible allí)

Mic1780
fuente
1

C, 158 bytes

Creo que esta es mi primera presentación aquí, por lo que probablemente puedas hacerlo mejor.

#include<stdio.h>
void f(n){int i=0,j=3,k,l;while(1){for(k=1;k<j;k++){for(l=k;l<j;l++){if(j*j==k*k+l*l)i++;if(i==n){printf("%d %d %d",j,k,l);return;}}}j++;};}

Y versión sin golf:

#include <stdio.h>

void f(n)
{
  int i=0, j=3, k, l;
  while (1) {
    for (k=1; k<j; k++) {
      for (l=k; l<j; l++) {
        if (j*j==k*k+l*l)
          i++;
        if (i==n) {
          printf("%d %d %d\n", j, k, l);
          return;
        }
      }
    }
    j++;
  };
}

void main()
{
  int i;

  scanf("%d", &i);

  f(i);
  printf("\n");
}

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.

Tsathoggua
fuente
Bienvenido a PPCG!
JAD
1

Gelatina , 27 25 bytes

⁽0(ḃs
Ɠḃd2Ḥ’×€Ç
3r5DṭÇæ×/

Esta 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.

matrices

Cuando A , B y C son fijos, cada PPT se puede obtener de una manera única.

Cómo funciona

3r5DṭÇæ×/  Main link. No arguments.

3          Set the argument and the return value to 3.
 r5        Create a range from 3 to 5, i.e., [3, 4, 5].
   D       Decimal; convert each integer to base 10, yielding [[3], [4], [5]].
     Ç     Call the second helper link with argument 3.
    ṭ      Tack; append [[3], [4], [5]] to the result.
      æ×/  Reduce by matrix multiplication.
Ɠḃd2Ḥ’×€Ç  Second helper link. Argument: 3

Ɠ          Read and evaluate one line of input, yielding an integer n.
 ḃ         Convert n to bijective base 3.
  d2       Divmod 2; map each digit d to [d/2, d%2].
    Ḥ      Unhalve; multiply the results by 2.
     ’     Decrement the doubled results.
           The previous four atoms apply the following mapping to the digits.
               1 -> [0, 1] -> [0, 2] -> [-1,  1]
               2 -> [1, 0] -> [2, 0] -> [ 1, -1]
               3 -> [1, 1] -> [2, 2] -> [ 1,  1]
        Ç  Call the helper link with argument 3, yielding the following 2D array.
               [[ 1,  2,  2],
                [ 2,  1,  2],
                [ 2,  2,  3]]
      ×€   Multiply each [-1,  1], [ 1, -1], and [ 1,  1] by that matrix, using
           vectorizing multiplication (not matrix multiplication), yielding one 
           of the following three 2D arrays.

               [[-1,  2,  2],    [[ 1, -2,  2],    [[ 1,  2,  2],
                [-2,  1,  2],     [ 2, -1,  2],     [ 2,  1,  2],
                [-2,  2,  3]]     [ 2, -2,  3]]     [ 2,  2,  3]]
⁽0(ḃs      First helper link. Argument: 3

⁽0(        Numeric literal; yield 13041.
   ḃ       Convert 13041 to bijective base 3, yielding [1, 2, 2, 2, 1, 2, 2, 2, 3].
    s      Split the result into chunks of length 3, yielding the aforementioned
           2D array.
Dennis
fuente
1

APL (NARS), 90 caracteres, 180 bytes

{a⊃⍨⍵⊃⍋↑¨a←{⍵[⍋⍵]}¨a/⍨{1=∨/⍵}¨a←{(-/k),(×/2,⍵),+/k←⍵*2}¨a/⍨{>/⍵}¨a←,a∘.,a←⍳(⌊2⍟2+⍵)×9+⌊√⍵}

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:

  f←{a⊃⍨⍵⊃⍋↑¨a←{⍵[⍋⍵]}¨a/⍨{1=∨/⍵}¨a←{(-/k),(×/2,⍵),+/k←⍵*2}¨a/⍨{>/⍵}¨a←,a∘.,a←⍳(⌊2⍟2+⍵)×9+⌊√⍵}
  f¨1..10
3 4 5  5 12 13  7 24 25  8 15 17  9 40 41  11 60 61  12 35 37  13 84 85  15 112 113  16 63 65  

Está relacionado con http://oeis.org/A020884 y http://oeis.org/A020884/b020884.txt

A020884: Patas cortas ordenadas de triángulos pitagóricos primitivos.

  ↑¨f¨1..23
3 5 7 8 9 11 12 13 15 16 17 19 20 20 21 23 24 25 27 28 28 29 31 
  f 999
716 128163 128165 
  f 1000
717 28556 28565 

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.

RosLuP
fuente
0

JavaScript, 101 bytes

Según la fórmula de Euclides, todos los triples pitagóricos primitivos se pueden generar a partir de enteros my ncon m>n>0, m+nimpar gcd(m,n)==1( Wikipedia )

Esta función enumera todos los m,npares que incrementan m a partir de m=2y disminuyen nen 2 a partir de m-1(por lo que m+nes extraño)

c=>eval("g=(a,b)=>b?g(b,a%b):a;for(m=2,n=1;c-=g(m,n)<2;(n-=2)>0||(n=m++));[m*m-n*n,2*m*n,m*m+n*n]")

Menos golf

c => {
  g = (a,b) => b ? g(b,a%b) : a;
  for( m = 2, n = 1; 
       g(m,n) < 2 ? --c : c; 
       (n -= 2) > 0 || (n = m++))
    /* empty for body */;
  return [m*m - n*n, 2*m*n, m*m + n*n]
}

Prueba

F=
c=>eval("g=(a,b)=>b?g(b,a%b):a;for(m=2,n=1;c-=g(m,n)<2;(n-=2)>0||(n=m++));[m*m-n*n,2*m*n,m*m+n*n]")

for(i=1;i<=50;i++) console.log(i+' '+F(i))

edc65
fuente