( связанный )

Тройка Пифагора - это список, (a, b, c)который удовлетворяет уравнению a ² + b ² = c ² .

Примитивный Пифагор Тройной (ППТ) является одним где a, bи cявляются все взаимно простым (т.е. единственным общий делитель между тремя элементами 1). Например, (3, 4, 5)правый треугольник - это знаменитая примитивная пифагорейская тройка.

Соревнование

• Учитывая ввод n, nвыводим PPT. Или,
• Учитывая ввод n, выведите первые nPPT.

Существует несколько способов упорядочить эти PPT, чтобы сформировать упорядоченный список, чтобы определить, какой именно n. Вы можете выбрать любой порядок, который захотите, при условии, что вы можете доказать (неофициально это хорошо), что ваш алгоритм может генерировать все возможные уникальные PPT. Например, ваш код не должен выводить оба, (3,4,5)и, (4,3,5)поскольку они являются дубликатами одной и той же тройки - одной или другой, пожалуйста.

Точно так же, независимо от того, является ли ваш код нулевым или индексируемым, это нормально, если вы указываете, какой код используете.

Примеры

Для приведенных ниже примеров я использую одноиндексирование, вывод nth-го PPT и упорядочение по наименьшему c, затем наименьшему a, а затем наименьшему b.

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

правила

• Ввод и вывод может быть дан в любом удобном формате .
• В своем представлении, пожалуйста, укажите, как упорядочены ваши записи, а также, проиндексированы ли они 0 или 1.
• Выбранный вами заказ не может создавать дубликаты.
• Допустимы либо полная программа, либо функция. Если функция, вы можете вернуть вывод, а не распечатать его.
• Если возможно, укажите ссылку на среду онлайн-тестирования, чтобы другие люди могли опробовать ваш код!
• Стандартные лазейки запрещены.
• Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).

Желе , 27 25 байт

2 байта благодаря Джонатану Аллану.

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

Попробуйте онлайн!

Выводит первые n1-индексированные тройки [b, a, c], отсортированные по возрастанию, bа затем a.

Использует алгоритм из Википедии :

Это генерирует все примитивные тройки для всех уникальных взаимно простых пар нечетных целых чисел m > n > 0.

объяснение

+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 байт

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

Вход основан на 1. Порядок вывода гарантирует, что каждая тройка появляется ровно один раз. Порядок объясняется следующим. Объяснение требует немного углубиться в то, как работает программа.

Код продолжает увеличивать счетчик kв цикле, начиная с 1. Для каждого kон генерирует все пары с a = 1,...,k, b = 1,...,k, a < b, и выбирает те , которые дают пифагореец с тройным c <= k. Пары получаются в порядке возрастания b, а затем a.

Затем каждая пара делится на свой gcd. Результирующие (возможно, дублированные) пары расположены в виде матрицы из двух столбцов. Эта матрица вертикально соединена с аналогичной матрицей, содержащей накопленные результаты, полученные для меньших значений k. Строки матрицы затем стабильно дедуплицируются. Это удаляет два типа дубликатов:

1. Пары, которые были найдены более одного раза для текущего k(например 3,4, который также возникает 6,8при делении на его gcd);

2. Пары, которые уже были найдены с меньшими k.

Фактически, каждая итерация kнаходит все пары, которые уже были найдены для предыдущих итераций. Но он может найти их в другом порядке . Например, k=25найдет тройку, 7,24,25а не 20,21,29(потому что cне может превысить k). Позже, итерация k=29найдет оба, но с 20,21,29 до 7,24,25 (порядок увеличивается b, тогда a). Вот почему вместо того, чтобы сохранять все пары, найденные для последних k, мы добавляем их к предыдущим и стабильно дедуплицируем. Это гарантирует, что порядок одинаков для любого ввода n.

Вышеуказанное гарантирует, что каждая примитивная пифагорейская тройка в конечном итоге появится, и она появится только один раз. Для ввода nцикл kзавершается, когда nполучены хотя бы действительные тройки; и тогда nтройная тройка - это выход.

Попробуйте онлайн!

Или используйте этот модифицированный код, чтобы увидеть первые nтройки:

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

Попробуйте онлайн!

Haskell , 98 байт

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)

Попробуйте онлайн!

Как это работает

Это интерпретирует биективные 3- значные цифры n как путь вниз по дереву примитивных пифагорейских троек . Он работает без поиска в O (log n ) операциях.

Желе , 19 18 байт

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

Программа берет основанный на 1 индекс n и печатает первые n PPT [c, b, a] в лексикографическом порядке.

Это решение O (64 ⁿ ) , поэтому TIO будет подавлять входы 4 и выше. Я буду работать над тем, чтобы сделать это быстрее.

Попробуйте онлайн!

Альтернативная версия, O (n ³ ), возможно, действительная

Чтобы найти n- ^й триплет - [c _n , b _n , a _n ] - в приведенном выше решении предполагается, что c _n ≤ 4 ⁿ , что легко проверить. Однако A020882 доказывает, что c _n ~ 2πn , поэтому существует такое k , что c _n ≤ kn для всех n .

