What are Harshad Numbers?
A Harshad number (or Niven number) is a positive integer that is divisible by the sum of its digits. The name comes from the Sanskrit word harsha meaning "joy" — these are numbers that bring joy through their divisibility property. The term was coined by Indian mathematician D.R. Kaprekar.
For example, 18 is a Harshad number because its digit sum is 1 + 8 = 9, and 18 ÷ 9 = 2. Similarly, 21 is Harshad because 2 + 1 = 3 and 21 ÷ 3 = 7. However, 11 is not Harshad because 1 + 1 = 2 and 11 is not divisible by 2.
Distribution and Density
All single-digit numbers (1 through 9) are Harshad numbers, since every number is divisible by itself. Beyond that, approximately one in six numbers are Harshad. The first non-trivial Harshad numbers are 10, 12, 18, 20, 21, 24, 27, 30, 36, 40.
Unlike prime numbers, whose gaps grow arbitrarily large, there is no bound on the gap between consecutive Harshad numbers. However, it has been proven that there are infinitely many Harshad numbers. The natural density of Harshad numbers is 0 — they become proportionally rarer as numbers grow, though they remain infinite in count.
Multiple Harshad Numbers
A multiple Harshad number (or MHN) is a Harshad number that, when divided by its digit sum, produces another Harshad number. For example, 6804 is a multiple Harshad number: its digit sum is 6 + 8 + 0 + 4 = 18, and 6804 ÷ 18 = 378, which is itself a Harshad number (3 + 7 + 8 = 18, 378 ÷ 18 = 21). The chain continues: 21 is Harshad (digit sum 3, 21 ÷ 3 = 7).
Harshad Numbers in Different Bases
The Harshad property is base-dependent. A number that is Harshad in base 10 may not be Harshad in other bases, and vice versa. In base 10, the smallest number that is not Harshad is 11. In base 2, a number is Harshad if it is divisible by the number of 1-bits in its binary representation (its Hamming weight).
An all-Harshad number is a number that is Harshad in every base from 2 up to some limit. The number 1 is trivially all-Harshad in every base. Numbers that are Harshad in many bases simultaneously are rare and mathematically interesting.
Connection to Digital Roots
Every Harshad number's digital root provides insight into its divisibility. The digital root (repeated digit sum until a single digit) is related to modular arithmetic base 9. If a number has digital root d, then the number is congruent to d modulo 9. Harshad numbers whose digit sum equals their digital root (i.e., single-iteration digit sum) are the simplest cases.
Applications
Harshad numbers appear in checksum algorithms and error detection. Many identification numbers (credit cards, ISBNs, etc.) use digit-sum-based checks that relate to the Harshad property. In programming contests, Harshad number detection is a common exercise that tests understanding of modular arithmetic and digit manipulation.