( verwandt )

Ein pythagoreisches Dreifach ist eine Liste (a, b, c), die die Gleichung a ² + b ² = c ² erfüllt .

Eine Primitive Pythagoreisches Tripel (PPT) ist eine , wo a, bund csind alle coprime (dh die einzige gemeinsame Teiler zwischen den drei Elementen ist 1). Das (3, 4, 5)rechte Dreieck ist beispielsweise ein berühmtes primitives pythagoreisches Dreieck.

Die Herausforderung

• Bei gegebener Eingabe nwird die nth PPT ausgegeben . Oder,
• Bei gegebener Eingabe nwerden die ersten nPPTs ausgegeben.

Es gibt mehrere Möglichkeiten, diese PPTs zu ordnen, um eine geordnete Liste zu bilden, um zu bestimmen, welche die nth ist. Sie können eine beliebige Reihenfolge auswählen, solange Sie nachweisen können (informell ist in Ordnung), dass Ihr Algorithmus jede mögliche eindeutige PPT generieren kann. Zum Beispiel sollte Ihr Code nicht beide ausgeben (3,4,5)und (4,3,5)da es sich um Duplikate desselben Tripels handelt, bitte das eine oder andere.

Ebenso ist es in Ordnung, ob Ihr Code null- oder einindexiert ist, solange Sie angeben, welchen Code Sie verwenden.

Beispiele

In den folgenden Beispielen verwende ich die Ein-Indexierung, gebe die nth-PPT aus und ordne nach kleinsten c, dann nach kleinsten aund dann nach kleinsten b.

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

Regeln

• Die Ein- und Ausgabe kann in jedem beliebigen Format erfolgen .
• Bitte geben Sie in Ihrem Beitrag an, wie Ihre Einträge sortiert sind und ob Ihre Einträge 0-indiziert oder 1-indiziert sind.
• Ihre gewählte Bestellung kann keine Duplikate erstellen.
• Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
• Fügen Sie nach Möglichkeit einen Link zu einer Online-Testumgebung hinzu, damit andere Benutzer Ihren Code ausprobieren können!
• Standardlücken sind verboten.
• Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.

Jelly , 27 25 Bytes

2 Bytes dank Jonathan Allan.

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

Probieren Sie es online!

Gibt die ersten n1-indizierten Tripel aus [b, a, c], sortiert nach Erhöhen bund dann a.

Verwendet den Algorithmus von Wikipedia :

Dies erzeugt alle primitiven Tripel für alle eindeutigen Coprime-Paare von ungeraden ganzen Zahlen m > n > 0.

Erläuterung

+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

Die Eingabe ist 1-basiert. Die Ausgabereihenfolge garantiert, dass jedes Tripel genau einmal vorkommt. Die Reihenfolge wird im Folgenden erläutert. Die Erklärung erfordert ein wenig Einblick in die Funktionsweise des Programms.

Der Code erhöht ständig einen Zähler kin einer Schleife, beginnend bei 1. Für jede kerzeugt er alle Paare mit a = 1,...,k, b = 1,...,k, a < b, und Picks jene , die einen pythagoreischen triple mit geben c <= k. Die Paare werden in der Reihenfolge zunehmender erhalten b, dann a.

Jedes Paar wird dann durch seinen gcd geteilt. Die resultierenden (möglicherweise duplizierten) Paare werden als zweispaltige Matrix angeordnet. Diese Matrix ist vertikal mit einer ähnlichen Matrix verkettet, die die akkumulierten Ergebnisse enthält, die für kleinere Werte von erhalten wurden k. Die Zeilen der Matrix werden dann stabil dedupliziert. Dadurch werden zwei Arten von Duplikaten entfernt:

1. Paare, die mehr als einmal für den Strom gefunden wurden k(wie z. B. 3,4, was sich auch aus der 6,8Division durch den gcd ergibt );

2. Paare, die bereits mit kleineren gefunden wurden k.

