Harshad number
A Harshad number, also known as a Niven number, is a positive integer that is divisible by the sum of its own digits when written in base 10.[1] The term "Harshad" originates from Sanskrit, combining harṣa (joy) and da (giver), meaning "giver of joy," reflecting its recreational mathematical appeal.[2] The concept was introduced by the Indian mathematician Dattatreya Ramchandra Kaprekar in 1955, who also referred to such numbers as "multidigital numbers" in his work on recreational mathematics.[1] Independently, the name "Niven number" was coined in 1980 by mathematicians Robert E. Kennedy, Thomas Goodman, and Curtis Best, honoring the Canadian-American number theorist Ivan Niven for his contributions to the field.[1] Harshad numbers form an infinite sequence beginning with 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, and continuing indefinitely, cataloged in the Online Encyclopedia of Integer Sequences as A005349.[2] These numbers have been studied for their distribution and properties in number theory; for instance, they have asymptotic density zero among all positive integers, meaning the proportion of Harshad numbers up to a large N approaches zero as N grows.[1] Notable results include the fact that no more than 20 consecutive positive integers can all be Harshad numbers, with the longest known such sequence having 44,363,342,786 digits.[1] Generalizations extend to other bases, where an n-Harshad number is divisible by the sum of its digits in base n ≥ 2, and "all-Harshad" numbers—those satisfying the condition in every base ≥ 2—are limited to just 1, 2, 4, and 6.[1]Definition and History
Definition
A Harshad number in base b \geq 2, also known as a b-Niven number, is a positive integer n that is divisible by the sum of its digits in base b. Formally, n is a Harshad number if s_b(n) divides n, where s_b(n) denotes the sum of the base-b digits of n. This condition is equivalently expressed as n \equiv 0 \pmod{s_b(n)}.[3] In the conventional base 10, the definition simplifies to n being divisible by the sum of its decimal digits s(n). The digit sum function s_b(n) is computed by expressing n as n = \sum_{k=0}^m d_k b^k with digits $0 \leq d_k < b, and then taking s_b(n) = \sum_{k=0}^m d_k. While iteratively applying s_b to the result yields the digital root of n (a value between 1 and b-1, congruent to n modulo b-1), the Harshad property concerns only the initial digit sum.[3][1] Although 0 has a digit sum of 0 and is sometimes considered trivially Harshad, it is typically excluded from the definition, as Harshad numbers focus on positive integers to avoid division by zero. The divisibility requirement is also stated as n / s_b(n) being an integer.[1][4]History and Etymology
The concept of Harshad numbers was first introduced by the Indian mathematician Dattatreya Ramchandra Kaprekar in 1955, under the name "multidigital numbers," in his exploration of intriguing properties of natural numbers.[1][2] Kaprekar, a prominent figure in recreational mathematics, coined the term "Harshad" from the Sanskrit roots harṣa (joy) and da (giver), literally meaning "joy-giver," reflecting his fascination with numbers that exhibit delightful divisibility patterns.[5][2] In 1980, the alternative name "Niven numbers" emerged in a paper by Robert E. Kennedy, Terry A. Goodman, and Clarence H. Best, honoring the Canadian-American mathematician Ivan M. Niven for his 1977 conference presentation at the annual Miami University Number Theory Conference, where he discussed problems involving numbers divisible by their digit sums.[1][2] Kaprekar's contributions, rooted in his broader investigations of number curiosities such as digit rearrangements and self-generating sequences, laid the groundwork for these numbers to transition from recreational puzzles to subjects of formal analysis in number theory.[5]Examples and Properties
Examples
All single-digit positive integers from 1 to 9 are Harshad numbers in base 10, as each equals the sum of its own digits and is thus divisible by that sum.[2] The sequence of such numbers continues with 10, 12, 18, 20, 21, 24, 27, 30, and many more.[1] To illustrate, consider 18: the sum of its digits is $1 + 8 = 9, and $18 \div 9 = 2, an integer.[2] Similarly, for 24, the digit sum is $2 + 4 = 6, and $24 \div 6 = 4.[2] A more complex example is 162, where $1 + 6 + 2 = 9 and $162 \div 9 = 18.[2] By contrast, 11 is not a Harshad number, since $1 + 1 = 2 and $11 \div 2 = 5.5, which is not an integer. Notably, the calendar years 2022 through 2025 are all Harshad numbers. For 2022, $2 + 0 + 2 + 2 = 6 and $2022 \div 6 = 337; for 2023, $2 + 0 + 2 + 3 = 7 and $2023 \div 7 = 289; for 2024, $2 + 0 + 2 + 4 = 8 and $2024 \div 8 = 253; and for 2025, $2 + 0 + 2 + 5 = 9 and $2025 \div 9 = 225.[2][6]Properties
All single-digit positive integers from 1 to 9 are Harshad numbers, as the sum of their digits equals the number itself, which trivially divides it.[1] Similarly, all powers of 10 (i.e., $10^k for positive integers k) are Harshad numbers in base 10, since their decimal representation consists of a 1 followed by k zeros, yielding a digit sum of 1, and 1 divides any integer.[7] The set of Harshad numbers is closed under multiplication by 1 (trivially, as it leaves numbers unchanged), but not generally under addition or multiplication. For instance, 10 and 12 are both Harshad numbers, but their sum 22 has digit sum 4 and $22 \div 4 = 5.5, which is not an integer. Likewise, 8 and 12 are Harshad numbers, but their product 96 has digit sum 15 and $96 \div 15 = 6.4, which is not an integer.[1] If n is a Harshad number and m is a multiple of n such that the digit sum of m equals the digit sum of n, then m is also a Harshad number. This follows from the definition, as s(n) \mid n and n \mid m imply s(n) \mid m, and since s(m) = s(n), it holds that s(m) \mid m. Without preservation of the digit sum, m may or may not be Harshad.[1] A fundamental property linking Harshad numbers to modular arithmetic is their consistency with base-10 congruences modulo 9. For any positive integer n, the sum of its digits satisfies s(n) \equiv n \pmod{9}. If n is Harshad, then n = q \cdot s(n) for some integer q, so substituting the congruence gives n \equiv q \cdot n \pmod{9}, or n(1 - q) \equiv 0 \pmod{9}. This relation is always satisfied for Harshad numbers, confirming the tautological consistency with digital root properties (where the digital root is n \pmod{9}, adjusted to 1–9). Thus, no number can be Harshad unless n \equiv s(n) \pmod{9}, a condition that holds universally but underscores the definitional constraint for divisibility.Harshad Numbers in Other Bases
Generalization to Other Bases
The concept of a Harshad number extends naturally to arbitrary integer bases b \geq 2. In base b, a positive integer n is called a b-Harshad number (or simply a Harshad number in base b) if n is divisible by the sum of its digits in the base-b representation, denoted s_b(n). This condition is equivalent to n \equiv 0 \pmod{s_b(n)}. For a d-digit number n in base b, the digit sum satisfies $1 \leq s_b(n) \leq d(b-1), since each digit is an integer between 0 and b-1, with the leading digit at least 1. In particular, powers of the base, such as b^k for k \geq 0, are always Harshad numbers in base b, as their representation consists of a 1 followed by k zeros, yielding s_b(b^k) = 1, which divides any integer. For instance, consider the decimal number 18, which is Harshad in base 10 ($18_{10}, digit sum $1+8=9, and $18/9=2). In base 12, however, 18 is represented as $16_{12} (since $1 \times 12 + 6 = 18), with digit sum $1+6=7, and 7 does not divide 18. This illustrates how the Harshad property is base-dependent.Properties in Different Bases
In any integer base b > 1, the powers of the base, b^k for k \geq 0, are Harshad numbers because their representation consists of the digit 1 followed by k zeros, yielding a digit sum of 1, by which any integer is divisible. This holds trivially for all bases, including prime and composite ones, and contributes to the infinite supply of Harshad numbers in each base. For composite bases, the structure of b-1 influences the abundance of Harshad numbers, as any number n whose digit sum s_b(n) divides b-1 is automatically Harshad. This follows from the congruence n \equiv s_b(n) \pmod{b-1}, which implies s_b(n) divides n when s_b(n) divides b-1. Bases where b-1 has many divisors thus admit more such numbers; for instance, in base 12 (b-1 = 11, prime, with divisors 1 and 11), the constraint is stricter than in base 10 (b-1 = 9, divisors 1, 3, 9), though empirical counts show similar densities around 9%. Harshad primes in base b are restricted to the single-digit primes (those less than b), as any multi-digit prime p > b cannot be Harshad. For p to be divisible by s_b(p) > 1, s_b(p) would need to equal p, impossible for multi-digit representations where s_b(p) < p; alternatively, s_b(p) = 1 implies p = b^k for k \geq 2, which is composite. The digit sum s_b(n) satisfies the bound s_b(n) \leq (b-1)(\lfloor \log_b n \rfloor + 1) < b \log_b n + b, which limits the possible divisors for Harshad numbers and underscores their relative scarcity for large n. This bound affects divisibility conditions, ensuring s_b(n) remains sublinear in n. In base 2 specifically, Harshad numbers are those where the population count (number of 1-bits) divides n; while powers of 2 satisfy this with population count 1, others exist, such as 6 (binary 110, sum 2, $6/2 = 3). Overall, densities of Harshad numbers tend to be higher in bases where b-1 has more divisors, facilitating more frequent satisfaction of the divisibility criterion.Consecutive Harshad Numbers
Maximal Runs of Consecutive Harshad Numbers
A run of consecutive Harshad numbers consists of integers m, m+1, \dots, m+k-1 such that each i in this range satisfies i \equiv 0 \pmod{s(i)}, where s(i) denotes the sum of the digits of i in base 10.[8] Early searches identified short runs, such as the length-2 sequence from 2 to 3, where both numbers are divisible by their digit sums of 2 and 3, respectively. Longer runs are constrained by the slow growth of digit sums relative to the numbers themselves, limiting the possible length of such sequences.[8] The maximal length of a run of consecutive Harshad numbers in base 10 is 20. Cooper and Kennedy (1993) proved that no sequence of 21 or more consecutive integers can all be Harshad numbers, relying on modular arithmetic constraints: in any 21 consecutive integers, their residues modulo certain values derived from possible digit sums force at least one non-divisibility. They also demonstrated that runs of exactly 20 occur infinitely often via general constructions.[8] The smallest known explicit run of 20 consecutive Harshad numbers begins at a number with 44,363,342,786 digits (Grundman, 1994).[1] Computational verifications up to $10^{18} have confirmed no runs exceeding length 20.[8]Runs of Exactly n Consecutive Harshad Numbers
A run of exactly n consecutive Harshad numbers consists of n successive positive integers, each divisible by the sum of its digits in base 10, such that neither the integer immediately preceding the run nor the one following it is Harshad. These runs are of interest because they highlight the sporadic clustering of Harshad numbers, with the smallest such runs providing benchmarks for their distribution. The sequence of the smallest starting points for these runs, denoted a(n), is cataloged in OEIS A060159.[9] For small n, these starting points are relatively modest, but they grow rapidly as n increases, reflecting the increasing rarity of long exact runs. The following table lists the smallest starting points for n from 1 to 10, along with representative examples of the runs:| n | Starting point a(n) | Example run |
|---|---|---|
| 1 | 12 | 12 |
| 2 | 20 | 20, 21 |
| 3 | 110 | 110, 111, 112 |
| 4 | 510 | 510 to 513 |
| 5 | 131052 | 131052 to 131056 |
| 6 | 12751220 | 12751220 to 12751225 |
| 7 | 10000095 | 10000095 to 10000101 |
| 8 | 2162049150 | 2162049150 to 2162049157 |
| 9 | 124324220 | 124324220 to 124324228 |
| 10 | 1 | 1 to 10 |