( powiązane )

Pitagorasa potrójny jest lista (a, b, c), która spełnia równanie ² + b ² = C ² .

Primitive Pitagorasa Triple (PPT) jest jedną gdzie a, bi cwszystkie są względnie pierwsze (czyli tylko wspólny dzielnik między trzema elementami jest 1). Na przykład (3, 4, 5)prawy trójkąt to słynna potrójna pitagorejska potrójna trójka.

Wyzwanie

• Biorąc pod uwagę wejście n, nwyślij th PPT. Lub,
• Biorąc pod uwagę dane wejściowe n, nwypisz pierwsze PPT.

Istnieje wiele sposobów na uporządkowanie tych PPT w celu utworzenia dobrze uporządkowanej listy w celu ustalenia, która z nich jest nth. Możesz wybrać dowolne zamówienie, o ile możesz udowodnić (nieformalnie, że jest w porządku), że Twój algorytm może wygenerować każdy możliwy unikalny PPT. Na przykład, twój kod nie powinien wypisywać obu, (3,4,5)a (4,3,5)ponieważ są to duplikaty tego samego potrójnego - proszę o jedno lub drugie.

Podobnie, czy twój kod jest zerowy czy indeksowany jest w porządku, pod warunkiem, że określisz, którego używasz.

Przykłady

W poniższych przykładach używam indeksowania jednokrotnego, generowania nth PPT i sortowania według najmniejszego c, następnie najmniejszego a, a następnie najmniejszego b.

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

Zasady

• Dane wejściowe i wyjściowe można podawać w dowolnym dogodnym formacie .
• W swoim zgłoszeniu podaj, w jaki sposób są uporządkowane Twoje wpisy i czy Twoje wpisy są indeksowane 0 czy indeksowane 1.
• Wybrane zamówienie nie może tworzyć duplikatów.
• Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
• Jeśli to możliwe, dołącz link do internetowego środowiska testowego, aby inni mogli wypróbować Twój kod!
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Galaretka , 27 25 bajtów

2 bajty dzięki Jonathanowi Allanowi.

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

Wypróbuj online!

Wyprowadza pierwsze n1-indeksowane tróje [b, a, c], posortowane według wzrostu, ba następnie a.

Wykorzystuje algorytm z Wikipedii :

Generuje to wszystkie prymitywne tróje dla wszystkich unikalnych par nieparzystych liczb całkowitych m > n > 0.

Wyjaśnienie

+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 bajtów

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

Dane wejściowe są oparte na 1. Kolejność wyjściowa gwarantuje, że każdy potrójny pojawi się dokładnie raz. Kolejność wyjaśniono poniżej. Wyjaśnienie wymaga dokładniejszego zapoznania się z działaniem programu.

Kod stale zwiększa licznik kw pętli, zaczynając od 1. Dla każdego kgeneruje wszystkie pary z a = 1,...,k, b = 1,...,k, a < b, i wybiera te, które otrzymano z pitagorejską potrójne c <= k. Par uzyskuje się w celu zwiększenia b, a następnie a.

Każda para jest następnie dzielona przez gcd. Powstałe (ewentualnie zduplikowane) pary są ułożone jako macierz dwukolumnowa. Macierz ta jest konkatenowana pionowo z podobną matrycą zawierającą skumulowane wyniki uzyskane dla mniejszych wartości k. Rzędy macierzy są następnie stabilnie deduplikowane. Usuwa to dwa typy duplikatów:

1. Pary, które zostały znalezione więcej niż raz dla prądu k(takie jak 3,4, które również wynikają z 6,8dzielenia przez jego gcd);

2. Pary, które zostały już znalezione z mniejszymi k.

