Задача A3 из конкурса Putnam 2008 года гласит:

$a_1, a_2, \dots, a_n$$j < k$$a_j$$a_k$$a_j$$a_k$$\gcd(a_j, a_k)$$\text{lcm}(a_j, a_k)$

Ваша задача в этой задаче - взять конечную последовательность положительных целых чисел в качестве входных данных и вывести результат повторения этого процесса, пока дальнейший прогресс невозможен. (То есть до тех пор, пока каждое число в полученной последовательности не разделит все числа, следующие за ним.) Вам не нужно решать проблему Путнама.

Это код-гольф : выигрывает самое короткое решение на каждом языке программирования.

Контрольные примеры

[1, 2, 4, 8, 16, 32] => [1, 2, 4, 8, 16, 32]
[120, 24, 6, 2, 1, 1] => [1, 1, 2, 6, 24, 120]
[97, 41, 48, 12, 98, 68] => [1, 1, 2, 4, 12, 159016368]
[225, 36, 30, 1125, 36, 18, 180] => [3, 9, 18, 90, 180, 900, 4500]
[17, 17, 17, 17] => [17, 17, 17, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [1, 1, 1, 1, 1, 2, 2, 6, 60, 2520]

Желе , 9 байт

ÆEz0Ṣ€ZÆẸ

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

Как это устроено

ÆEz0Ṣ€ZÆẸ  Main link. Argument: A (array)

ÆE         For each n in A, compute the exponents of n's prime factorization.
           E.g., 2000000 = 2⁷3⁰5⁶ gets mapped to [7, 0, 6].
  z0       Zip 0; append 0's to shorter exponent arrays to pad them to the same
           length, then read the resulting matrix by columns.
    Ṣ€     Sort the resulting arrays (exponents that correspond to the same prime).
      Z    Zip; read the resulting matrix by columns, re-grouping the exponents by
           the integers they represent.
       ÆẸ  Unexponents; map the exponent arrays back to integers.

Пари / ГП , 33 байта

Вычислить элементарные делители диагональной матрицы.

a->Vecrev(matsnf(matdiagonal(a)))

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

J , 17 байт

/:~"1&.|:&.(_&q:)

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

Вероятно, первый ответ J на ​​PPCG использовать &.дважды. После этого и что , я начинаю чувствовать себя странным J хакера.

В основном перевод от Дениса Желе ответ .

Как это устроено

/:~"1&.|:&.(_&q:)  Single monadic verb.
           (_&q:)  Convert each number to prime exponents
                   (automatically zero-filled to the right)
       |:&.        Transpose
/:~"1&.            Sort each row in increasing order
       |:&.        Transpose again (inverse of transpose == transpose)
           (_&q:)  Apply inverse of prime exponents; convert back to integers

Wolfram Language (Mathematica) , 44 байта

Table[GCD@@LCM@@@#~Subsets~{i},{i,Tr[1^#]}]&

$k$$k$

$b_k = \gcd(\{\operatorname{lcm}(a_{i_1}, \cdots, a_{i_k}) | 1 \le i_1 < \cdots < i_k \le n\})$

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

Python 3 , 103 байта

import math
def f(a,i=0,j=-1):d=math.gcd(a[i],a[j]);a[j]*=a[i]//d;a[i]=d;a[i:j]and f(a,i,j-1)==f(a,i+1)

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

объяснение

Эта задача по существу является параллельной сортировкой по простым множителям, и (gcd (a, b), lcm (a, b)) аналогична (min (a, b), max (a, b)). Итак, давайте поговорим с точки зрения сортировки.

По индукции мы докажем, что после f (i, j) a [i] становится наименьшим значением в (старом значении) L, где L - диапазон между a [i] и a [j], включая оба конца , И если j = -1, f (i, j) будет сортировать диапазон L.

Случай, когда L содержит один элемент, тривиален. Для первого утверждения обратите внимание, что самый маленький из L не может оставаться в [j] после перестановки, поэтому f (i, j-1) поместит его в a [i], а f (i + 1, - 1) не повлияет на это.

Для второго утверждения обратите внимание, что a [i] является наименьшим значением, а f (i + 1, -1) будет сортировать оставшиеся значения, поэтому L сортируется после f (i, j).

Сетчатка , 65 байт

\d+
*
+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b
$2$4$5$#3*$5
_+
$.&

Попробуйте онлайн! Ссылка включает в себя более быстрые тестовые случаи. Объяснение:

\d+
*

Преобразовать в одинарный.

+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b

Повторное сопоставление: любое число с фактором, затем более позднее число, которое не делится на первое число, но делится на фактор.

$2$4$5$#3*$5

$1это первое число. $2это фактор. Поскольку регулярное выражение является жадным, это самый большой фактор, т.е. gcd. $4является частью совпадения между исходными числами. $5это второе число. $#3(в десятичной, а не в унарной форме) на единицу меньше, чем $1делится на $2, поскольку не включает в себя оригинал $2. Это означает, что для вычисления lcm нам нужно умножить $5на единицу больше, чем то, $#3которое наиболее кратко записано как сумма $5и произведение $#3и $5.

_+
$.&

Преобразовать в десятичную.

05AB1E , 10 байтов

Признание за подход идет к alephalpha .

εIæN>ù€.¿¿

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

εIæN>ù€.¿¿     Full program. Takes a list from STDIN, outputs another one to STDOUT.
ε              Execute for each element of the input, with N as the index variable.
 Iæ            Powerset of the input.
   N>ù         Only keep the elements of length N+1.
      €.¿      LCM each.
         ¿     Take the GCD of LCMs.

Perl 6 , 53 байта

{map {[gcd] map {[lcm] $_},.combinations: $^i},1..$_}

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

Порт Mathematica ответ алефальфа.

JavaScript (SpiderMonkey) , 69 байт

a=>a.map((q,i)=>a.map(l=(p,j)=>a[j]=j>i&&(t=p%q)?p/t*l(q,j,q=t):p)|q)

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

• Функция lправопреемник lcm(p,q)к a[j]и правопреемнику gcd(p, q)в qслучай j > i, иначе сохраняют все без изменений.
  • lcm(p,q) = if p%q=0 then p else p*lcm(q,p%q)/(p%q)

Старый ответ:

JavaScript (SpiderMonkey) , 73 байта

a=>a.map((u,i)=>a.map((v,j)=>i<j?a[j]*=u/(g=p=>p%u?g(u,u=p%u):u)(v):0)|u)

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

• Функция gвычисляет gcd(u, v)и присваивает возвращаемое значение u.

05AB1E , 15 14 13 байт

Ó¾ζ€{øεgÅpymP

Port of @ Dennis ♦ 'Jelly ответ , но, к сожалению, 05AB1E не имеет встроенного Unexponents, так что это занимает более половины программы .. :(
-1 байт благодаря @ Mr.Xcoder .
-1 байт благодаря @Enigma ,

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

Ó          # Prime exponents of the (implicit) input-list
 ¾ζ        # Zip, swapping rows and columns, with integer 0 as filler
   €{      # Sort each inner list
     ø     # Zip, swapping rows and columns again
ε          # Map each inner list:
 gÅp       #  Get the first `l` primes, where `l` is the size of the inner list
    ym     #  Take the power of the prime-list and inner list
      P    #  And then take the product of that result
           # (And output implicitly)