Harshad number

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

A Harshad number, or Niven number, is an integer that is divisible by the sum of its digits in a given number base. The Niven numbers take their name from Ivan M. Niven from a paper delivered at a conference on number theory in 1997. All numbers between zero and the base number are Harshad numbers.

The first few Harshad numbers with more than one digit in base 10 are (sequence A005349 in the OEIS):

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, 204

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's not a Harshad number. For example, 99, although divisible by 9 as shown by 9 + 9 = 18 and 1 + 8 = 9, is not a Harshad number, since 9 + 9 = 18 = 2 × 32 and 99 is not divisible by 2.

Obviously, the base number 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 the base number, (that is, a 1-digit number) or the base number itself. 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.

In base 10, all factorials are Harshad numbers.

Consecutive Harshad numbers

H.G. Grundman proved in 1994 that in base 10 no 21 consecutive integers are all Harshad numbers. He also found the smallest sequence of 20 consecutive integers that are all Harshad numbers; they exceed 1044363342786.

In binary there are infinitely many sequences of four consecutive Harshad numbers, while in ternary there are infinitely many sequences of six consecutive Harshad numbers; both of these facts were proven by T. Cai in 1996. In unary base, or tallying, all numbers are Harshad numbers.

Estimating the density of Harshad numbers

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

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

where c = 14/27 log 10 ≈ 1.1939.

References

  • H. G. Grundmann, Sequences of consecutive Niven numbers, Fibonacci Quart. 32 (1994), 174-175
  • Jean-Marie De Koninck and Nicolas Doyon, On the number of Niven numbers up to x, Fibonacci Quart. 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