View source for Harshad number

{{refimprove|date=July 2019}}
In [[mathematics]], a '''harshad number''' (or '''Niven number''') in a given [[number base]] is an [[integer]] that is divisible by the [[digit sum|sum of its digits]] when written in that base.
Harshad numbers in base {{mvar|n}} are also known as '''{{mvar|n}}-harshad''' (or '''{{mvar|n}}-Niven''') numbers.
Harshad numbers were defined by [[D. R. Kaprekar]], a [[mathematician]] from [[India]]. The word "harshad" comes from the [[Sanskrit]] ''{{IAST|harṣa}}'' (joy) + ''{{IAST|da}}'' (give), meaning joy-giver. The term "Niven number" arose from a paper delivered by [[Ivan M. Niven]] at a conference on [[number theory]] in 1977. All integers between [[0 (number)|zero]] and {{mvar|n}} are {{mvar|n}}-harshad numbers.

== Definition ==

Stated mathematically, let {{mvar|X}} be a positive integer with {{mvar|m}} digits when written in base {{mvar|n}}, and let the digits be <math>a_i</math> (<math>i = 0, 1, \cdots, m-1</math>). (It follows that <math>a_i</math> must be either zero or a positive integer up to {{tmath|n-1}}.) {{mvar|X}} can be expressed as

:<math>X=\sum_{i=0}^{m-1} a_i n^i.</math>

{{mvar|X}} is a harshad number in base {{mvar|n}} if:

:<math>X \equiv 0 \bmod {\sum_{i=0}^{m-1} a_i}.</math>

{{anchor|all-harshad number}}
A number which is a harshad number in every number base is called an '''all-harshad number''', or an '''all-Niven number'''. There are only four all-harshad numbers: [[1 (number)|1]], [[2 (number)|2]], [[4 (number)|4]], and [[6 (number)|6]] (The number [[12 (number)|12]] is a harshad number in all bases except [[octal]]).

== Examples ==
* The number 18 is a harshad number in base 10, because the sum of the digits 1 and 8 is 9 (1 + 8 = 9), and 18 is [[divisible]] by 9.
* The [[1729 (number)|Hardy–Ramanujan number (1729)]] is a harshad number in base 10, since it is divisible by 19, the sum of its digits (1729 = 19 × 91).
* The number 19 is not a harshad number in base 10, because the sum of the digits 1 and 9 is 10 (1 + 9 = 10), and 19 is not divisible by 10.
* Harshad numbers in [[base 10]] form the sequence:
*: [[1 (number)|1]], [[2 (number)|2]], [[3 (number)|3]], [[4 (number)|4]], [[5 (number)|5]], [[6 (number)|6]], [[7 (number)|7]], [[8 (number)|8]], [[9 (number)|9]], [[10 (number)|10]], [[12 (number)|12]], [[18 (number)|18]], [[20 (number)|20]], [[21 (number)|21]], [[24 (number)|24]], [[27 (number)|27]], [[30 (number)|30]], [[36 (number)|36]], [[40 (number)|40]], [[42 (number)|42]], [[45 (number)|45]], [[48 (number)|48]], [[50 (number)|50]], [[54 (number)|54]], [[60 (number)|60]], [[63 (number)|63]], [[70 (number)|70]], [[72 (number)|72]], [[80 (number)|80]], [[81 (number)|81]], [[84 (number)|84]], [[90 (number)|90]], [[100 (number)|100]], [[102 (number)|102]], [[108 (number)|108]], [[110 (number)|110]], [[111 (number)|111]], [[112 (number)|112]], [[114 (number)|114]], [[117 (number)|117]], [[120 (number)|120]], [[126 (number)|126]], [[132 (number)|132]], [[133 (number)|133]], [[135 (number)|135]], [[140 (number)|140]], [[144 (number)|144]], [[150 (number)|150]], [[152 (number)|152]], [[153 (number)|153]], [[156 (number)|156]], [[162 (number)|162]], [[171 (number)|171]], [[180 (number)|180]], [[190 (number)|190]], [[192 (number)|192]], [[195 (number)|195]], [[198 (number)|198]], [[200 (number)|200]], ...  {{OEIS|id=A005349}}.

== Properties ==