W rzeczywistości każda iteracja kznajduje wszystkie pary, które zostały już znalezione dla poprzednich iteracji. Ale może znaleźć je w innej kolejności . Na przykład k=25znajdzie potrójne 7,24,25i nie 20,21,29(bo cnie może przekroczyć k). Później iteracja k=29znajdzie oba, ale 20,21,29 wcześniej 7,24,25 (kolejność rośnie b, a następnie a). Dlatego zamiast zachować wszystkie znalezione pary dla najnowszych k, dołączamy je do poprzednich i stabilnie deduplikujemy. Takie postępowanie zapewnia, że ​​kolejność jest taka sama dla każdego wejścia n.

Powyższe gwarantuje, że każdy prymitywny potrójny pitagorejczyk w końcu pojawi się i pojawi się tylko raz. W przypadku danych wejściowych npętla kkończy się, gdy nuzyskano przynajmniej ważne trzykrotności; a następnie n-ty potrójny jest wyjściem.

Wypróbuj online!

Lub użyj tego zmodyfikowanego kodu, aby zobaczyć pierwsze ntrzykrotnie:

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

Wypróbuj online!

Haskell , 98 bajtów

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)

Wypróbuj online!

Jak to działa

To interpretuje dwuskładnikowe 3-cyfrowe cyfry n jako ścieżkę w dół drzewa pierwotnych triad pitagorejskich . Działa bez wyszukiwania w operacjach O (log n ).

Galaretka , 19 18 bajtów

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

Program przyjmuje indeks 1 n i drukuje pierwsze n PPT [c, b, a] w kolejności leksykograficznej.

Jest to rozwiązanie O (64 ⁿ ) , więc TIO będzie dławić się na wejściach 4 i wyższych. Popracuję nad tym, aby było to szybsze.

Wypróbuj online!

Alternatywna wersja, O (n ³ ), prawdopodobnie ważna

Aby znaleźć n- ^tą tryplet - [c _n , b _n , a _n ] - powyższe rozwiązanie zakłada, że c _n ≤ 4 ⁿ , co jest łatwe do zweryfikowania. Jednak A020882 dowodzi, że c _n ~ 2πn , więc istnieje k takie, że c _n ≤ kn dla wszystkich n .

Jeśli możemy przyjąć k = 7 , poniższe rozwiązanie jest również poprawne (i znacznie, znacznie szybsze).

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

Wypróbuj online!

Jak to działa

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 bajtów

Wysyła N-ty PPT. Wyniki są indeksowane 1 i uporządkowane według wartości 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)

Próbny

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 bajty

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

Wypróbuj online!

Lekcja gry w golfa poszła bardzo źle. W każdym razie publikuję to, ponieważ zastanawiam się, czy istnieją sposoby na grę w golfa lepiej.

Oparłem to na tej stronie Wikipedii w połączeniu ze wzorem Euclida, aby konstruktywnie wygenerować wszystkie potrójne, a nie metody prób i błędów.

Po pierwsze, nieparzyste pary coprime są generowane jako drzewo trójskładnikowe. Odbywa się to przez mnożenie dużej macierzy, co odpowiada większości bajtów. Następnie stosuje się wzór Euklidesa, być może również w sposób bardzo marnotrawczy. Jeśli ktoś ma wskazówki dotyczące tych dwóch części, chciałbym je usłyszeć.

Zauważ, że aby zapisać bajty, program ten generuje drzewo o tej samej głębokości co dane wejściowe, a nie log3(n). Ponadto dzieci są generowane dla każdego wiersza, a nie tylko dla ostatniego wiersza drzewa, a następnie ponownie filtrowane za pomocą Xu. Tyle o efektywnym, konstruktywnym podejściu.

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 bajtów

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

Indeksowanie na podstawie 0. Na dany c, bbiegnie aż do ci amaksymalnie b, więc c > b > azawsze trzyma.

Wypróbuj online!

Python, 67 50 48 46 bajtów

Używając formuł znalezionych na wikipedii,

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

gdzie m>n>0i mi nsą pierwszymi i nieparzystymi. Oto kod

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

-17 bajtów dzięki @Martin Ender

Wypróbuj online

