Algorithm for Computing the LCM

The applet below illustrates an algorithm for finding the Least Common Multiple (LCM) of a number of integers.

Let there be a finite sequence of positive integers X = (x₁, x₂, ..., x_n), n > 1. The algorithm proceeds in steps as follows: on each step m it examines and updates the sequence X^(m) = (x₁^(m), x₂^(m), ..., x_n^(m)), X⁽¹⁾ = X. The purpose of the examination is to pick the least (perhaps, one of many) element of the sequence X^(m). Assuming x_k₀^(m) is the selected element, the sequence X^(m+1) is defined as

	x_k^(m+1)	= x_k^(m),	k ≠ k₀
	x_k₀^(m+1)	= x_k₀^(m) + x_k₀.

In other words, the least element is increased by the corresponding x whereas the rest of the elements pass from X^(m) to X^(m+1) unchanged.

The algorithm stops when all elements in sequence X^(m) are equal. Their common value L is exactly LCM(X).

(In the applet the numbers x₁, x₂, ..., x_n that appear at the top row are modifiable by clicking left or right off their vertical center line. Press button Compute to see the algorithm running. The blue numbers the ones that have been modified at one of the steps.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

Discussion

Let M^k = max x_i^(k). There are only finitely many k such that M^k ≤ L. Let m be the largest such index. I.e., we assume that M^m ≤ L whereas M^m+1 > L provided the algorithm does not stop at step m. This assumption leads to a contradiction.

Indeed, by a suitable re-numbering, we will then have

	X^(m)	= (r·x₁, x₂^(m), ..., x_n^(m)) and
	X^(m+1)	= ((r+1)·x₁, x₂^(m), ..., x_n^(m)),

with r a positive integer and

L ≠ r·x₁ ≤ x₂^(m) ≤ ... ≤ x_n^(m) = M^m ≤ L

Now (r+l)·x₁ ≤ L would imply that M^m+1 ≤ L which could not be, by the maximality of m. Hence

r·x₁ < L < (r+1)·x₁.

But this contradicts the fact that L is a multiple of x₁. Hence the assumption that m is not the last step is false and

X^(m)

= (M^m, M^m, ..., M^m).

But then M^m is a common multiple of all the x_i, i = 1, 2, ..., n, and L ≥ M^m, at that. However, since L is the least common multiple, L ≤ M^m. Hence

L = M^m

and

X^(m)

= (L, L, ..., L),

as required.

Remark

This algorithm could be used to simulate a multitasking environment. In fact it was so used in the early days of computing. Assume, for example, you write a program which shows several balls bouncing up and down and off the walls. A task is associated with each ball that regularly updates its position and velocity. All balls must be continuously controlled, i.e. all the associated tasks need to be executed on a rotating basis. In addition, some balls may have to be updated more frequently than others.

The solution is this: each task k is assigned the (reversed) relative frequency x_k and the LCM algorithm is run. One step of task k is executed whenever x_k^(m) is updated. The above discussion shows that all tasks will be updated with the required frequencies.

Reference

A. J. Goldman; N. J. Fine, El655, The American Mathematical Monthly, Vol. 71, No. 9. (Nov., 1964), pp. 1045-1046.

34220362

Amazon.com Widgets