Если мы можем принять k = 7 , решение, приведенное ниже, также верно (и намного, намного быстрее).

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

Попробуйте онлайн!

Как это работает

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 байт

Выводит N-ую PPT. Результаты индексируются 1 и упорядочиваются по значению 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)

демонстрация

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 байта

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

Попробуйте онлайн!

Урок игры в гольф прошел ужасно неправильно. В любом случае я публикую это, потому что мне интересно, есть ли способы поиграть в гольф лучше.

Я основал это на этой странице Википедии в сочетании с формулой Евклида, чтобы конструктивно генерировать все тройки, а не метод проб и ошибок.

Во-первых, нечетные взаимно простые пары генерируются как троичное дерево. Это делается как большое матричное умножение, учитывающее большую часть количества байтов. Затем применяется формула Евклида, возможно, также очень бесполезно. Если у кого-то есть советы по этим двум частям, я бы хотел их услышать.

Обратите внимание, что для сохранения байтов эта программа генерирует дерево той же глубины, что и вход, а не log3(n). Кроме того, дочерние элементы создаются для каждой строки, а не только для последней строки дерева, а затем снова фильтруются с помощью Xu. Вот вам и эффективный конструктивный подход.

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 байт

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

Индексирование на основе 0. Для данного c, bработает до cи aдо b, такc > b > a всегда имеет место.

Попробуйте онлайн!

Python, 67 50 48 46 байт

Используя формулы, найденные в Википедии,

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

где m>n>0и mи nвзаимно просты и нечетны. Вот код

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

-17 байт благодаря @Martin Ender

Попробуйте онлайн

Работает, всегда имея значение nпеременной в уравнении, равное 1, что означает, что это mпросто любое другое нечетное значение, в данном случае, 3+2*nгде nчисло примитивной пифагорейской тройки. Это позволяет нам принять значение 1 для всех nзначений.

Шелуха , 18 байт

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

Попробуйте онлайн!

-4 байта спасибо Згарбу, с вдохновением от Дениса

Подход с использованием супер-медленной грубой силы, не будет работать на TIO для входов больше 1. Вы можете попробовать более управляемую версию, ограниченную a, b≤200 здесь

объяснение

↑ü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 байт

с помощью Solve по заказу 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 байта

(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 (+ цифры), 88 байт

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

Для использования встроенной функции для генерации чисел требуется поразительное количество байтов, чтобы получить то, что мы хотим. Встроенный принимает два аргумента c1и c2, и возвращает те тройки, которые имеют c >= c1 & c <= c2. Это делает его немного раздражающим, чтобы добраться до 3-го nтриплета. Это будет только увеличивать c21 за раз, пока на выходе не будет достаточно строк.

PHP , 273 байта

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) возвращает массив [a, b, c] с упорядочением a < b < c
• Возвращает нулевой индекс

Попробуйте онлайн! (там тоже код читаемый)

C 158 байтов

Я считаю, что это мое первое представление здесь, так что вы, скорее всего, можете сделать лучше.

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

И негольфированная версия:

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

Для a ² + b ² = c ² упорядочение увеличивается c, затем увеличивается a .

Желе , 27 25 байт

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

Это реализация древовидного подхода из ответа Хаскелла @ AndersKaseorg , с другим порядком ветвления. Программа использует индексирование на основе 0 и получает данные от STDIN.

Попробуйте онлайн!

Задний план

Как уже упоминалось на странице Википедии Дерево примитивных пифагорейских троек , каждый PPT может быть получен путем многократного умножения влево вектора строки (3, 4, 5) на матрицы с определенными свойствами.

В каждой итерации предыдущий результат можно умножить влево на A , B или C , что можно выбрать следующим образом.

Когда А , Б и С фиксированы, каждый PPT может быть получен уникальным образом.

Как это работает

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 символов, 180 байтов

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

если аргумент вышеприведенной функции равен above, то вышеприведенная функция вернет элемент индекса based (на основе 1) массива, который содержит элементы пифагорейских троек (a, b, c), где a <= b <= c и этот массив сначала порядок для a (сторона более короткая), затем для b (другая сторона не гипотенуза). Там было бы что-то не так, потому что там не видел, где я тоже заказываю на 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  

это связано с http://oeis.org/A020884 и http://oeis.org/A020884/b020884.txt

A020884: Заказаны короткие ножки из примитивных пифагорейских треугольников.

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

Я не знаю, верно ли это, кажется, что функция дает правильный результат с первой стороны треугольника до 1000, но я не знаю, для остатка, и возможно, может быть некоторая тройка не так, даже <1000.

JavaScript, 101 байт

По формуле Евклида все примитивные пифагорейские тройки могут быть получены из целых чисел mи nс m>n>0, m+nнечетным gcd(m,n)==1( Wikipedia )

Эта функция перечисляет все m,nпары, увеличивающие m, начиная с m=2и уменьшая nна 2, начиная с m-1(так что m+nэто нечетно)

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

Меньше гольфа

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

Тест

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