Tatsächlich findet jede Iteration kalle Paare, die bereits für vorherige Iterationen gefunden wurden. Aber es kann sie in einer anderen Reihenfolge finden . Zum Beispiel k=25finden Sie das Triple 7,24,25und nicht 20,21,29(weil cnicht überschreiten kann k). Später wird Iteration k=29beides finden, aber mit 20,21,29 vorher 7,24,25 (die Reihenfolge nimmt bdann zu a). Aus diesem Grund werden nicht alle Paare für die neuesten gefunden, sondern kan die vorherigen angehängt und stabil dedupliziert. Dadurch wird sichergestellt, dass die Reihenfolge für alle Eingaben gleich ist n.

Das Obige garantiert, dass jedes primitive pythagoreische Tripel irgendwann auftaucht und nur noch einmal auftaucht. Bei der Eingabe endet ndie Schleife, kwenn mindestens ngültige Tripel erhalten wurden. und dann ist das nDreifache die Ausgabe.

Probieren Sie es online!

Oder verwenden Sie diesen geänderten Code, um die ersten nTriples zu sehen:

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

Probieren Sie es 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)

Probieren Sie es online!

Wie es funktioniert

Dies interpretiert die bijektiven Basis-3- Ziffern von n als Pfad entlang des Baums der primitiven pythagoreischen Tripel . Es wird ohne Suchen in O- Operationen (log n ) ausgeführt.

Jelly , 19 18 Bytes

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

Das Programm verwendet einen 1-basierten Index n und druckt die ersten n PPTs [c, b, a] in lexikographischer Reihenfolge.

Dies ist eine O (64 ⁿ ) -Lösung, sodass TIO ab Eingang 4 drosselt. Ich werde daran arbeiten, es schneller zu machen.

Probieren Sie es online!

Alternative Version, O (n ³ ), wahrscheinlich gültig

Um das n- ^te Triplett zu finden - [c _n , b _n , a _n ] - nimmt die obige Lösung an, dass c _n ≤ 4 ^{n ist} , was leicht zu überprüfen ist. Jedoch A020882 beweist , dass c _n ~ 2πn , so gibt es einen k , so dass c _n ≤ kn für alle n .

Wenn wir k = 7 nehmen können , ist die unten stehende Lösung ebenfalls gültig (und viel, viel schneller).

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

Probieren Sie es online!

Wie es funktioniert

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 Byte

Gibt die n-te PPT aus. Die Ergebnisse sind 1-indiziert und nach dem Wert von b geordnet .

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

Probieren Sie es online!

Eine Golfstunde, die furchtbar schief gelaufen ist. Ich poste es trotzdem, weil ich mich frage, ob es Möglichkeiten gibt, dies besser zu golfen.

Ich habe dies auf dieser Wikipedia-Seite in Kombination mit der Formel von Euclid basiert, um konstruktiv alle Tripel zu generieren und nicht nur Versuche und Irrtümer.

Zunächst werden ungerade Koprime-Paare als ternärer Baum erzeugt. Dies geschieht als eine große Matrixmultiplikation, die den größten Teil der Byteanzahl ausmacht. Dann wird die Euklid-Formel angewendet, möglicherweise auch in einer sehr byteschwachen Weise. Wenn jemand Tipps für diese beiden Teile hat, würde ich sie gerne hören.

Beachten Sie, dass dieses Programm zum Speichern von Bytes einen Baum mit der gleichen Tiefe wie die Eingabe generiert log3(n). Außerdem werden Kinder für jede Zeile und nicht nur für die letzte Zeile des Baums generiert und dann erneut mit gefiltert Xu. Soviel zu einem effizienten konstruktiven Ansatz.

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

0-basierte Indizierung. Für eine gegebene c, bzu läuft cunda bis zu b, c > b > ahält also immer.

Probieren Sie es online!

Python, 67 50 48 46 Bytes

Verwenden Sie die Formeln auf Wikipedia,

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

wo m>n>0und mund nsind coprimes und ungerade. Hier ist der Code

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

-17 Bytes dank @Martin Ender

Probieren Sie es online

