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
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.$
No comments:
Post a Comment