Harshad-Zahl
# Harshad-Zahl

Eine Harshad-Zahl oder Niven-Zahl ist eine natürliche Zahl, die durch ihre Quersumme, das heißt die Summe ihrer Ziffern (im Dezimalsystem mit Basis 10), teilbar ist.

Der Begriff Harshad-Zahl wurde vom indischen Mathematiker D. R. Kaprekar eingeführt und ist vom Sanskrit-Wort harsha („Freude“) abgeleitet, während Niven-Zahl auf den Mathematiker Ivan M. Niven zurückgeht, der diese Zahlen auf einem Kongress im Jahre 1977 beschrieb.

## Beispiele

777 ist durch seine Quersumme $7+7+7=21$ teilbar und ist somit eine Harshad-Zahl: $777=21\cdot 37$.

Die ersten Harshad-Zahlen (im Dezimalsystem) sind:

    $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,\ldots$ (Folge A005349 in OEIS)

Die kleinsten $k$, sodass $k\cdot n$ eine Harshad-Zahl ist, sind die folgenden:

    $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,\ldots$ (Folge A144261 in OEIS)
    d. h.: ${\underline {1}}\cdot 1=1,{\underline {1}}\cdot 2=2,\ldots ,{\underline {1}}\cdot 10=10,{\underline {10}}\cdot 11=110,{\underline {1}}\cdot 12=12,{\underline {9}}\cdot 13=117,\ldots$ sind Harshad-Zahlen

Die kleinsten $k$, sodass $k\cdot n$ keine Harshad-Zahl ist, sind die folgenden:

    $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,\ldots$ (Folge A144262 in OEIS)
    d. h.: ${\underline {11}}\cdot 1=11,{\underline {7}}\cdot 2=14,{\underline {5}}\cdot 3=15,{\underline {4}}\cdot 4=16,{\underline {3}}\cdot 5=15,{\underline {11}}\cdot 6=66,\ldots$ sind keine Harshad-Zahlen

## n-Harshad-Zahlen

Harshad-Zahlen nennt man auch n-Harshad-Zahlen (oder n-Niven-Zahlen), wenn man sie in der Basis n betrachtet.

Die ersten n-Harshad-Zahlen in der Basis 12 sind (wobei mangels weiterer Ziffern $A$ für 10 und $B$ für 11 steht):

    $1,2,3,4,5,6,7,8,9,A,B,10,1A,20,29,30,38,40,47,50,56,60,65,70,74,80,83,90,92,A0,A1,B0,100,$
       $10A,110,115,119,120,122,128,130,134,137,146,150,153,155,164,172,173,182,191,1A0,\ldots$

Beispiel:

    $172$ ist keine n-Harshad Zahl für die Basis 10:
    $N=172$ hat die Quersumme $1+7+2=10$, es ist aber $10$ kein Teiler von $172$.
    $172_{12}$ ist aber eine n-Harshad Zahl für die Basis 12:
    $N=172_{12}$ ist im Dezimalsystem die Zahl ${\underline {1}}\cdot 12^{2}+{\underline {7}}\cdot 12^{1}+{\underline {2}}\cdot 12^{0}=230$. Die Quersumme von $N=172_{12}$ ist $1+7+2=A_{12}$ (im Dezimalsystem also $10$). Es ist $A_{12}$ tatsächlich ein Teiler von $N=172_{12}=A_{12}\cdot 1B_{12}$ (im Dezimalsystem $230=10\cdot 23$).

Die kleinsten $k$, sodass $k\cdot n$ eine n-Harshad-Zahl zur Basis 12 ist, sind die folgenden (im Dezimalsystem geschrieben):

    $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\ldots$

Die kleinsten $k$, sodass $k\cdot n$ keine n-Harshad-Zahl zur Basis 12 ist, sind die folgenden (im Dezimalsystem geschrieben):

    $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\ldots$

## Eigenschaften

Das oben angegebene Beispiel mit der Zahl 777 lässt sich auf alle 3-stelligen natürlichen Zahlen desselben Typs verallgemeinern:

* Jede natürliche Zahl der Form $nnn$, wobei $n$ eine beliebige Ziffer von 1 bis 9 darstellen kann, ist im Dezimalsystem eine Harshad-Zahl (lässt sich also durch ihre Quersumme teilen).

       Der Beweis ergibt sich aus folgender Überlegung:
          ${\begin{aligned}nnn&=n\cdot 10^{2}+n\cdot 10^{1}+n\cdot 10^{0}\\&=n\cdot (100+10+1)\\&=n\cdot 111\\&=n\cdot (3\cdot 37)\\&=(n\cdot 3)\cdot 37\\\end{aligned}}$
          Nun ist aber die Quersumme von $nnn\colon ~n+n+n=n\cdot 3$.
          Somit ist jede natürliche Zahl der Form $nnn$ das 37-fache ihrer Quersumme, also eine Harshad-Zahl. q. e. d.
* Alle ganzen Zahlen zwischen 0 und der Basis n sind n-Harshad-Zahlen.
* Im Dezimalsystem gibt es keine 21 aufeinander folgende Harshad-Zahlen.
* Im Dezimalsystem gibt es unendlich viele 20 aufeinander folgende Harshad-Zahlen. Die kleinste davon ist größer als $10^{44363342786}$.

