Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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

1 Answer 1

up vote 11 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.