An Application of Floor Division — Harshad Numbers

Python 2.2 introduced a new operator called floor division // to its already powerful arsenal of operators. Floor division divides two numbers and reduces the quotient to its preceding integer. While true division / divides the numbers to the fractional part precision, floor division // chips off the fractional part of the result. The important aspect of floor division is that it doesn’t round off the value to compensate the significant error.

In Python 3, the / operator is for floating-point division, and // is for integer division (i.e. quotient without remainder); whereas in Python 2, the / is simply integer division, unless one of the operands was already a floating-point number.
Study the following illustrations.

true-division-vs-floor-division-python3

true-division-vs-floor-division-python2

Floor division (aka integer division) comes handy in solving many real-world problems. It often helps us to write a very concise code for calculations involving the modulo % arithmetic. We’ll see an elementary example of floor division today — finding Harshad numbers.

Harshad Numbers

An Harshad number is any positive integer that’s divisible by the sum of its digits. For example, 24 is an Harshad number because the sum of its digits 6(2+4) divides it 4 times leaving no remainder (24/6=4); whereas 26 is not, since 26 is not divisible by 8(2+6).

Harshad numbers were defined by D. R. Kaprekar, a mathematician from India.

Harshad  numbers are also known as Niven numbers. The term “Niven number” arose from a paper delivered by Ivan M. Niven at a conference on number theory in 1977.

Notice in determining whether a number is Harshad or not, we’re ignoring the fractional part of the quotient and concern ourselves with only the integer part. That gives us a hint of potential floor division application. So let’s write a script for testing the Harshad-ness of a number entered by the user.

Grace Over

We’ll develop the logic incrementally by testing small computations in the Python interactive shell. Later we’ll integrate the individual steps into a seamless logic. The process is similar to the way a Cricket batsman and a bowler play the grace over during the beginning of the Test match to understand the nature of the pitch.

The first-half of our problem requires us to compute the sum of individual digits in the number. To do so, we first need to parse the digits in the number one after the other. Let’s take an example number 248. As we all know fetching the unit’s digit can be easily accomplished by applying modulo 10 on the number.

>>> n = 248
>>> n%10  # Returns the remainder of 248/10
8

So the unit’s digit 8 of 248 is fetched by applying modulo 10. In order to fetch the next digit 4, we should somehow turn 248 into 24 and apply the modulo 10. There are only two ways to reduce a number — subtraction or division. Subtraction reduces a number incrementally whereas division in one step. Observe 248 becoming 24, it’s a drastic reduction which hints us to use the division. Plus we’re reducing the number approximately 10 times less. Hence we should divide the number by 10. Let’s test our theory.

>>> 248/10
24.8

That’s almost right except the fractional part (.8). It should be obvious by now that we should use the floor division in this scenario.

>>> 248//10   # 248 reduces to 24
24

Perfect. Now modulo 10 on 24 to get the second number 4.

>>> 24%10
4

Finally we’ll fetch the last digit 2 by reducing 24 to 2 (floor division by 10) and applying modulo 10 on 2.

>>> 24//10  # reducing 24 to 2
2
>>> 2%10    # fetching the unit's digit
2

We’re done fetching all the three digits of 248, and finally we’re left with 2. If we again do the floor division by 10 on 2, we’ll get zero.

>>> 2//10
0

In other words, following from the unit’s place of the number, when the floor division of the digit of the number results in zero, then we’ll have fetched all the digits of the number. And we should terminate the loop. That’s it.

Now in order compute the sum of digits fetched during each iteration, we need an accumulator that holds the sum of digits. So the logic to compute the sum of digits of 248 is,

>>> n = 248
>>> sum = 0
>>> while(n>0):
	sum += n%10  # Fetch the unit's digit and add it to sum
	n = n//10    # Reduce the number by 10 times

>>> sum   # After the loop, sum now has 8+4+2
14

 

We’re done with the first-half of calculating the sum of digits of the number. The second-half is just testing whether number is divisible by the sum of digits calculated in the first-half. To do so we should have stored the number in some temporary variable, since the original number is reduced to zero by the time we compute the sum of its digits (and the loop terminates). We’ll test the divisibility by applying modulo sum on the number.

Final Over

We can now easily write the script that tells whether a number is Harshad or not.

n = int(input('Enter a number: '))

num = n  # saving for comparison in second-half

sum = 0  # accumulator

# First-half: compute the sum of digits
while(n>0):
    sum += n%10
    n = n//10


# Second-half: test the divisibility
if( num%sum == 0 ):
    print('{0} is an Harshad Number.'.format(num))

else:
    print('{0} is NOT an Harshad Number.'.format(num))
OUTPUT:
Enter a number: 24
24 is an Harshad Number.

============== RERUN ===============
Enter a number: 26
26 is NOT an Harshad Number.

============== RERUN ===============
Enter a number: 248
248 is NOT an Harshad Number.

============== RERUN ===============
Enter a number: 133
133 is an Harshad Number.

Floor division rocks like Virat Kohli. Is it not?!

Post-match Analysis:
Harshad Numbers
Floor and Ceiling Functions