5 Best Ways to Check if Product of First n Natural Numbers is Divisible by Their Sum in Python

Rate this post
Checking Divisibility of Natural Numbers’ Product by Their Sum in Python

πŸ’‘ Problem Formulation: You’re tasked with determining whether the product of the first n natural numbers (also known as the factorial of n) is divisible by the sum of these numbers. For instance, if n = 4, the factorial 4! equals 24, and the sum of the first four natural numbers is 10. You want a Python function that checks if 24 % 10 == 0.

Method 1: Iterative Approach

For the iterative approach, we define a function that calculates both the sum and the product of the first n natural numbers using a loop. Once we have both values, we use the modulo operator to check if the product is divisible by the sum.

Here’s an example:

def is_divisible_sum_product(n):
    total_sum = 0
    total_product = 1
    for i in range(1, n+1):
        total_sum += i
        total_product *= i
    return total_product % total_sum == 0

print(is_divisible_sum_product(4))

Output: False

This code snippet defines a function is_divisible_sum_product() that iterates from 1 to n, accumulating the sum and product of these numbers. At the end of the loop, it checks the divisibility using the modulo operator and returns the boolean result.

Method 2: Mathematics Shortcut

This method takes advantage of the mathematical property that a number n factorial (n!) is never divisible by n for any n greater than 2. We’ll use a simple mathematical check to avoid unnecessary calculations.

Here’s an example:

def is_divisible_shortcut(n):
    return False if n > 2 else True

print(is_divisible_shortcut(4))

Output: False

In this example, the function is_divisible_shortcut() immediately returns False if n is greater than 2. This takes advantage of the known mathematical fact and provides a simple, efficient check for divisibility in this particular case.

Method 3: Functional Programming Approach

By employing Python’s functional programming tools such as reduce() and sum(), we can elegantly express the solution on a single line. This is a more Pythonic way, utilizing built-in high-order functions.

Here’s an example:

from functools import reduce
from operator import mul

def is_divisible_functional(n):
    numbers = range(1, n+1)
    product = reduce(mul, numbers)
    total_sum = sum(numbers)
    return product % total_sum == 0

print(is_divisible_functional(4))

Output: False

The is_divisible_functional() function creates a range for the natural numbers, then uses the reduce() function with the multiplication operator to find the product. It calculates the sum with sum() and finally checks for divisibility.

Method 4: Using Factorial and Sum Formulas

Instead of calculating the sum and product through an iterative process, we can use direct mathematical formulas — the factorial of n and the sum of an arithmetic series. This approach reduces complexity by avoiding loops.

Here’s an example:

import math

def is_divisible_formula(n):
    product = math.factorial(n)
    total_sum = n * (n + 1) // 2
    return product % total_sum == 0

print(is_divisible_formula(4))

Output: False

The function is_divisible_formula() uses Python’s math.factorial() to compute the factorial of n. It then calculates the sum with the arithmetic series sum formula and checks for divisibility.

Bonus One-Liner Method 5: Compact Lambda Expression

For those who prefer concise Python expressions, lambda functions provide a way to write the entire operation in a single line. This approach is a compact version of the functional approach.

Here’s an example:

from functools import reduce
from operator import mul

is_divisible = lambda n: reduce(mul, range(1, n+1)) % sum(range(1, n+1)) == 0

print(is_divisible(4))

Output: False

This one-liner consists of a lambda function is_divisible, which computes the factorial with reduce(), calculates the sum with sum(), and then performs the divisibility check, all in a single expression.

Summary/Discussion

  • Method 1: Iterative Approach. Simple to understand. Time-consuming for large n due to the loop.
  • Method 2: Mathematics Shortcut. Extremely fast. Limited to the mathematical property that only applies for n greater than 2.
  • Method 3: Functional Programming Approach. Pythonic and concise. May be less readable to those unfamiliar with functional programming.
  • Method 4: Using Factorial and Sum Formulas. Efficient for large n. Requires knowledge of the math module.
  • Method 5: Compact Lambda Expression. One-liner elegance. Readability might suffer for those not versed in lambda functions.