El problema A3 de la competencia Putnam 2008 dice:

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

Su objetivo en este desafío es tomar una secuencia finita de enteros positivos como entrada y generar el resultado de repetir este proceso hasta que no sea posible ningún progreso adicional. (Es decir, hasta que cada número en la secuencia resultante divida todos los números que le siguen). No necesita resolver el problema de Putnam.

Esto es code-golf : gana la solución más corta en cada lenguaje de programación.

Casos de prueba

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

Jalea , 9 bytes

ÆEz0Ṣ€ZÆẸ

Pruébalo en línea!

Cómo funciona

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

Calcular los divisores elementales de la matriz diagonal.

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

Pruébalo en línea!

J , 17 bytes

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

Pruébalo en línea!

Probablemente la primera respuesta J en PPCG para usar &.dos veces. Después de esto y aquello , empiezo a sentirme como un extraño hacker de J.

Básicamente una traducción de la respuesta de Dennis 'Jelly .

Cómo funciona

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

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

El -ésimo elemento del resultado es el MCD de los LCM de los subconjuntos con elementos.$k$$k$

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

Pruébalo en línea!

Python 3 , 103 bytes

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)

Pruébalo en línea!

Explicación

Este problema es esencialmente una clasificación paralela de los factores primos, y (mcd (a, b), mcm (a, b)) es análogo a (min (a, b), max (a, b)). Entonces hablemos en términos de clasificación.

Demostraremos por inducción que después de f (i, j), a [i] se convierte en el valor más pequeño en (el valor anterior de) L, donde L es el rango entre a [i] y a [j], incluidos ambos extremos . Y si j = -1, f (i, j) ordenará el rango L.

El caso cuando L contiene un elemento es trivial. Para el primer reclamo, observe que el más pequeño de L no puede permanecer en un [j] después del intercambio, por lo que f (i, j-1) lo colocará en un [i], yf (i + 1, - 1) no lo afectará.

Para la segunda afirmación, tenga en cuenta que a [i] es el valor más pequeño y f (i + 1, -1) clasificará los valores restantes, por lo que L se ordena después de f (i, j).

Retina , 65 bytes

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

Pruébalo en línea! El enlace incluye los casos de prueba más rápidos. Explicación:

\d+
*

Convierte a unario.

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

Emparejar repetidamente: cualquier número con un factor, luego un número posterior que no es divisible por el primer número pero es divisible por el factor.

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

$1Es el primer número. $2es el factor Debido a que la expresión regular es codiciosa, este es el factor más importante, es decir, el mcd. $4es la parte de la coincidencia entre los números originales. $5Es el segundo número. $#3(en decimal en lugar de unario) es uno menos que $1dividido por $2, ya que no incluye el original $2. Esto significa que para calcular el mcm necesitamos multiplicar $5por uno más de lo $#3que se escribe más sucintamente como la suma de $5y el producto de $#3y $5.

_+
$.&

Convierte a decimal.

05AB1E , 10 bytes

El crédito por el enfoque va a alephalpha .

εIæN>ù€.¿¿

Pruébalo en línea!

ε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 bytes

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

Pruébalo en línea!

Port of alephalpha's Mathematica answer.

JavaScript (SpiderMonkey) , 69 bytes

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)

Pruébalo en línea!

• La función lasignar lcm(p,q)a a[j], y asignar gcd(p, q)a qsi j > i, de lo contrario mantiene todo sin cambios.
  • lcm(p,q) = if p%q=0 then p else p*lcm(q,p%q)/(p%q)

Vieja respuesta:

JavaScript (SpiderMonkey) , 73 bytes

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)

Pruébalo en línea!

• Función gcalcular gcd(u, v)y asignar valor de retorno a u.

05AB1E , 15 14 13 bytes

Ó¾ζ€{øεgÅpymP

Puerto de @ Dennis ♦ 'Respuesta de Jelly , pero desafortunadamente 05AB1E no tiene un componente de Unexponents, por lo que toma más de la mitad del programa ... :(
-1 byte gracias a @ Mr.Xcoder .
-1 byte gracias a @Enigma .

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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