[Question]
  [
Problem A3 from [the 2008 Putnam competition](https://kskedlaya.org/putnam-archive/2008.pdf) 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](/questions/tagged/code-golf "show questions tagged '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]
```
  
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 bytes
```
ÆEz0Ṣ€ZÆẸ
```
[Try it online!](https://tio.run/##y0rNyan8//9wm2uVwcOdix41rYk63PZw147/R/ccbgfyFI5OerhzBpABYmeB6IY5CrZ2Co8a5ipE/v@vwaUQbaijYKSjYKKjYKGjYGimo2BsFKsDEjYyAEoAhc3A8kBVhmBxS3OgYiDPBKQcKGEJpM0swFJGRqZA7SAjgFoNDWE8Q5BKCwOIqUDdCAwRAptvDHaCKdg6c7BbLIEqQJo0AQ "Jelly – Try It Online")
### How it works
```
Æ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.
```
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 33 bytes
Calculate the [elementary divisors](https://en.wikipedia.org/wiki/Smith_normal_form) of the diagonal matrix.
```
a->Vecrev(matsnf(matdiagonal(a)))
```
[Try it online!](https://tio.run/##RY7dCoMwDIVfJXhloQVT/y/mY@xGehE2FcG54mSwp@@SwNhFSc/Jd5JEOla3xDTDBRK54TrdjumdP@h87bOU@0rLc6ctJ2NMohi3T07gBojHup/8zURkMAtgYRzRgrdQWegsYGOh9IFt9AX77DbaZgjF7ltGWVQCs99zbTrpeF9zVvIcRPwpFLArdCRn/08dnV3q9lpXtXpGz0ARgklf "Pari/GP – Try It Online")
[Answer]
# [J](http://jsoftware.com/), 17 bytes
```
/:~"1&.|:&.(_&q:)
```
[Try it online!](https://tio.run/##TU7LCsIwELz7FUMPqQWJu5s0L/BbPIhFvIi3HNRfTxdKg7DDDjPLzD7bYDEuuJQRJ3wLCIp2Lr@Bjf0UY49X8y5Tmw732@OFBQyBRwIHOOmiEMQjqMfgXc2xwrMiVb2oyLpDqrstMsNpCoF5o6yxiXpo7PNf7rR@1qqoT2QwtRU "J – Try It Online")
Probably the first J answer on PPCG to use `&.` twice. After this and [that](https://codegolf.stackexchange.com/a/174017/78410), I'm starting to feel like a weird J hacker.
Basically a translation from [Dennis' Jelly answer](https://codegolf.stackexchange.com/a/175092/78410).
### How it works
```
/:~"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
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 44 bytes
```
Table[GCD@@LCM@@@#~Subsets~{i},{i,Tr[1^#]}]&
```
The \$k\$-th element of the result is the GCD of the LCM's of the subsets with \$k\$ elements.
\$b\_k = \gcd(\{\operatorname{lcm}(a\_{i\_1}, \cdots, a\_{i\_k}) | 1 \le i\_1 < \cdots < i\_k \le n\})\$
[Try it online!](https://tio.run/##RY49C8IwEIb/ykHAKWKTfg9KoIKLgmC3EKGVFgPWoY1TSP96vATEIYR77nnvburMc5g6ox@dH2Hv265/DfLUHIU4NxchBFlvn34ZzLJa7ajVtJ0luxPl1MZfZ/02ksD2AKMkSsEGdgKsZRQ4hYxCRYEVFFLuKFjGE@RIi9hGiQVcl6hikQUZeY1/UYUO5zlmQx6DjP0qFsQqiSMx@3@RxNlp3J7HVWU8o0Yhcc5/AQ "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/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)
```
[Try it online!](https://tio.run/##RU/NDoIwDL7zFD2KVmVDEDB7ErLD4kS2RCC4i0@PXRVdsvXn@@k6vUI/DvmyuMc0zgEeJvSJvXXQbQw6laFXe5E2VkXgcL/ajWmdRtN6nV7iu1WxcTzaS4yKQ@O1GezHAj3pleJ8J9Il3J7BmmBAQZsAnVYgSIQTQoUgSoRcavwiMiOMkJIpRBQrVJ9JQo1TFBFWUyyrFZWyIJ/oRQZCrJWI5Cr72ZPH//66PCvnHxU8@sxfq4kUpTpJunEGA26AdZmGpbRjysk0uyFQsbwB "Python 3 – Try It Online")
### Explanation
This problem is essentially a parallel sort on the prime factors, and (gcd(a,b), lcm(a,b)) is analogous to (min(a,b), max(a,b)). So let's talk in terms of sorting.
We will prove by induction that after f(i,j), a[i] becomes the smallest value in (the old value of) L, where L is the range between a[i] and a[j], including both ends. And if j = -1, f(i,j) will sort the range L.
The case when L contains one element is trivial. For the first claim, notice that the smallest of L can't stay in a[j] after the swap, so f(i,j-1) will put it in a[i], and f(i+1,-1) will not affect it.
For the second claim, note that a[i] is the smallest value, and f(i+1,-1) will sort the remaining values, so L becomes sorted after f(i,j).
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 65 bytes
```
\d+
*
+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b
$2$4$5$#3*$5
_+
$.&
```
[Try it online!](https://tio.run/##NYzBCsIwDIbveQsxStuE0aTtNk8efYnC5tDDLh7E968pIoSQ/0vyvZ@f/XWXdnK3tdUHQQBa6@bcQt5V9eQtDKH366EK1a3jTgEVMxY8poAFFgIczq0JK2eeWUZOCqKRNfNoUFhAtXCyRWSR3yh2OUeQif8F3ZDMUextMtOFJX4B "Retina – Try It Online") Link includes the faster test cases. Explanation:
```
\d+
*
```
Convert to unary.
```
+`\b((_+)(\2)+)\b(.*)\b(?!\1+\b)(\2+)\b
```
Repeatedly match: any number with a factor, then a later number that is not divisible by the first number but is divisible by the factor.
```
$2$4$5$#3*$5
```
`$1` is the first number. `$2` is the factor. Because regex is greedy this is the largest factor i.e the gcd. `$4` is the part of the match between the original numbers. `$5` is the second number. `$#3` (in decimal rather than unary) is one less than `$1` divided by `$2`, since it doesn't include the original `$2`. This means that to calculate the lcm we need to multiply `$5` by one more than `$#3` which is most succintly written as the sum of `$5` and the product of `$#3` and `$5`.
```
_+
$.&
```
Convert to decimal.
[Answer]
# [JavaScript (SpiderMonkey)](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Releases/45), 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)
```
[Try it online!](https://tio.run/##bVHbToQwEH3fr@iLS8dUpNx20RSf/Aok2QZZLRYoFzcx8d9xCst6iQmlnTNnzplpK3mSQ9ErM94MRj2Xfd02b@XHdBSTFKl0a2ko7ZiCNdCCGlbZMKtyUaVqu6WjMFcdPJjb8VojuWKdGOHOwGcH0/1hk3FGfEZCRvaM8JiRwM@JSMl/OJJ9D2EE4zmLHH5hLwXxkkci0pMdKiAeWg1MJrjH@z8V4ZLjUeLxOMD0JvP9CA2tKdpxvkbcyuy9pT5AuQVKvBm2B/yFkWetOVp/r7Plb2ydPZh7iObed/O8Vtj72ebl89chY3sRkZ3y4I69qim4g9FqpM5T48D5NVK9glbLAXCPbf8oi1dKM8XKHF@qaJuh1aWr2xeqGGnFe1OepKZHOm8KACwqSoDpCw "JavaScript (SpiderMonkey) – Try It Online")
* Function `l` assign `lcm(p,q)` to `a[j]`, and assign `gcd(p, q)` to `q` if `j > i`, otherwise keeps everything unchanged.
	+ `lcm(p,q) = if p%q=0 then p else p*lcm(q,p%q)/(p%q)`
---
Old answer:
# [JavaScript (SpiderMonkey)](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Releases/45), 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)
```
[Try it online!](https://tio.run/##bVHZboMwEHzPV/ilirdyqc0VSGvy1K@gkWKlJDXlEsRIlfrvdG1KeqgSxt7Z2Zldu1SjGo697i53Q6dfir5um7fifTrJSclMebXqKDVMwzUYWYmBfix3Ki/3t9Lc07PsZNbdmN0ZqUbiCbYG6AhbDh8GpofDKheM@IyEjCSMiJiRwN8TmZH/cCT7HGEEY5dFjriy54J4ziMR6ekGFRAPrQYmU9zj5E9FOOdElHIRB5he5b4foaE1RTshlkhYmYTP9QHKzVDKHWwP@Asjbq0FWn@vL8vf2DJ74HqIXO8bN68V5j/bvH7@MmRsLyKyUx68S69rCt7QVfpC18/NGtyLVDKrFtBqrQG8U9s/qeMrpblmxR7f69g2Q1sVXtWeqWaklaYpRlXRE3WbBgCLygJg@gQ "JavaScript (SpiderMonkey) – Try It Online")
* Function `g` calculate `gcd(u, v)` and assign return value to `u`.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 10 bytes
Credit for the approach goes to [alephalpha](https://codegolf.stackexchange.com/a/175097/59487).
```
εIæN>ù€.¿¿
```
[Try it online!](https://tio.run/##yy9OTMpM/f//3FbPw8v87A7vfNS0Ru/Q/kP7//@PNjIy1VEwNgNiAx0FQ0MYz9AChA1iAQ "05AB1E – Try It 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.
```
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 53 bytes
```
{map {[gcd] map {[lcm] $_},.combinations: $^i},1..$_}
```
[Try it online!](https://tio.run/##RY5NCoNADIX3PUUWUhSCmFHHH@hJihVraxEcFe1GxLNPMymliyGT772XZH4ug7Zmg3MHF7ubZob9@mofFXy/Q2sq8OoDw3Yy935s3v00riV4t/5ACkOW7Nps0PleHUA3LSefEBRCgpAjkEaIVYBMVcScqRaZTeRwkbGVm8SZmRdcde4UpVLOujwHiX4dOWMeyUjO/p8QmR3L9lRWZXJGwYYosB8 "Perl 6 – Try It Online")
Port of alephalpha's Mathematica answer.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~15~~ ~~14~~ 13 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Ó¾ζ€{øεgÅpymP
```
Port of [*@Dennis♦*' Jelly answer](https://codegolf.stackexchange.com/a/175092/52210), but unfortunately 05AB1E doesn't have an Unexponents-builtin, so that takes more than halve the program.. :(  
-1 byte thanks to *@Mr.Xcoder*.  
-1 byte thanks to *@Emigna*.
[Try it online](https://tio.run/##yy9OTMpM/f//8ORD@85te9S0pvrwjnNb0w@3FlTmBvz/H21kZKpjbKZjbKBjaAhhGloAkUEsAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeX/w5MP7Tu37VHTmurDO85tTT/cWlCZG/C/Vud/dLShjpGOiY6FjqGZjrFRrI5CtKGRgY6RiY4ZUNxQxxAkYmmuY2KoYwJUY6RjaaFjZgESNDIy1TEG6jHQMTSEMA2BCiwMwEaY68AQmAs0yhhoiSnQUHOgVZY6hgaxsQA).
**Explanation:**
```
Ó          # 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)
```
]