This is proof of why answer < 3.

Suppose, we have 3 elements x, y, z, with gcd(x, y, z) != 1. Then, after first transformation array will contain elements: gcd(x, y), gcd(x, z), gcd(y, z), Let's call them a = gcd(x, y), b = gcd(x, z), c = gcd(y, z). After second tranformation array will contain elements: gcd(a, b), gcd(a, c), gcd(b, c), we can notice, that:
gcd(a, b) = gcd(gcd(x, y), gcd(x, z)) = gcd(x, y, x, z) = gcd(x, y, z). Doing similar things with gcd(a, c) and gcd(b, c), it turns out, that gcd(a, b) = gcd(a, c) = gcd(b, c) = gcd(x, y, z). That means, that after 2nd transformation array will contain 3 equal numbers greater than 1. I think it's obvious, that answer will be infinity, if array contains 3 equal numbers greater than 1.


Now, if gcd of any tripple of numbers equals one, that means, that we will end in less than 2 transformations (Proof this by yourself)

Edited by author 22.01.2022 15:49