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]

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

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!

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.

Answer 7

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 8

Perl 6, 53 bytes

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

Try it online!

Port of alephalpha's Mathematica answer.

Answer 9

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 10

05AB1E, 15 14 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.

Try it online or verify all test cases.

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)