| n | erstes Auftreten von n aufeinander folgenden Harshad-Zahlen (Folge A060159 in OEIS) |
| - | - |
| $1$ | $12$ |
| $2$ | $20$ |
| $3$ | $110$ |
| $4$ | $510$ |
| $5$ | $131.052$ |
| $6$ | $12.751.220$ |
| $7$ | $10.000.095$ |
| $8$ | $2.162.049.150$ |
| $9$ | $124.324.220$ |
| $10$ | $1$ |
| $11$ | $920.067.411.130.599$ |
| $12$ | $43.494.229.746.440.272.890$ |
| $13$ | $121.003.242.000.074.550.107.423.034\cdot 10^{20}-10$ |
| $14$ | $420.142.032.871.116.091.607.294\cdot 10^{40}-4$ |
| $15$ | unbekannt |
| $16$ | $50.757.686.696.033.684.694.106.416.498.959.861.492\cdot 10^{280}-9$ |
| $17$ | $14.107.593.985.876.801.556.467.795.907.102.490.773.681\cdot 10^{280}-10$ |
| $18$ | unbekannt |
| $19$ | unbekannt |
| $20$ | unbekannt |

* Mit Basis n gibt es keine 2n+1 aufeinander folgende n-Harshad-Zahlen (Verallgemeinerung der weiter oben stehenden Eigenschaft).
* Mit Basis n gibt es unendlich viele 2n aufeinander folgende Harshad-Zahlen (Verallgemeinerung der weiter oben stehenden Eigenschaft).
* Sei $N(x)$ die Anzahl der Harshad-Zahlen $\leq x$ und sei $\varepsilon >0$. Dann gilt:

       $x^{1-\varepsilon }\ll N(x)\ll {\frac {x\log \log x}{\log x}}$
    Beispiel:
       Es gibt unter 100000 genau 11872 Harshad-Zahlen. Somit ist $x=100000$ und $N(x)=11872$. Und tatsächlich gilt $x^{1-\varepsilon }=100000^{1-\varepsilon }\ll 100000^{1-0,185095}\approx N(x)=11872\ll 21223,7\approx {\frac {100000\cdot \log \log 100000}{\log 100000}}={\frac {x\log \log x}{\log x}}$

| $x$ | Harshad-Zahlen $\leq x$ |
| - | - |
| $10$ | $10$ |
| $100$ | $33$ |
| $1000$ | $213$ |
| $x$ | Harshad-Zahlen $\leq x$ |
| $10^{4}$ | $1538$ |
| $10^{5}$ | $11872$ |
| $10^{6}$ | $95428$ |
| $x$ | Harshad-Zahlen $\leq x$ |
| $10^{7}$ | $806095$ |
| $10^{8}$ | $6954793$ |
| $10^{9}$ | $61574510$ |

## Nivenmorphe Zahlen

Eine nivenmorphe Zahl (oder harshadmorphe Zahl) für eine Basis n ist eine ganze Zahl t, so dass eine Harshad-Zahl N existiert, dessen Quersumme t ist, und t, geschrieben in dieser Basis n, die Zahl N in dieser Basis n beschreibt.

Beispiel 1:

    $18$ ist eine nivenmorphe Zahl für die Basis 10:
    $N=16218$ ist eine Harshad-Zahl (zur Basis n=10). Die Quersumme von $16218$ ist $1+6+2+1+8=18$. Es ist $18$ tatsächlich ein Teiler von $16218=18\cdot 901$.

Beispiel 2:

    $18_{12}$ ist eine nivenmorphe Zahl für die Basis 12:
    $N=1A0_{12}$ ist eine Harshad-Zahl (zur Basis n=12) und ist im Dezimalsystem die Zahl ${\underline {1}}\cdot 12^{2}+{\underline {10}}\cdot 12^{1}+{\underline {0}}\cdot 12^{0}=264$. Die Quersumme von $N=1A0_{12}$ ist $1+A+0=B_{12}$ (im Dezimalsystem also 11). Es ist $B_{12}$ tatsächlich ein Teiler von $N=1A0_{12}=B_{12}\cdot 20_{12}$ (im Dezimalsystem $264=11\cdot 24$).

Die nächste Liste gibt die jeweils kleinste Zahl (im Dezimalsystem) an, deren Quersumme n ist und die durch n teilbar ist (falls es keine solche Zahl gibt, wird 0 angegeben):

    $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,\ldots$ (Folge A187924 in OEIS)
    Zum Beispiel hat $289835$ die Quersumme $2+8+9+8+3+5=35$ und tatsächlich ist $35$ ein Teiler von $289835=35\cdot 8281$. Somit ist $35$ eine nivenmorphe Zahl zur Basis 10.

Eigenschaften:

* Alle positiven ganzen Zahlen mit Basis 10 sind nivenmorphe Zahlen, außer der Zahl 11.
* Alle positiven geraden ganzen Zahlen mit Basis n>1 sind nivenmorphe Zahlen zur Basis n, außer n+1.
* Alle positiven ungeraden ganzen Zahlen mit Basis n>1 sind nivenmorphe Zahlen zur Basis n.

## Multiple Harshad-Zahlen

Eine multiple Harshad-Zahl ist eine Harshad-Zahl, welche, durch seine Quersumme dividiert, wieder eine (andere) Harshad-Zahl ergibt.

Beispiel 1: $6804$ ist eine multiple Harshad-Zahl, weil $6804/18=378$, $378/18=21$, $21/3=7$ und $7/7=1$ ebenfalls Harshad-Zahlen sind. Man bezeichnet diese Zahl $6804$ auch als MHN-4, man kann also vier (verschiedene) weitere Harshad-Zahlen daraus machen.

Beispiel 2: $2016502858579884466176$ ist eine MHN-12, man kann also 12 verschiedene weitere Harshad-Zahlen durch Division mit ihren jeweiligen Quersummen (die erste Quersumme ist $108$) finden.

Beispiel 3: $10080000000000=1008\cdot 10^{10}$ ist eine weitere, kleinere MHN-12.

Beispiel 4: $1008\cdot 10^{n}$ ist eine MHN-(n+2).

