( relacionado )

Um triplo pitagórico é uma lista (a, b, c)que satisfaz a equação a ² + b ² = c ² .

Um Triplo Pitágico Primitivo (PPT) é aquele em que a, be csão todos coprimes (isto é, o único divisor comum entre os três elementos é 1). Por exemplo, o (3, 4, 5)triângulo retângulo é um famoso Triplo Pitágico Primitivo.

O desafio

• Dada a entrada n, produza o nth PPT. Ou,
• Dada a entrada n, nproduza os primeiros PPTs.

Existem várias maneiras de solicitar esses PPTs para formar uma lista bem ordenada, para determinar qual é o nth. Você pode escolher qualquer pedido que quiser, desde que possa provar (informalmente é bom) que seu algoritmo pode gerar todos os PPT únicos possíveis. Por exemplo, seu código não deve produzir os dois (3,4,5)e, (4,3,5)como esses são duplicados do mesmo triplo - um ou outro, por favor.

Da mesma forma, se o seu código é zero ou um indexado é bom, desde que você indique qual está usando.

Exemplos

Para os exemplos abaixo, estou usando a indexação única, produzindo o nth PPT e solicitando o menor c, o menor ae o menor b.

n | output
1 | (3, 4, 5)
2 | (5, 12, 13)
5 | (20, 21, 29)
12| (48, 55, 73)

Regras

• A entrada e saída podem ser fornecidas em qualquer formato conveniente .
• Em seu envio, indique como suas entradas são ordenadas e se elas são indexadas em 0 ou 1.
• Seu pedido escolhido não pode criar duplicatas.
• Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
• Se possível, inclua um link para um ambiente de teste on-line para que outras pessoas possam experimentar seu código!
• As brechas padrão são proibidas.
• Isso é código-golfe, portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.

Geléia , 27 25 bytes

2 bytes graças a Jonathan Allan.

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

Experimente online!

Produz os primeiros ntriplos indexados em 1 [b, a, c], classificados por aumento be depois a.

Usa o algoritmo da Wikipedia :

Isso gera todos os triplos primitivos para todos os pares coprime exclusivos de números inteiros ímpares m > n > 0.

Explicação

+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].

MATL , 36 bytes

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

A entrada é baseada em 1. A ordem de saída garante que cada triplo apareça exatamente uma vez. A ordem é explicada a seguir. A explicação requer um pouco de como o programa funciona.

O código continua aumentando um contador kem um loop, começando em 1. Para cada kele gera todos os pares com a = 1,...,k, b = 1,...,k, a < b, e picaretas aquelas que dão um terno pitagórico com c <= k. Os pares são obtidos em ordem crescente b, então a.

Cada par é então dividido pelo seu MDC. Os pares resultantes (possivelmente duplicados) são organizados como uma matriz de duas colunas. Essa matriz é concatenada verticalmente com uma matriz semelhante contendo os resultados acumulados obtidos para valores menores de k. As linhas da matriz são então desduplicadas de forma estável. Isso remove dois tipos de duplicatas:

1. Pares que foram encontrados mais de uma vez para a corrente k(como 3,4, que também resulta da 6,8divisão pelo seu MDC);

2. Pares que já foram encontrados com menores k.

De fato, cada iteração klocaliza todos os pares que já foram encontrados para iterações anteriores. Mas pode encontrá-los em uma ordem diferente . Por exemplo, k=25encontrará o triplo 7,24,25e não 20,21,29(porque cnão pode exceder k). Mais tarde, a iteração k=29encontrará os dois, mas com 20,21,29 antes 7,24,25 (a ordem está aumentando b, então a). É por isso que, em vez de manter todos os pares encontrados para o mais recente k, os anexamos aos anteriores e desduplicamos de forma estável. Isso garante que o pedido seja o mesmo para qualquer entrada n.

O acima garante que cada triplo pitagórico primitivo acabará por aparecer e aparecerá apenas uma vez. Para entrada n, o loop over ktermina quando pelo menos ntriplos válidos foram obtidos; e então o ndécimo terceiro triplo é produzido.

Experimente online!

Ou use este código modificado para ver os primeiros ntriplos:

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

Experimente online!

Haskell , 98 bytes

f 0=(3,4,5)
f n|let(a,b,c)=f$div(n-1)3;r=mod n 3;d=a*(-1)^2^r;e=b*(-1)^r;s=2*(d+e+c)=(s-d,s-e,s+c)

Experimente online!

Como funciona

Isso interpreta os dígitos bijetivos da base-3 de n como um caminho abaixo da árvore dos triplos pitagóricos primitivos . É executado sem pesquisa nas operações O (log n ).

Geléia , 19 18 bytes

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

O programa pega um índice baseado em 1 n e imprime os primeiros n PPTs [c, b, a] em ordem lexicográfica.

Como é uma solução O (64 ⁿ ) , o TIO engasga com as entradas 4 e superiores. Vou trabalhar para torná-lo mais rápido.

Experimente online!

Versão alternativa, O (n ³ ), provavelmente válida

Para encontrar o n ^th tripleto - [c _n , b _n , um _n ] - a solução acima assume que c _n ≤ 4 ^N , o qual é fácil de verificar. No entanto, A020882 prova que c _n ~ 2πn , então existe um k tal que c _n ≤ kn para todos os n .