Given the [[divisibility test]] for [[9 (number)|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 {{mvar|n}}, the digits of {{mvar|n}} can only be added up once and {{mvar|n}} must be divisible by that sum; otherwise, it is not a harshad number. For example, [[99 (number)|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.

All numbers whose base ''b'' digit sum divides ''b''−1 are harshad numbers in base ''b''.

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 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 [[base 12]] the number 11 may be represented as “Ɛ”, the sum of whose digits is also Ɛ. Since Ɛ is divisible by itself, it is harshad in base 12.

Although the sequence of [[factorial]]s starts with harshad numbers in base 10, not all factorials are harshad numbers. 432! is the first that is not. (432! has digit sum = 3897 = 3<sup>2</sup>×433 in base 10, thus not divide 432!)

Smallest {{mvar|k}} such that <math>k \cdot n</math> is a harshad number are
:1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10, 1, 9, 3, 2, 3, 6, 1, 6, 1, 1, 5, 9, 1, 2, 6, 1, 3, 9, 1, 12, 6, 4, 3, 2, 1, 3, 3, 3, 1, 10, 1, 12, 3, 1, 5, 9, 1, 8, 1, 2, 3, 18, 1, 2, 2, 2, 9, 9, 1, 12, 6, 1, 3, 3, 2, 3, 3, 3, 1, 18, 1, 7, 3, 2, 2, 4, 2, 9, 1, ... {{OEIS|id=A144261}}.

Smallest {{mvar|k}} such that <math>k \cdot n</math> is not a harshad number are
:11, 7, 5, 4, 3, 11, 2, 2, 11, 13, 1, 8, 1, 1, 1, 1, 1, 161, 1, 8, 5, 1, 1, 4, 1, 1, 7, 1, 1, 13, 1, 1, 1, 1, 1, 83, 1, 1, 1, 4, 1, 4, 1, 1, 11, 1, 1, 2, 1, 5, 1, 1, 1, 537, 1, 1, 1, 1, 1, 83, 1, 1, 3, 1, 1, 1, 1, 1, 1, 5, 1, 68, 1, 1, 1, 1, 1, 1, 1, 2, ... {{OEIS|id=A144262}}.

== Other bases ==
The harshad numbers in [[duodecimal|base 12]] are:
:1, 2, 3, 4, 5, 6, 7, 8, 9, ᘔ, Ɛ, 10, 1ᘔ, 20, 29, 30, 38, 40, 47, 50, 56, 60, 65, 70, 74, 80, 83, 90, 92, ᘔ0, ᘔ1, Ɛ0, 100, 10ᘔ, 110, 115, 119, 120, 122, 128, 130, 134, 137, 146, 150, 153, 155, 164, 172, 173, 182, 191, 1ᘔ0, 1Ɛ0, 1Ɛᘔ, 200, ...
where ᘔ represents ten and Ɛ represents eleven.

Smallest {{mvar|k}} such that <math>k \cdot n</math> is a base-12 harshad number are (written in base 10):
:1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 12, 6, 4, 3, 10, 2, 11, 3, 4, 1, 7, 1, 12, 6, 4, 3, 11, 2, 11, 3, 1, 5, 9, 1, 12, 11, 4, 3, 11, 2, 11, 1, 4, 4, 11, 1, 16, 6, 4, 3, 11, 2, 1, 3, 11, 11, 11, 1, 12, 11, 5, 7, 9, 1, 7, 3, 3, 9, 11, 1, ...

Smallest {{mvar|k}} such that <math>k \cdot n</math> is not a base-12 harshad number are (written in base 10):
:13, 7, 5, 4, 3, 3, 2, 2, 2, 2, 13, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 157, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 157, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1885, 1, 1, 1, 1, 1, 3, ...

Similar to base 10, not all factorials are harshad numbers in base 12. After 7! (= 5040 = 2Ɛ00 in base 12, with digit sum 13 in base 12, and 13 does not divide 7!), 1276! is the next that is not. (1276! has digit sum = 14201 = 11×1291 in base 12, thus does not divide 1276!)

== Consecutive harshad numbers ==

=== Maximal runs of consecutive harshad numbers ===
Cooper and Kennedy proved in 1993 that no 21 consecutive integers are all harshad numbers in base 10.<ref>{{citation | zbl=0776.11003 | last1=Cooper | first1=Curtis | last2=Kennedy | first2=Robert E. | title=On consecutive Niven numbers | journal=[[Fibonacci Quarterly]] | volume=31 | number=2 | pages=146–151 | year=1993 | issn=0015-0517 |url=http://www.fq.math.ca/Scanned/31-2/cooper.pdf}}</ref><ref name=HBII382>{{cite book | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | zbl=1079.11001|page=382}}</ref> They also constructed infinitely many 20-tuples of consecutive integers that are all 10-harshad numbers, the smallest of which exceeds 10<sup>44363342786</sup>.

{{harvs|authorlink=Helen G. Grundman|first=H. G.|last=Grundman|year=1994|txt}} extended the Cooper and Kennedy result to show that there are 2''b'' but not 2''b'' + 1 consecutive ''b''-harshad numbers.<ref name=HBII382/><ref>{{citation | last = Grundman | first = H. G. | authorlink=Helen G. Grundman | title = Sequences of consecutive ''n''-Niven numbers | journal = [[Fibonacci Quarterly]] | volume = 32 | issue = 2 | year=1994 | pages = 174–175 | zbl=0796.11002 | issn=0015-0517 |url=http://www.fq.math.ca/Scanned/32-2/grundman.pdf}}</ref> 
This result was strengthened to show that there are infinitely many runs of 2''b'' consecutive ''b''-harshad numbers for ''b'' = 2 or 3 by {{harvs|authorlink=T. Tony Cai|first=T.|last=Cai|year=1996|txt}}<ref name=HBII382/> and for arbitrary ''b'' by [[Brad Wilson (mathematician)|Brad Wilson]] in 1997.<ref>{{citation | last1=Wilson | first1=Brad | title=Construction of 2''n'' consecutive ''n''-Niven numbers | journal=[[Fibonacci Quarterly]] | volume=35 | pages=122–128 | year=1997 | issn=0015-0517 |url=http://www.fq.math.ca/Scanned/35-2/wilson.pdf}}</ref>

In [[binary numeral system|binary]], there are thus infinitely many runs of four consecutive harshad numbers and in [[ternary numeral system|ternary]] infinitely many runs of six.

In general, such maximal sequences run from ''N''·''b<sup>k</sup>'' − ''b'' to ''N''·''b<sup>k</sup>'' + (''b'' − 1), where ''b'' is the base, ''k'' is a relatively large power, and ''N'' is a constant.
Given one such suitably chosen sequence, we can convert it to a larger one as follows:
* Inserting zeroes into ''N'' will not change the sequence of digital sums (just as 21, 201 and 2001 are all 10-harshad numbers).
* If we insert ''n'' zeroes after the first digit, ''α'' (worth ''αb<sup>i</sup>''), we increase the value of ''N'' by ''αb<sup>i</sup>''(''b<sup>n</sup>'' − 1).
* If we can ensure that ''b<sup>n</sup>'' − 1 is divisible by all digit sums in the sequence, then the divisibility by those sums is maintained.
* If our initial sequence is chosen so that the digit sums are [[coprime]] to ''b'', we can solve ''b<sup>n</sup>'' = 1 modulo all those sums.
* If that is not so, but the part of each digit sum not coprime to ''b'' divides ''αb<sup>i</sup>'', then divisibility is still maintained.
* ''(Unproven)'' The initial sequence is so chosen.
Thus <!-- any solution implies --> our initial sequence yields an infinite set of solutions.

=== First runs of exactly {{mvar|n}} consecutive 10-harshad numbers ===
The smallest naturals starting runs of ''exactly'' {{mvar|n}} consecutive 10-harshad numbers (i.e., smallest {{mvar|x}} such that <math>x, x+1, \cdots, x+n-1</math> are harshad numbers but <math>x-1</math> and <math>x+n</math> are not) are as follows {{OEIS|id=A060159}}:

<div style="overflow:auto">
{| class="wikitable" style="text-align:right;overflow:auto"
|-
{{Alternating rows table section|os=background:#f0f0f0;
| {{!}} {{mvar|n}} {{!!}} 1 {{!!}} 2 {{!!}} 3 {{!!}} 4 {{!!}} 5

| {{!}} {{mvar|x}} {{!!}} 12 {{!!}} 20 {{!!}} 110 {{!!}} 510 {{!!}} {{val|131052}}
| {{!}} {{mvar|n}} {{!!}} 6 {{!!}} 7 {{!!}} 8 {{!!}} 9 {{!!}} 10
| {{!}} {{mvar|x}} {{!!}} {{val|12751220}}  {{!!}} {{val|10000095}}  {{!!}} {{val|2162049150}}  {{!!}} {{val|124324220}}  {{!!}} 1
| {{!}} {{mvar|n}} {{!!}} 11 {{!!}} 12 {{!!}} 13 {{!!}} 14 {{!!}} 15
| {{!}} {{mvar|x}} {{!!}} {{val|920067411130599}}  {{!!}} {{val|43494229746440272890}}  {{!!}} <small>{{val|121003242000074550107423034e20|s=&nbsp;− 10}}</small>  {{!!}} <small>{{val|420142032871116091607294e40|s=&nbsp;− 4}}</small>  {{!!}} unknown
| {{!}} {{mvar|n}} {{!!}} 16 {{!!}} 17 {{!!}} 18 {{!!}} 19 {{!!}} 20
| {{!}} {{mvar|x}} {{!!}} <small>{{val|50757686696033684694106416498959861492e280|s=&nbsp;− 9}}</small>  {{!!}} <small>{{val|14107593985876801556467795907102490773681e280|s=&nbsp;− 10}}</small>  {{!!}} unknown {{!!}} unknown {{!!}} unknown
}}
|}
</div>

By the previous section, no such {{mvar|x}} exists for <math>n > 20</math>.

== Estimating the density of harshad numbers ==

If we let <math>N(X)</math> denote the number of harshad numbers <math>\le x</math>, then for any given <math>\epsilon > 0</math>,

:<math>x^{1-\varepsilon} \ll N(x) \ll \frac{x\log\log x}{\log x}</math>

as shown by [[Jean-Marie De Koninck]] and Nicolas Doyon;<ref>{{citation|first1=Jean-Marie|last1=De Koninck|first2=Nicolas|last2=Doyon|title=On the number of Niven numbers up to ''x''|journal=[[Fibonacci Quarterly]]|volume=41|issue=5|date=November 2003|pages=431–440}}.</ref> furthermore, De Koninck, Doyon and Kátai<ref>{{citation|first1=Jean-Marie|last1=De Koninck|first2=Nicolas|last2=Doyon|first3=I.|last3=Katái|title=On the counting function for the Niven numbers|journal=[[Acta Arithmetica]]|volume=106|year=2003|pages=265–275|doi=10.4064/aa106-3-5}}.</ref> proved that

:<math>N(x)=(c+o(1))\frac{x}{\log x}</math>,

where <math>c = (14/27)  \log 10 \approx 1.1939</math> and the <math>o(1)</math> term uses [[Big O notation|little o notation]].

== Nivenmorphic numbers ==

A '''Nivenmorphic number''' or '''harshadmorphic number''' for a given number base is an integer {{mvar|t}} such that there exists some harshad number {{mvar|N}} whose [[digit sum]] is {{mvar|t}}, and {{mvar|t}}, written in that base, terminates {{mvar|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 (number)|11]].<ref>{{citation|first=Sandro|last=Boscaro|title=Nivenmorphic integers|journal=[[Journal of Recreational Mathematics]]|volume=28|issue=3|year=1996–1997|pages=201–205}}.</ref> In fact, for an even integer ''n'' > 1, all positive integers except ''n''+1 are Nivenmorphic numbers for base ''n'', and for an odd integer ''n'' > 1, all positive integers are Nivenmorphic numbers for base ''n''. e.g. the Nivenmorphic numbers in [[duodecimal|base 12]] are {{oeis|A011760}} (all positive integers except 13).

The smallest number with base 10 digit sum ''n'' and terminates ''n'' written in base 10 are: (0 if no such number exists)

:1, 2, 3, 4, 5, 6, 7, 8, 9, 910, 0, 912, 11713, 6314, 915, 3616, 15317, 918, 17119, 9920, 18921, 9922, 82823, 19824, 9925, 46826, 18927, 18928, 78329, 99930, 585931, 388832, 1098933, 198934, 289835, 99936, 99937, 478838, 198939, 1999840, 2988941, 2979942, 2979943, 999944, 999945, 4698946, 4779947, 2998848, 2998849, 9999950, ... {{OEIS|id=A187924}}

== {{anchor|Multiple Harshad number|Multiple Harshad numbers|Multiple harshad number}}Multiple harshad numbers ==
{{harvtxt|Bloem|2005}} defines a '''multiple harshad number''' as a harshad number that, when divided by the sum of its digits, produces another harshad number.<ref>{{citation|first=E.|last=Bloem|year=2005|title=Harshad numbers|journal=[[Journal of Recreational Mathematics]]|volume=34|issue=2|page=128}}.</ref>  He states that 6804 is "MHN-4" on the grounds that
:<math>\begin{align}
6804/18&=378\\
378/18&=21\\
21/3&=7\\
7/7&=1
\end{align}</math>

(it is not MHN-5 since <math>1/1=1</math>, but 1 is not "another" harshad number)

and went on to show that 2016502858579884466176 is MHN-12. The number 10080000000000 = 1008·10<sup>10</sup>, which is smaller, is also MHN-12. In general, 1008·10<sup>''n''</sup> is MHN-(''n''+2).

== References ==
{{reflist}}

==External links==
{{mathworld|id=HarshadNumber|title=Harshad Number}}

{{Classes of natural numbers}}
{{Divisor classes}}

[[Category:Base-dependent integer sequences]]