On the additive complexity of GCD and LCM matrices
Sergey Borisovich Gashkov, Igor' Sergeevich Sergeev · Mathematical Notes · 2016
In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the n × n matrix formed by the numbers GCD r (i, k) over the basis {x + y} is asymptotically equal to rn log2 n as n→∞, and the complexity of the n × n matrix formed by the numbers LCM r (i, k) over the basis {x + y,−x} is asymptotically equal to 2rn log2 n as n→∞.