Editing Harshad number

{{short description|Integer divisible by sum of its digits}}
{{refimprove|date=July 2019}}
In [[mathematics]], a '''harshad number''' (or '''Niven number''') in a given [[radix|number base]] is an [[integer]] that is divisible by the [[digit sum|sum of its digits]] when written in that base.<ref>{{cite OEIS|A005349|name=Niven (or Harshad, or harshad) numbers: numbers that are divisible by the sum of their digits.|mode=cs2}} (includes only base 10 Harshad numbers).</ref> Harshad numbers in base {{mvar|n}} are also known as '''{{mvar|n}}-harshad''' (or '''{{mvar|n}}-Niven''') numbers. Because being a Harshad number is determined based on the base the number is expressed in, a number can be a Harshad number many times over.<ref>{{Cite OEIS|A080221|name=n is Harshad (divisible by the sum of its digits) in a(n) bases from 1 to n.}}</ref> So-called '''Trans-Harshad numbers''' are Harshad numbers in every base.<ref>{{Cite OEIS|A080459|name=Trans-Harshad numerals: base-10 numerals that represent positive Harshad numbers in every base in which they occur. }}</ref>

Harshad numbers were defined by [[D. R. Kaprekar]], a mathematician from [[India]].<ref>D. R. Kaprekar, ''Multidigital Numbers'', [[Scripta Mathematica]] '''21''' (1955), 27.</ref> 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.

== 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, \ldots, 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, 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, and 19 is not divisible by 10.
*In base 10, every [[natural number]] expressible in the form 9R<sub>''n''</sub>''a''<sub>''n''</sub>, where the number R<sub>''n''</sub> consists of ''n'' copies of the single digit 1, ''n'' > 0, and ''a''<sub>''n''</sub> is a positive integer less than 10<sup>''n''</sup> and multiple of ''n'', is a harshad number. (R. D’Amico, 2019).  The number 9R<sub>3</sub>''a''<sub>3</sub> = 521478, where R<sub>3</sub> = 111, ''n'' = 3 and ''a''<sub>3</sub> = 3×174 = 522, is a harshad number; in fact, we have: 521478/(5+2+1+4+7+8) = 521478/27 = 19314.<ref> Rosario D'Amico, A method to generate Harshad numbers, in Journal of Mathematical Economics and Finance, vol. 5, n. 1, giugno 2019, p. 19-26.</ref>
*Harshad numbers in base 10 form the [[integer sequence|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}}.
*All integers between [[0 (number)|zero]] and {{mvar|n}} are {{mvar|n}}-harshad numbers.

== Properties ==

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 {{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 “{{d3}}”, the sum of whose digits is also {{d3}}. Since {{d3}} 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 dividing 432!)

The 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}}.

The 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, {{d2}}, {{d3}}, 10, 1{{d2}}, 20, 29, 30, 38, 40, 47, 50, 56, 60, 65, 70, 74, 80, 83, 90, 92, {{d2}}0, {{d2}}1, {{d3}}0, 100, 10{{d2}}, 110, 115, 119, 120, 122, 128, 130, 134, 137, 146, 150, 153, 155, 164, 172, 173, 182, 191, 1{{d2}}0, 1{{d3}}0, 1{{d3}}{{d2}}, 200, ...
where {{d2}} represents ten and {{d3}} 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{{d3}}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 [[mathematical proof|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 | doi=10.1080/00150517.1993.12429304 | 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 | url=https://archive.org/details/handbooknumberth00sand_741 | url-access=limited | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | zbl=1079.11001|page=[https://archive.org/details/handbooknumberth00sand_741/page/n381 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 for any base ''b''.<ref name=HBII382/><ref>{{citation | last = Grundman | first = H. G. | author-link=Helen G. Grundman | title = Sequences of consecutive ''n''-Niven numbers | journal = [[Fibonacci Quarterly]] | volume = 32 | issue = 2 | year=1994 | pages = 174–175 | doi = 10.1080/00150517.1994.12429245 | 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 | issue=2 | doi=10.1080/00150517.1997.12429006 | 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 <math>\alpha b^i \left (b^n - 1 \right )</math>.
* 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 [[modular arithmetic|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., the 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">
{{alternating rows table|class=wikitable|style=text-align: right}}
|-
| {{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>\varepsilon > 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|doi=10.1080/00150517.2003.12428555 }}.</ref> furthermore, De Koninck, Doyon and Kátai<ref>{{citation|first1=Jean-Marie|last1=De Koninck|first2=Nicolas|last2=Doyon|first3=I.|last3=Kátai|title=On the counting function for the Niven numbers|journal=[[Acta Arithmetica]]|volume=106|year=2003|issue=3 |pages=265–275|doi=10.4064/aa106-3-5|bibcode=2003AcAri.106..265D |doi-access=free}}.</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]].

== Sums of harshad numbers ==

Every natural number not exceeding one billion is either a harshad number or the sum of two harshad numbers. Conditional to a technical hypothesis on the [[zero of a function|zeros]] of certain [[Dedekind zeta function]]s, Sanna proved that there exists a positive integer <math>k</math> such that every natural number is the sum of at most <math>k</math> harshad numbers, that is, the set of harshad numbers is an [[additive basis]].<ref>{{citation|first1=Carlo|last1=Sanna|title=Additive bases and Niven numbers|journal=[[Bulletin of the Australian Mathematical Society]]|volume=104|issue=3|date=March 2021|pages=373–380|doi=10.1017/S0004972721000186|s2cid=231639019 |doi-access=free|arxiv=2101.07593}}.</ref>

The number of ways that each natural number 1, 2, 3, ... can be written as sum of two harshad numbers is:
:0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 3, 2, 4, 3, 3, 4, 3, 3, 5, 3, 4, 5, 4, 4, 7, 4, 5, 6, 5, 3, 7, 4, 4, 6, 4, 2, 7, 3, 4, 5, 4, 3, 7, 3, 4, 5, 4, 3, 8, 3, 4, 6, 3, 3, 6, 2, 5, 6, 5, 3, 8, 4, 4, 6, ... {{OEIS|id=A337853}}.

The smallest number that can be written in exactly 1, 2, 3, ... ways as the sum of two harshad numbers is:
:2, 4, 6, 8, 10, 51, 48, 72, 108, 126, 90, 138, 144, 120, 198, 162, 210, 216, 315, 240, 234, 306, 252, 372, 270, 546, 360, 342, 444, 414, 468, 420, 642, 450, 522, 540, 924, 612, 600, 666, 630, 888, 930, 756, 840, 882, 936, 972, 1098, 1215, 1026, 1212, 1080, ... {{OEIS|id=A337854}}.

== 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 [[parity (mathematics)|even]] integer ''n'' > 1, all positive integers except ''n''+1 are Nivenmorphic numbers for base ''n'', and for an [[parity (mathematics)|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&nbsp;×&thinsp;10<sup>10</sup>, which is smaller, is also MHN-12. In general, 1008&nbsp;×&thinsp;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]]
[[Category:Eponymous numbers in mathematics]]