Kodeclik Blog

# How to check for multiples of 3 in Python

How do you test if a number is divisible by 3? In math we are taught that we must sum all the digits of the number and if the sum is divisible by 3, then the original number is also divisible by 3. For instance, given the number 27, the sum of its digits is 2+7=9. 9 is divisible by 3; therefore 27 is divisible by 3.

In Python we have many ways to check if a given number is divisible by 3. Let us count the ways!

## Modulo Operation

The simplest and most straightforward method is using the modulo operation:

```
def is_divisible_by_3(n):
return n % 3 == 0
```

In this function we directly compute the remainder when the number is divided by 3, using the % operator, and if the remainder is zero, we return True, else False.

## Digit Sum Method

Another interesting method is based on implementing the divisibility rule for 3:

```
def is_divisible_by_3(n):
digit_sum = sum(int(digit) for digit in str(abs(n)))
return digit_sum % 3 == 0
```

The above Python function first converts the absolute value of the input number n to a string using str(abs(n)), which allows it to handle both positive and negative integers. The function then iterates through each character (digit) in this string, converting each back to an integer, and calculates the sum of all these digits using a generator expression within the sum() function. This sum is stored in the variable digit_sum. Finally, the function checks if digit_sum is itself divisible by 3 using the modulo operator (%).

## Recursive Digit Sum

For very large numbers, we can use a recursive approach:

```
def is_divisible_by_3(n):
if n < 10:
return n in (0, 3, 6, 9)
return is_divisible_by_3(sum(int(digit)
for digit in str(abs(n))))
```

This method repeatedly sums the digits until we get a single-digit number, which is then checked for divisibility by 3. For single-digit numbers (n < 10), it directly checks if n is 0, 3, 6, or 9. For larger numbers, it calculates the sum of the digits of the absolute value of n and recursively calls itself with this sum. The function continues this process until it reaches a single-digit number, effectively implementing the digit sum method for divisibility by 3.

## Bitwise Operation

For a more efficient method with large numbers, we can use bitwise operations:

```
def is_divisible_by_3(n):
return (n & 3) == 0 if n & 1 == 0 else ((n >> 1) & 3) == 0
```

This method exploits properties of binary numbers divisible by 3. It exploits the property that for even numbers, divisibility by 3 is equivalent to divisibility of n/4 by 3, while for odd numbers, it's equivalent to divisibility of (n-1)/2 by 3. The function uses bitwise AND (&) and right shift (>>) operations to efficiently perform these checks without actual division.

Each of the above methods has its advantages depending on the specific use case and the size of the numbers being tested.

## Finding all multiples of 3 from 1 to 100

Here is a very simple program to find all multiples of 3 from 1 to 100:

```
def is_divisible_by_3(n):
return n % 3 == 0
multiples_of_3 = [i for i in range(1, 101) if is_divisible_by_3(i)]
print(multiples_of_3)
```

This code defines the is_divisible_by_3 function, which uses the modulo operator to check if a number is divisible by 3. Then, it uses a list comprehension to create a list of all numbers from 1 to 100 that are divisible by 3. Finally, it prints the result.

The output of this code will be:

```
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45,
48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90,
93, 96, 99]
```

This list contains all the multiples of 3 from 1 to 100, as expected. The largest multiple of 3 less than or equal to 100 is 99, which is included in the list.

## Generalizing to find multiples of any number

Of course it is very easy to update the above code to find all multiples of a different number, say 5, from a different range, say 1 to 1000.

```
def find_multiples(x, y):
return [i for i in range(1, y + 1) if i % x == 0]
# Example usage
multiples_of_3 = find_multiples(3, 100)
print(multiples_of_3)
multiples_of_5 = find_multiples(5, 100)
print(multiples_of_5)
```

This function, find_multiples, takes two arguments: x (the number to find multiples of) and y (the upper limit of the range to search). It uses a list comprehension to create a list of all numbers from 1 to y (inclusive) that are divisible by x. The modulo operator (%) is used to check divisibility, where i % x == 0 means i is divisible by x without a remainder. When called with arguments 3 and 100, it efficiently generates a list of all multiples of 3 from 1 to 100.

This function is versatile and can be used to find multiples of any number within any specified range, making it useful for various mathematical and programming tasks, like we have done above in the bottom portion of the program, i.e., finding all multiples of 5 from 1 to 100.

The output will be:

```
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36,
39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72,
75, 78, 81, 84, 87, 90, 93, 96, 99]
[5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65,
70, 75, 80, 85, 90, 95, 100]
```

## Finding all multiples of 3 or 5 in Python

What if we needed to find all multiples of 3 or 5 in Python from 1 to 100? That should be simple, right? We just combine the above two lists! Well, not so fast. We need to make sure we do not double count numbers like 15, 30, etc.

Note that this is not the same as finding multiples of 15. We still would like to retain multiples like 6, 9, etc. We just dont want to double count multiples. How do we do that?

To find all multiples of 3 or 5 from 1 to 100 without double counting, we can update the code using the find_multiples() function as follows:

```
def find_multiples(numbers, y):
multiples = set()
for number in numbers:
multiples.update(i for i in range(1, y + 1) if i % number == 0)
return sorted(multiples)
numbers = [3, 5]
y = 100
unique_multiples = find_multiples(numbers, y)
print(unique_multiples)
```

This solution elegantly solves the problem of finding multiples of 3 or 5 without double counting. The find_multiples() function takes a list of numbers and an upper limit y as arguments. It uses a set to store the multiples, which automatically eliminates duplicates. The function iterates through each number in the input list, adding its multiples to the set. Finally, it returns a sorted list of unique multiples. When we run this code with numbers = [3, 5] and y = 100, it produces a list of all multiples of 3 or 5 up to 100, including numbers like 6 and 9, while avoiding double counting of common multiples like 15 and 30.

The output will be:

```
[3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30,
33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60,
63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90,
93, 95, 96, 99, 100]
```

In summary, we have seen four different ways of checking for divisibility by 3 and then used that function to analyze a large set of numbers. Have fun extending this program to satisfy other use cases!

Want to learn Python with us? Sign up for 1:1 or small group classes.