# Is there a general function to derive the minimum number which can be divided by 1, 2, 3, 4 …?

1 can be divided by 1

2 can be divided by 1, 2

6 can be divided by 1, 2, 3

12 can be divided by 1, 2, 3, 4

60 can be divided by 1, 2, 3, 4, 5

60 can be divided by 1, 2, 3, 4, 5, 6

420 can be divided by 1, 2, 3, 4, 5, 6, 7

840 can be divided by 1, 2, 3, 4, 5, 6, 7, 8

I just wonder whether there is a general function to derive this number.

Thanks.

-
Check out the references in oeis.org/A003418 – Peter Taylor Jan 19 '11 at 10:31
@Peter Taylor, Thank you. This link is helpful. – user6023 Jan 19 '11 at 10:38

The question rephrased:

How does one determine $m_k$, the smallest number which is divisible by all the positive integers from 1 to $k$?

## As a product of primes

Well, if one starts with the product $\tilde m_k = 1 \cdot 2 \cdot \dots \cdot k$, this is divisble by $1, 2, \dots, k$, but it's not the smallest. For example $1 \cdot 2 \cdot 3 \cdot 4 = 24$, but the smallest is 12, since 4 is divisble by 2. If we remove the 2 we get the smallest number. This suggest a general procedure.

Take all the prime numbers $p_1, \dots, p_l$ from $\{1, 2, \dots, k\}$ and let $q_i$ be the largest integer such that $p_i^{q_i} \leq k$ and set

$$m_k = p_1^{q_1} p_2^{q_2} \cdots p_l^{q_l}$$

which should be the smallest number which is divisble by $1, \dots, k$.

## Recursively

Calculate $m_k$, let $m_{k-1}$ be given.

• Is $m_{k-1}$ divisble by $k$? If so, set $m_k = m_{k-1}$.
• Otherwise, set $m_k = \operatorname{lcm}(m_{k-1}, k)$, where $\operatorname{lcm}$ is the least common multiple.

This gives a nice implementation for computer using the following formula:

$$\operatorname{lcm}(a,b) = \frac{|a b|}{\operatorname{gcd}(a,b)}$$

## Least common multiple

Of course, you can just set:

$$m_k = \operatorname{lcm}(2, 3, \dots, k)$$.

-
I think the second answer is what I want. Thanks. – user6023 Jan 19 '11 at 10:41
You're welcome. :) – Calle Jan 19 '11 at 10:45