Is maximizing an LCM equivalent to minimizing a GCD

algorithmsgcd-and-lcmleast-common-multiplenumber theoryprogramming

I'm working on a programming problem here: https://codeforces.com/problemset/problem/235/A

Find an algorithm to solve the question:

Given $1\leq n\leq 10^6,$ return the largest value of $\operatorname{lcm}(a,b,c)$ where $a,b,c$ are integers between $1$ and $n$ inclusive.

It is not a live competition, and I have already read a solution to it, but I would like to know whether my approach works. Also, although the problem is programming, I thought that the actual solution was inherently math, so it was more reasonable to post it here, rather than, say, stackoverflow.

After doing some research, I learned that the inequality

$$\gcd(a_{1}, a_{2}, \ldots, a_{n}) \cdot \text{lcm}(a_{1}, a_{2}, \ldots, a_{n}) \leq \prod_{i=1}^{n}a_{i}$$

holds. So this motivated me to write the following algorithm:

  • Iterate $G = \text{gcd}(a_{1}, a_{2}, \ldots, a_{n})$ from $1$ to $n$. These are the only possible values that $G$ can take.

  • For every $G$, choose three numbers that are the largest multiples of $G$. For example, if $G = 2$ and $n = 9$, then we would choose $8, 6, 2$.

  • Compute the lcm for that gcd. This is a maximal value of the LCM for that gcd.

Is my approach correct?

Thanks

Best Answer

The first key is:

Theorem 1: If $a_1,\cdots,a_k$ are positive integers which are pair-wise relatively prime (that is, $\gcd(a_i,a_j)=1$ when $i\neq j$) we have that $$\operatorname{lcm}(a_1,\dots,a_k)=\prod_{i=1}^{k}a_i$$

The second key is:

Theorem 2: if $a_1,\cdots,a_k$ are positive integers then there are pair-wise relatively prime integers $a_1',\dots,a_k'$ with $1\leq a_i'\leq a_i$ for all $i$ and $$\prod_{i=1}^{n}a_i'=\operatorname{lcm}(a_1',\dots,a_k')=\operatorname{lcm}(a_1,\dots,a_k)$$ (You can actually get $a_i'\mid a_i.$)

So the set of least common multiples of $k$ numbers from $1$ to $n$ is the same as the set of products of $k$ pairwise relatively prime numbers from $1$ to $n.$

Then, in order to find the maximum LCM, we need to find the maximum product of three pairwise relatively prime numbers numbers.

When $n$ is odd, $n,n-1,$ and $n-2$ are pairwise relatively prime, so we get a least common multipe of $n(n-1)(n-2)$ which is the maximum product of three numbers from $1$ to $n,$, at least if $n>2.$

When $n$ is even, but not divisible by $3,$ then $n,n-1$ and $n-3$ are pairwise relatively prime. This is because the only product of three different numbers from $1$ to $n$ is $n(n-1)(n-2),$ but $n$ and $n-2$ are not relatively prime when $n$ is even.

When $n$ is even and divisible by $3$, then we have that $n-1$ is odd, so $(n-1)(n-2)(n-3)$ is a lest common multiple. On the other hand, any other product of three pairwise relatively prime integers with $n$ involved is at most $n(n-1)(n-5).$ But $n(n-5)<(n-2)(n-3)$ so $n(n-1)(n-5)<(n-1)(n-2)(n-3).$ So when $n$ is divisible by $6,$ the maximal value is $(n-1)(n-2)(n-3).$

You have to take care when $n\leq 2.$ In those cases, multiple values can be equal to $1.$ . When $n=2,$ you have a maximal LCM is $2.$ When $n=1,$ the maximum LCM is $1.$

Example of theorem 2: If $a_1=12,a_2=45,a_3=30,$ then we have:

$$a_1=2^23^15^0\\a_2=2^03^25^1\\a_3=2^13^15^1,$$ then we can take:

$$a_1'=2^2\\a_2'=3^2\\a_3'=5^1.$$ The $a_i'$ are pairwise relatively prime and the LCM is the product which is $2^23^25^1=180,$ and this is the least common multiple of the original triple $12,45,30.$

Related Question