5
$\begingroup$

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.

  • 4
    Check out the references in http://oeis.org/A0034182011-01-19

1 Answers 1

11

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)$.