Arbeitet so, dass der Wert der nVariablen in der Gleichung immer 1 ist, was bedeutet, dass dies meinfach ein anderer ungerader Wert ist, in diesem Fall, 3+2*nbei dem nes sich um die Nummer des primitiven pythagoreischen Tripels handelt. Dies ermöglicht es uns, für alle nWerte den Wert 1 anzunehmen .

Schale , 18 Bytes

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

Probieren Sie es online!

-4 Bytes danke an Zgarb, mit Inspiration von Dennis

Super-langsamer Brute-Force-Ansatz, funktioniert bei TIO-Eingängen über 1 nicht. Sie können hier eine handlichere Version ausprobieren, die auf a, b ≤ 200 beschränkt ist

Erläuterung

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

using Solve sortiert nach 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 (+ Zahlen), 88 Bytes

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

Um mit einem Built-In die Zahlen zu generieren, ist eine überraschende Menge an Bytes erforderlich, um das zu erhalten, was wir wollen. Das Builtin nimmt zwei Argumente c1und c2und gibt die Triplets zurück, die haben c >= c1 & c <= c2. Dies macht es etwas ärgerlich, zum n-ten Triplett zu gelangen. Dies erhöht immer nur c21 auf einmal, bis die Ausgabe gerade genug Zeilen ist.

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) Gibt ein Array von [a, b, c] mit der Reihenfolge zurück a < b < c
• Gibt einen nullbasierten Index zurück

Probieren Sie es online! (Code ist dort auch lesbar)

C 158 Bytes

Ich glaube, dies ist meine erste Einreichung hier, also können Sie es höchstwahrscheinlich besser machen.

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

Und ungolfed version:

#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");
}

Für a ² + b ² = c ² erhöht sich die Reihenfolge von c zu a .

Jelly , 27 25 Bytes

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

Dies ist eine Implementierung des Baumansatzes von @ AndersKaseorgs Haskell-Antwort mit einer anderen Verzweigungsreihenfolge. Das Programm verwendet eine 0-basierte Indexierung und nimmt Eingaben von STDIN entgegen.

Probieren Sie es online!

Hintergrund

Wie auf der Wikipedia-Seite Tree of primitive Pythagorean triples erwähnt , kann jede PPT durch wiederholtes Linksmultiplizieren des Zeilenvektors (3, 4, 5) erhalten werden. mit Matrizen mit bestimmten Eigenschaften erhalten werden.

In jeder Iteration kann das vorherige Ergebnis mit A , B oder C multipliziert werden , was wie folgt gewählt werden kann.

Wenn A , B und C festgelegt sind, kann jede PPT auf einzigartige Weise erhalten werden.

Wie es funktioniert

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 Zeichen, 180 Byte

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

Wenn das Argument der obigen Funktion ⍵ ist, würde die obige Funktion das Element des Index zurückgeben. ⍵ (1 basiert) des Arrays enthält Elemente Pythagoreische Tripel (a, b, c), wobei a <= b <= c und dieses Array ist Reihenfolge zuerst für a (die Seite ist kürzer), dann für b (die andere Seite ist nicht hypotenuse). Es wäre etwas nicht in Ordnung, da dort nicht zu sehen ist, wo ich für b bestelle ... 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  

es ist verwandt mit http://oeis.org/A020884 und http://oeis.org/A020884/b020884.txt

A020884: Geordnete kurze Beine aus primitiven pythagoreischen Dreiecken.

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

Ich weiß nicht, ob es richtig ist, es scheint, dass die Funktion das korrekte Ergebnis der ersten Seite des Dreiecks bis 1000 liefert, aber ich weiß nicht, ob es noch übrig ist, und es kann sein, dass ein Triple auch <1000 nicht richtig ist.

JavaScript, 101 Bytes

Nach der Euklidschen Formel können alle primitiven pythagoreischen Tripel aus ganzen Zahlen mund nmit m>n>0, m+nodd gcd(m,n)==1( Wikipedia ) erzeugt werden.

Diese Funktion zählt alle m,nPaare auf, die ab m um m=2eins inkrementieren und ab n2 um eins dekrementieren m-1(also m+nungerade).

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

Weniger golfen

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

Prüfung

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