The Minimum LCM of a sequence

Here, I would like to discuss the problem of minimizing the LCM of a sequence of $k$ distinct integers given their exact sum to be $n$ . This value I will denote as $LK (N )$ . I will establish a lower and an upper bound on this value for any $n,k ∈ ℕ$ . The lower bound, as you will see, is extremely simple to establish; a far more complex problem is establishing an upper bound.

Consider the following problem, listed in the shortlist for IMO 2022, as an example of where this function has been used.

This problem is equivalent to calculating the exact value of $L3(2022)$ , it is specifically this problem, which convinced me to generalize the concept.

2 Lower Bound

Here, I will prove that the lower bound on the value of $Lk(n)$ is $n∕ (1+ 1 + ...+ 1) 1 2 k$ , along with the fact that this bound is tight.

Proof. Let us assume the opposite, that indeed, $L (n) < n∕(1-+ 1 +...+ 1) k 1 2 k$ , then let $L (n)∕a < L (n )∕a < ...< L (n )∕a k 1 k 2 k k$ be the $k$ divisors of $L (n) k$ (meaning, the $k$ divisors, which sum to $n$ , from the definition), then we conclude, that,

∑k ( )
n = Lk(n)= Lk (n) -1 + 1-+ ...+ 1-
i=1 ai a1 a2 ak
------n------ (-1 1- -1)
< 1 + 1+ ...+ 1 a1 + a2 + ...+ ak
1 2 k

(1)

However, as one can probably already see, $-1 + 1-+ ...+ 1-≤ 1 + 1+ 1 + ...+ -1 a1 a2 ak 1 2 3 k$ , however even if this sum equals its maximum possible value the last expression will only be $n$ , thus it is impossible for there to be a strict less sign in the inequality, contradiction. Thus, the inequality is indeed true. ■

Notice that the lower bound on $Lk(n)$ gives something more interesting. Obviously one can see that from this, one can conclude that,

is true for any $a1,...,ak ∈ ℕ$ , assuming that for no two $ai,aj$ we have $ai = aj$ . As a small example of the two equations, we get the following nice simple tricks, (given, that $a ⁄= b$ )

3 Upper Bound

3.1 $L2(N )$ Analysis

Proof. Let us assume this is not the case, then it must hold, that, the partition of $n$ was into two parts $xd$ and $yd$ , where $x,y > 1$ , and $d$ is the greatest common denominator of the two numbers in the partition (consequently $(x,y) = 1$ ). Notice, that $[xd,yd] = d[x,y]$ , however, due to $(x,y) = 1$ , one can conclude that $[x,y] = xy$ , thus $[xd,yd] = xyd$ . However, notice, that $xy$ is minimized, when $x = 2$ and $y = n - 2 d$ , but notice that even then,

( ) n- dxy = 2d d - 2 = 2(n- d)

(5)

However, notice, that, if one considers the partition where $x = 1$ and $n y = d - 1$ , then the least common multiple will be the following,

(n ) dxy = d d-- 1 = n- d

(6)

Which is better, than than $2(n - d)$ , consequently, it is always benificial to make the partition of the form $d,dx$ , thus, to minimize the least common denominator, the value of $dx$ , must be minimized, in other words the value of $nd - 1$ must be minimized, however this problem is equivelent to maximizing $d$ (note, that the maximized value of $d$ is represented as $r$ in the statement). However, to simplify the statement, notice that maximizing $d$ means minimizing $nd$ , however $nd ≥ 3$ must hold, for the partitioning to be legal (e.i. the numbers would be distinct), consequently, one sees, that if $q$ is the smallest divisor, such that $q ≥ 3$ , the value of $L2(N )$ is exactly $(q- 1)r$ . ■

Notice, that trivially (through simply considering the partitioning $1,n - 1$ ), $L2(N )$ is at least bounded by $N - 1$ , however through this theorem, we understand that this bound is tight for prime values of $N$ , thus proving, that indeed, the upper bound $N - 1$ is tight.

While this does indeed already tell us a lot, the function is bounded by two linear functions, consequently $L2(N ) = O (N )$ , however this does not tell the full story, the question that I will raise in this section, will be to find a function $L^2 (N )$ , such that,

In simple terms, a nice approximation of $L2(N)$ in the form of a linear function, $^L2(N )$ . To start the analysis, I will perform a common trick, notice, that $L2(N )$ from the previous theorem is a very hard function to work with, consequently to eliminate any drastic changes in the value of the function, I propose analysing the value of the following,

Notice, that the problem of identifing the smallest divisor greater than 2, is not extremely different from identifying the smallest prime divisor, this is due to the fact, that the smallest divisor greater than 2, must be part of the set ${4,3,5,7,...}$ (in other words, the union of ${4}$ and the set of primes, greater than 2) let π_n represent the probability that the n-th special number is the minimal divisor greater than 2, then, indeed, a recursive relationship holds (where s_n is the n-th special number),

First of all, quick note, from this, one can conclude, that, π_n ≤ -1
sn

, which has as a direct biproduct,

Now, I shall return to the definition of $AL2 (N )$ , to get, (where, $d(k)$ represents the smallest divisor, which is greater than 2 of $k$ )

The expectation is just a convienient way to rephrase the previous, assuming that the random variable $k$ is uniformly selected from $1$ to $N$ . Thus, I propose analysing that value,

One of the methods here, is to immediately write the last expression using the prime zeta function,

However, I have found this result to not be precise enough, this is due to the rough approximation we make, for the value of $πk$ , it far from accurate, I am referencing this specific moment in logic,

If one accounts for this error (I have not figured out a way here, to get a nice formula to simplify the last, thus I have simply calculated this with a computer),

Thus, we have come to quite an accurate formula for $AL2 (N )$ , which is $AL2 (N) ≈ 0.405N$ , let the constant be $c$ , then, one can conclude, the following,

3.2 $L3(N )$ Case-wise Analysis

Consider the simplest and most elementary situation where $k = 3$ . Now let one consider three situation for different possible congruences $mod 3$ .

Thus, indeed, one has established an upper bound on the value of $L3(N )$ to be $2N-- 3$ . It is important to note this bound is strict only for $N$ large enough so that the above examples work (the exact number after which the bound starts working will be discussed a bit later). One can see the established lower and upper bound for the values of $L3(N )$ ,

However, this somewhat brute-force approach does not work for larger values of $N$ , in fact already just to find an upper bound for $L4(N )$ posses a harder problem than before. Thus, calculating an upper bound for higher values of $K$ requires a different perspective. In fact it seems the linear upper bound for $L4(N )$ while close, is not as tight as it was for $L3(N )$ .

I want to note, that the value of $L3 (N )$ is already to a large extend analysed, one already knows from the previous theorems, that $6N-≤ L3(N ) ≤ 2N 11 3$ (whilst, the upper bound is proven is a non-insightful fashion, it does not deminish the fact, that the bound is proven).

3.3 Remarks on $LK(N )$

I cannot say much, about the completely generalized concept, except for the fact, that this problem is quite fundamental, if one thinks about it closer. Again, let us take a closer look at how can one interpret the value of $L2(N )$ . Let us interpret all partitions of 2-partitions of $N$ , then one can easily come to see, that this is nothing more, than all the lattice points of a line $y = - x+ N$ , thus if $F2(N) ≥ L2(N )$ , this means, that for any line $y = - x + N$ , there exists a lattice point, which is less or equal to $F2(N )$ , this interpretation can be easily generalized for larger dimensions.

MrMineev