Repeat this GCD operation

Question

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]

• lynn: 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 :)

Answer 1

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 = 273056 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 2

Pari/GP, 33 bytes

Calculate the elementary divisors of the diagonal matrix.

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

Try it online!

Answer 3

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

• FrownyFrog: An earlier one is here

Answer 4

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!

• Misha Lavrov: Very nice! You're two for two on weird approaches I didn't see coming :)

Answer 5

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

Answer 6

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.

• Dennis: Unary is allowed by default for Retina, so you can count this as 52 bytes.
• Neil: @Dennis Only three of my Retina answers take input in unary; I've got used to doing I/O in decimal.

Answer 7

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)

---

Old answer:

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.

Answer 8

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.

Answer 9

Perl 6, 53 bytes

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

Try it online!

Port of alephalpha's Mathematica answer.

Answer 10

05AB1E, (削除) 15 (削除ここまで) (削除) 14 (削除ここまで) 13 bytes

Ó3⁄4ζ€{øε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 @Emigna.

Try it online or verify all test cases.

Explanation:

Ó # Prime exponents of the (implicit) input-list
 3⁄4ζ # 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)

• Mr. Xcoder: 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)
• Emigna: Using εgÅpymP would save another byte over the one Mr. Xcoder metioned
• Kevin Cruijssen: @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. :)