# Multiples of *N* Between *A* and *B*

A common counting problem is to determine the number of multiples of an integer *n* in a give range from *a* to *b* (inclusive) where *a* < *b*. There may be other conditions on the problem, such as counting the numbers that are multiples of both *n* AND *m*, multiples of EITHER *n* OR *m*, or multiples of *n* but NOT of *m*.

For small ranges it is easy to list them by hand, but for larger ranges it is more efficient to use a formula. Each condition scenario is analyzed below. You can also use the convenient calculator on the left to quickly count multiples and generate them as a list.

#### Case I: Multiples of *n*

To count the number of multiples of *n*between

*a*and

*b*, you need to use the floor and ceiling functions, ⌊⌋ and ⌈⌉ respectively. The the number of multiples is given by the expression

⌊b/n⌋ - ⌈a/n⌉ + 1

For example, the multiples of 4 between 0 and 24 are {0, 4, 8, 12, 16, 20, 24}. To count them more quickly without having to list them, you compute

⌊24/4⌋ - ⌈0/4⌉ + 1

= 6 - 0 + 1

= 7

#### Case II: Multiples of both *n* AND *m*

To count integers that are multiples of both *n*and

*m*, it suffices to count numbers that are multiples of the least common multiple (LCM) of

*n*and

*m*. The formula is

⌊b/y⌋ - ⌈a/y⌉ + 1

where y = LCM(n, m). For example, suppose you want to count numbers that are multiples of both 4 and 6 between 100 and 200. Since the LCM of 4 and 6 is 12, you compute

⌊200/12⌋ - ⌈100/12⌉ + 1

= 16 - 9 + 1

= 8

The exact set is {108, 120, 132, 144, 156, 168, 180, 192}.

#### Case III: Multiples of Either *n* OR *m*

To determine the number of integers that are multiples of either *n*or

*m*(or both), you calculate the multiples of just

*n*, then add the multiples of just

*m*, and subtract the mutliples of LCM(n, m). If you don't subract this quantity, the multiples of LCM(n, m) will be counted twice. The full expression is

⌊b/n⌋ - ⌈a/n⌉ + ⌊b/m⌋ - ⌈a/m⌉ - ⌊b/y⌋ + ⌈a/y⌉ + 1

where y = LCM(n, m). For instance, suppose you need to find the number of integers between 20 and 40 that are multiples of either 4 or 6. Since LCM(4, 6) = 12, the answer is

⌊40/4⌋ - ⌈20/4⌉ + ⌊40/6⌋ - ⌈20/6⌉ - ⌊40/12⌋ + ⌈20/12⌉ + 1

= 10 - 5 + 6 - 4 - 3 + 2 + 1

= 7

The exact set is {20, 24, 28, 30, 32, 36, 40}.

#### Case IV: Multiples of *n* but NOT of *m*

The number of multiples of *n*that are NOT multiples of

*m*is given by the expression

⌊b/n⌋ - ⌈a/n⌉ - ⌊b/y⌋ + ⌈a/y⌉

where y = LCM(n, m). For example how many multiples of 4 between are there between 0 and 60 that are not multiples of 6? To calculate the answer, evaluate the expression

⌊60/4⌋ - ⌈0/4⌉ - ⌊60/12⌋ + ⌈0/12⌉

= 15 - 0 - 5 + 0

= 10.

The full list is {4, 8, 16, 20, 28, 32, 40, 44, 52, 56}.

© *Had2Know 2010
*