19
1
Problem A3 from the 2008 Putnam competition says:
Start with a finite sequence \$a_1, a_2, \dots, a_n\$ of positive integers. If possible, choose two indices \$j < k\$ such that \$a_j\$ does not divide \$a_k\$, and replace \$a_j\$ and \$a_k\$ by \$\gcd(a_j, a_k)\$ and \$\text{lcm}(a_j, a_k)\$, respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made.
Your goal in this challenge is to take a finite sequence of positive integers as input, and output the result of repeating this process until no further progress is possible. (That is, until every number in the resulting sequence divides all the numbers that come after it.) You don't need to solve the Putnam problem.
This is code-golf: the shortest solution in every programming language wins.
Test cases
[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]
9What a neat problem! Write each integer $a_i$ as $\displaystyle 2^{\alpha_i} 3^{\beta_i} 5^{\gamma_i} \cdots$ and note that the process simply bubble-sorts the lists $\alpha, \beta, \gamma, \dots$ in parallel :) – Lynn – 2018-11-02T02:57:18.753