Harshad number

A Harshad number, or Niven number in a given number base, is an integer that is divisible by the sum of its digits when written in that base. Harshad numbers were defined by D. R. Kaprekar, a mathematician from India. The word "Harshad" comes from the Sanskrit harṣa (joy) + da (give), meaning joy-giver. The Niven numbers take their name from Ivan M. Niven from a paper delivered at a conference on number theory in 1977. All integers between zero and n are Harshad numbers in base n.

Stated mathematically, let X be a positive integer with m digits when written in base n, and let the digits be a_i (i = 0, 1, ..., m − 1). (It follows that a_i must be either zero or a positive integer up to n − 1.) X can be expressed as

$X=\sum_{i=0}^{m-1} a_i n^i.$

If there exists an integer A such that the following holds, then X is a Harshad number in base n:

$X=A\sum_{i=0}^{m-1} a_i.$

Harshad numbers in base 10 form the sequence:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, 45, 48, 50, 54, 60, 63, 70, 72, 80, 81, 84, 90, 100, 102, 108, 110, 111, 112, 114, 117, 120, 126, 132, 133, 135, 140, 144, 150, 152, 153, 156, 162, 171, 180, 190, 192, 195, 198, 200, 201, ... (sequence A005349 in OEIS)

A number which is a Harshad number in any number base is called an all-Harshad number, or an all-Niven number. There are only four all-Harshad numbers: 1, 2, 4, and 6.

What numbers can be Harshad numbers?

Given the divisibility test for 9, one might be tempted to generalize that all numbers divisible by 9 are also Harshad numbers. But for the purpose of determining the Harshadness of n, the digits of n can only be added up once and n must be divisible by that sum; otherwise, it is not a Harshad number. For example, 99 is not a Harshad number, since 9 + 9 = 18, and 99 is not divisible by 18.

The base number (and furthermore, its powers) will always be a Harshad number in its own base, since it will be represented as "10" and 1 + 0 = 1.

For a prime number to also be a Harshad number it must be less than or equal to the base number. Otherwise, the digits of the prime will add up to a number that is more than 1 but less than the prime and, obviously, it will not be divisible. For example: 11 is not Harshad in base 10 because the sum of its digits "11" is 1+1=2 and 11 is not divisible by 2, while in hexadecimal the number 11 may be represented as "B", the sum of whose digits is also B and clearly B is divisible by B, ergo it is Harshad in base 16.

Although the sequence of factorials starts with Harshad numbers in base 10, not all factorials are Harshad numbers. 432! is the first that is not.

Consecutive Harshad numbers

Cooper and Kennedy proved in 1993 that no 21 consecutive integers are all Harshad numbers in base 10 but there are infinitely many consecutive sequences of length 20. They also constructed infinitely many 20-tuples of consecutive integers that are all Harshad numbers, smallest of which exceed 10^44363342786.

The integers starting run of exactly n consecutive integers that are all Harshad numbers (i.e., smallest x such that x, x+1, ..., x+n-1 are Harshad numbers but x-1 and x+n are not) for n = 1,2,... are:

12, 20, 110, 510, 131052, 12751220, 10000095, 2162049150, 124324220, 1, 920067411130599, ... (sequence A060159 in OEIS)

H.G. Grundman extended the Cooper and Kennedy result to show that there are 2b but not 2b+1 consecutive Harshad numbers in base b.

In binary, there are infinitely many sequences of four consecutive Harshad numbers; in ternary, there are infinitely many sequences of six consecutive Harshad numbers. Both of these facts were proven by T. Cai in 1996. More generally, there are exist infinitely many 2n-tuples of consecutive Harshad numbers in base n as proved by Wilson in 1997.

In general, such maximal sequences run from N · b^k - b to N · b^k + (b-1), where b is the base, k is a relatively large power, and N is a constant. Interpolating zeroes into N will not change the sequence of digital sums, so it is possible to convert any solution into a larger one by interpolating a suitable number of zeroes, just as 21 and 201 and 2001 are all Harshad numbers base 10. Thus any solution implies an infinite class of solutions.

Estimating the density of Harshad numbers

If we let N(x) denote the number of Harshad numbers ≤ x, then for any given ε > 0,

$x^{1-\varepsilon} \ll N(x) \ll \frac{x\log\log x}{\log x}$

as shown by Jean-Marie De Koninck and Nicolas Doyon; furthermore, De Koninck, Doyon and Kátai proved that

$N(x)=(c+o(1))\frac{x}{\log x}$

where c = (14/27) log 10 ≈ 1.1939.

Nivenmorphic numbers

A Nivenmorphic number or Harshadmorphic number for a given number base is an integer t such that there exists some Harshad number N whose digit sum is t, and t, written in that base, terminates N written in the same base.

For example, 18 is a Nivenmorphic number for base 10:

 16218 is a Harshad number
 16218 has 18 as digit sum
    18 terminates 16218

Sandro Boscaro determined that for base 10 all positive integers are Nivenmorphic numbers except 11.

Multiple Harshad numbers

Bloem (2005) defines a multiple Harshad number as a Harshad number that, when divided by the sum of its digits, produces another Harshad number. He states that 6804 is "MHN-3" on the grounds that

$\begin{array}{l} 6804/18=378\\ 378/18=21\\ 21/3=7 \end{array}$

and went on to show that 2016502858579884466176 is MHN-12. The number 10080000000000 = 1008·10¹⁰, which is smaller, is also MHN-12. In general, 1008·10ⁿ is MHN-(n+2).

References

• E. Bloem 2005/2006. Harshad numbers. Journal of Recreational Mathematics, 34(2): 128
• Jean-Marie De Koninck and Nicolas Doyon, On the number of Niven numbers up to x, Fibonacci Quarterly Volume 41.5 (November 2003), 431–440
• Jean-Marie De Koninck, Nicolas Doyon and I. Katái, On the counting function for the Niven numbers, Acta Arithmetica 106 (2003), 265–275
• Sandro Boscaro, Nivenmorphic Integers, Journal of Recreational Mathematics 28, 3 (1996 - 1997): 201–205
• Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. ISBN 1-4020-2546-7. Zbl 1079.11001. 

External links

• Harshad Numbers
• Numbers of Harshad