Se pudermos tomar k = 7 , a solução abaixo também é válida (e muito, muito mais rápida).

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

Experimente online!

Como 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².

JavaScript (ES7), 106 105 103 bytes

Emite o enésimo PPT. Os resultados são indexados em 1 e ordenados pelo 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)

Demo

let f =

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)

for(n = 1; n <= 20; n++) {
  console.log('#' + n + ' : ' + f(n));
}

MATL , 63 bytes

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

Experimente online!

Uma lição de golfe deu terrivelmente errado. Estou postando de qualquer maneira, porque estou me perguntando se existem maneiras de jogar isso melhor.

Baseei isso nesta página da Wikipedia em combinação com a fórmula de Euclides, para gerar construtivamente todas as triplas, em vez de abordagens de tentativa e erro.

Primeiro, pares ímpares de coprime são gerados como uma árvore ternária. Isso é feito como uma grande multiplicação de matrizes, representando a maior parte da contagem de bytes. Então, a fórmula de Euclides é aplicada, possivelmente também de uma maneira que desperdiça muitos bytes. Se alguém tiver dicas para essas duas partes, eu adoraria ouvi-las.

Observe que, para salvar bytes, este programa gera uma árvore da mesma profundidade que a entrada, em vez de log3(n). Além disso, os filhos são gerados para cada linha e não apenas para a última linha da árvore e depois filtrados novamente com Xu. É o suficiente para uma abordagem construtiva 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²

Haskell, 65 bytes

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

Indexação baseada em 0. Para um dado c, bcorre até ce aaté b, c > b > asempre é válido.

Experimente online!

Python, 67 50 48 46 bytes

Usando as fórmulas encontradas na wikipedia,

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

onde m>n>0e me nsão coprimes e ímpares. Aqui está o código

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

-17 bytes graças a @Martin Ender

Experimente Online

Funciona sempre tendo o valor da nvariável na equação sendo 1, o que significa que msimplesmente é qualquer outro valor ímpar, neste caso, 3+2*nonde né o número do triplo pitagórico primitivo. Isso nos permite assumir o valor de 1 para todos os nvalores.

Casca , 18 bytes

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

Experimente online!

-4 bytes obrigado a Zgarb, com inspiração em Dennis

Abordagem de força bruta super lenta, não funcionará no TIO para entradas maiores que 1. Você pode tentar uma versão mais gerenciável, limitada a a, b≤200 aqui

Explicação

↑ü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

Mathematica, 89 bytes

usando 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][[#]])&

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 um builtin para gerar os números, são necessários uma quantidade surpreendente de bytes para obter o que queremos. O builtin usa dois argumentos c1e c2, e retorna os trigêmeos que possuem c >= c1 & c <= c2. Isso torna um pouco chato chegar ao ntrigésimo trigêmeo. Isso continuará aumentando c21 de cada vez até que a saída seja apenas o suficiente em linhas.

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) retorna uma matriz de [a, b, c] com ordenação a < b < c
• Retorna um índice baseado em zero

Experimente online! (o código também pode ser lido aqui)

C, 158 bytes

Acredito que esta é a minha primeira submissão aqui, então você provavelmente pode fazer melhor.

#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++;};}

E versão não destruída:

#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 ² + b ² = c ² , a ordem está aumentando c e depois aumentando a .

Geléia , 27 25 bytes

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

Esta é uma implementação da abordagem em árvore da resposta Haskell do @ AndersKaseorg , com uma ordem de ramificação diferente. O programa usa indexação baseada em 0 e recebe informações do STDIN.

Experimente online!

fundo

Como mencionado na página da Wikipedia Árvore dos triplos pitagóricos primitivos , todo PPT pode ser obtido multiplicando-se repetidamente o vetor de linha (3, 4, 5) por matrizes com determinadas propriedades.

Em cada iteração, o resultado anterior pode ser multiplicado à esquerda por A , B ou C , que pode ser escolhido da seguinte maneira.

Quando A , B e C são fixos, cada PPT pode ser obtido de uma maneira única.

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

APL (NARS), 90 caracteres, 180 bytes

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

se o argumento da função acima for ⍵, a função acima retornaria o elemento do índice ⍵ (com base em 1) da matriz tem elementos triplos pitagóricos (a, b, c) em que a <= b <= ce essa matriz é ordem primeiro para a, (o lado mais curto), depois para b (o outro lado não é hipotenusa). Haveria algo errado, porque não é visto onde eu pedir para b também ... test:

  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 com http://oeis.org/A020884 e http://oeis.org/A020884/b020884.txt

A020884: Pernas curtas 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 

Eu não sei se está certo, parece que a função dá o resultado correto do primeiro lado do triângulo até 1000, mas eu não sei o que resta, e possível pode ser que alguns triplos não estejam certos, mesmo <1000.

JavaScript, 101 bytes

Pela fórmula de Euclides, todos os triplos pitagóricos primitivos podem ser gerados a partir de números inteiros me ncom m>n>0, m+nímpar gcd(m,n)==1( Wikipedia )

Esta função enumera todos os m,npares que aumentam m começando m=2e decrementando n2 começando m-1(de modo que m+né ímpar)

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 golfe

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]
}

Teste

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