Problem A3 z konkursu Putnam 2008 mówi:

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

Twoim celem w tym wyzwaniu jest przyjęcie skończonej sekwencji dodatnich liczb całkowitych jako danych wejściowych i wygenerowanie wyniku powtarzania tego procesu, dopóki dalszy postęp nie będzie możliwy. (To znaczy, dopóki każda liczba w wynikowej sekwencji nie podzieli wszystkich liczb, które występują po niej.) Nie musisz rozwiązywać problemu Putnam.

To jest golf golfowy : wygrywa najkrótsze rozwiązanie w każdym języku programowania.

Przypadki testowe

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

Galaretka , 9 bajtów

ÆEz0Ṣ€ZÆẸ

Wypróbuj online!

Jak to działa

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

Pari / GP , 33 bajty

Oblicz elementarne dzielniki macierzy diagonalnej.

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

Wypróbuj online!

J , 17 bajtów

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

Wypróbuj online!

Prawdopodobnie pierwsza odpowiedź J na PPCG została użyta &.dwukrotnie. Po tym i tamtym zaczynam czuć się jak dziwny haker J.

Zasadniczo tłumaczenie z odpowiedzi Jelly'ego na galaretkę .

Jak to działa

/:~"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 bajty

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

$k$ -tego elementu wyniku jest GCD LCM-tych podgrupach z $k$ elementów.

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

Wypróbuj online!

Python 3 , 103 bajty

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)

Wypróbuj online!

Wyjaśnienie

Ten problem jest zasadniczo równoległym sortowaniem czynników pierwszych i (gcd (a, b), lcm (a, b)) jest analogiczny do (min (a, b), max (a, b)). Porozmawiajmy więc o sortowaniu.

Udowodnimy przez indukcję, że po f (i, j) a [i] staje się najmniejszą wartością w (starej wartości) L, gdzie L jest zakresem między [i] a [j], obejmującym oba końce . A jeśli j = -1, f (i, j) posortuje zakres L.

Przypadek, w którym L zawiera jeden element, jest trywialny. W przypadku pierwszego zastrzeżenia zwróć uwagę, że najmniejszy z L nie może pozostać w [j] po zamianie, więc f (i, j-1) umieści go w [i], i f (i + 1, - 1) nie wpłynie na to.

W drugim zastrzeżeniu należy zauważyć, że [i] jest najmniejszą wartością, a f (i + 1, -1) posortuje pozostałe wartości, więc L zostanie posortowane po f (i, j).

Siatkówka , 65 bajtów

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

Wypróbuj online! Link zawiera szybsze przypadki testowe. Wyjaśnienie:

\d+
*

Konwertuj na unary.

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

Wielokrotne dopasowanie: dowolna liczba ze współczynnikiem, a następnie późniejsza liczba, która nie jest podzielna przez pierwszą liczbę, ale jest podzielna przez współczynnik.

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

$1jest pierwszą liczbą. $2jest czynnikiem. Ponieważ wyrażenie regularne jest zachłanne, jest to największy czynnik, tj. Gcd. $4jest częścią dopasowania oryginalnych liczb. $5jest drugą liczbą. $#3(w liczbach dziesiętnych zamiast jednostkowych) jest o jeden mniej niż $1podzielony $2, ponieważ nie zawiera oryginału $2. Oznacza to, że aby obliczyć lcm, musimy pomnożyć $5przez jeden więcej, niż $#3to, co jest najlepiej zapisane jako suma $5i iloczyn $#3i $5.

_+
$.&

Konwertuj na dziesiętny.

05AB1E , 10 bajtów

Uznanie za podejście należy do alephalpha .

εIæN>ù€.¿¿

Wypróbuj online!

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

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

Wypróbuj online!

Odpowiedź Mathematiki na port Aphalphy.

JavaScript (SpiderMonkey) , 69 bajtów

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)

Wypróbuj online!

• Funkcja lprzypisuje lcm(p,q)do a[j]i przypisuje gcd(p, q)do qif j > i, w przeciwnym razie wszystko pozostanie niezmienione.
  • lcm(p,q) = if p%q=0 then p else p*lcm(q,p%q)/(p%q)

Stara odpowiedź:

JavaScript (SpiderMonkey) , 73 bajty

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)

Wypróbuj online!

• Funkcja goblicza gcd(u, v)i przypisuje wartość zwracaną do u.

05AB1E , 15 14 13 bajtów

Ó¾ζ€{øεgÅpymP

Port z @ Dennis ♦ 'Galaretka odpowiedź , ale niestety 05AB1E nie ma wbudowanego Unexonents, więc zajmuje to ponad połowę programu .. :(
-1 bajt dzięki @ Mr.Xcoder .
-1 bajt dzięki @Enigma .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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