# Repeat this GCD operation

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

• What 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 Nov 2 '18 at 2:57

# Jelly, 9 bytes

ÆEz0Ṣ€ZÆẸ


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.


# Pari/GP, 33 bytes

Calculate the elementary divisors of the diagonal matrix.

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


Try it online!

# J, 17 bytes

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


Try it online!

Probably the first J answer on PPCG to use &. twice. After this and that, I'm starting to feel like a weird J hacker.

Basically a translation from Dennis' Jelly answer.

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

• An earlier one is here – FrownyFrog Nov 2 '18 at 9:47

# Wolfram Language (Mathematica), 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!

• Very nice! You're two for two on weird approaches I didn't see coming :) – Misha Lavrov Nov 2 '18 at 5:14

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


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

# Retina, 65 bytes

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


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. • Unary is allowed by default for Retina, so you can count this as 52 bytes. – Dennis Nov 2 '18 at 0:53 • @Dennis Only three of my Retina answers take input in unary; I've got used to doing I/O in decimal. – Neil Nov 2 '18 at 9:40 # 05AB1E, 10 bytes Credit for the approach goes to alephalpha. εIæN>ù€.¿¿  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.  # Perl 6, 53 bytes {map {[gcd] map {[lcm]$_},.combinations: $^i},1..$_}


Try it online!

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


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)

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


Try it online!

• Function g calculate gcd(u, v) and assign return value to u.

# 05AB1E, 1514 13 bytes

Ó¾ζ€{øεgÅpymP


Port of @Dennis♦' Jelly answer, 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 @Enigma.

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)

• Oh, I hadn't seen your answer prior to posting my own, lol. 14 bytes by using ¾ and removing 0ï, +1. (I've tried this before because I tried to port Dennis' answer as well lol) – Mr. Xcoder Nov 2 '18 at 8:18
• Using εgÅpymP would save another byte over the one Mr. Xcoder metioned – Emigna Nov 2 '18 at 8:28
• @Mr.Xcoder Oh, didn't knew there was a difference between the filler with 0 and ¾. Need to remember that! In fact, I will add it to my small 05AB1E tips right now. :) – Kevin Cruijssen Nov 2 '18 at 10:00