Działa, zawsze mając wartość nzmiennej w równaniu równą 1, co oznacza, że mjest to po prostu każda inna nieparzysta wartość, w tym przypadku, 3+2*ngdzie njest liczba pierwotnej potrójnej pitagorejskiej potrójnej wartości. To pozwala nam przyjąć wartość 1 dla wszystkich nwartości.

Łuska , 18 bajtów

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

Wypróbuj online!

-4 bajty dzięki Zgarbowi, z inspiracją Dennisa

Super powolne podejście brutalnej siły, nie będzie działać na TIO dla danych wejściowych większych niż 1. Możesz wypróbować bardziej łatwą do zarządzania wersję, ograniczoną do a, b ≤ 200 tutaj

Wyjaśnienie

↑ü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 bajtów

za pomocą Solve uporządkowanego przez 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 bajty

(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 (+ cyfry), 88 bajtów

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

Aby użyć wbudowanego do wygenerowania liczb, potrzeba naprawdę zaskakującej ilości bajtów, aby uzyskać to, czego chcemy. Polecenie wbudowane pobiera dwa argumenty c1i c2, i zwraca te, które mają trojaczki c >= c1 & c <= c2. To sprawia, że ​​nieco denerwujące jest dotarcie do n-tego trypletu. To będzie po prostu zwiększać c21 na raz, aż wynik będzie wystarczającą ilością wierszy.

PHP , 273 bajtów

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) zwraca tablicę [a, b, c] z uporządkowaniem a < b < c
• Zwraca indeks zerowy

Wypróbuj online! (tam też kod jest czytelny)

C, 158 bajtów

Wierzę, że to moje pierwsze zgłoszenie tutaj, więc najprawdopodobniej możesz zrobić lepiej.

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

I wersja bez golfa:

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

Na się ² + b ² = c ² , kolejność wzrasta C , a następnie zwiększa .

Galaretka , 27 25 bajtów

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

Jest to implementacja podejścia drzewiastego z odpowiedzi Haskell @ AndersKaseorga , z inną kolejnością rozgałęzień. Program korzysta z indeksowania opartego na 0 i pobiera dane wejściowe ze STDIN.

Wypróbuj online!

tło

Jak wspomniano na stronie Wikipedii Drzewo prymitywnych trójek pitagorejskich , każdy PPT można uzyskać poprzez wielokrotne lewe mnożenie wektora wiersza (3, 4, 5) przez macierze o określonych właściwościach.

W każdej iteracji poprzedni wynik można pomnożyć w lewo przez A , B lub C , które można wybrać w następujący sposób.

Kiedy A , B i C są ustalone, każdy PPT można uzyskać w unikalny sposób.

Jak to działa

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 znaków, 180 bajtów

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

jeśli argumentem powyższej funkcji jest ⍵, powyższa funkcja zwróci element indeksu ⍵ (oparty na 1) tablicy ma elementy triagów pitagorejskich (a, b, c), gdzie a = b <= c i ta tablica jest najpierw rzędu a, (strona krótsza), a następnie b (druga strona nie jest przeciwprostokątna). Byłoby coś nie tak, ponieważ nie widać, gdzie zamawiam też b ... 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  

jest związany z http://oeis.org/A020884 i http://oeis.org/A020884/b020884.txt

A020884: Zamówione krótkie nogi prymitywnych trójkątów pitagorejskich.

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

Nie wiem, czy to prawda, wydaje się, że funkcja daje poprawny wynik pierwszej strony trójkąta do 1000, ale nie wiem do końca, i możliwe, że może być potrójne, a nawet <1000.

JavaScript, 101 bajtów

Według wzoru Euclida wszystkie prymitywne tróje pitagorejskie można wygenerować z liczb całkowitych mi za npomocą m>n>0, m+nnieparzyste gcd(m,n)==1( Wikipedia )

Ta funkcja wylicza wszystkie m,npary zwiększające m, zaczynając od m=2i zmniejszając no 2, zaczynając od m-1(więc to m+njest nieparzyste)

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

Mniej golfa

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

Test

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