Harshad number

In mathematics, 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 in base $n$ are also known as $n$ -harshad (or $n$ -Niven) numbers. 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 term "Niven number" arose from a paper delivered by Ivan M. Niven at a conference on number theory in 1977. All integers between zero and $n$ are $n$ -harshad numbers.

Definition

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,\cdots ,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}.

$X$ is a harshad number in base $n$ if:

X\equiv 0{\bmod {\sum _{i=0}^{m-1}a_{i}}}.

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, 2, 4, and 6 (The 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 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.
In base 10, every natural number expressible in the form 9R_na_n, where the number R_n consists of n copies of the single digit 1, n>0, and a_n is a positive integer less than 10ⁿ and multiple of n, is a harshad number. (R. D’Amico, 2019). The number 9R₃a₃ = 521478, where R₃ = 111, n =3 and a₃ = 3*174 = 522, is a harshad number; in fact, we have: 521478/(5+2+1+4+7+8) = 521478/27 = 19314. [1]
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, ... (sequence A005349 in the OEIS).

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 $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.

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 factorials 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²×433 in base 10, thus not dividing 432!)

Smallest $k$ such that $k\cdot n$ 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, ... (sequence A144261 in the OEIS).

Smallest $k$ such that $k\cdot n$ 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, ... (sequence A144262 in the OEIS).

Other bases

The harshad numbers in 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 $k$ such that $k\cdot n$ 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 $k$ such that $k\cdot n$ 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.[2][3] They also constructed infinitely many 20-tuples of consecutive integers that are all 10-harshad numbers, the smallest of which exceeds 10^44363342786.

H. G. Grundman (1994) extended the Cooper and Kennedy result to show that there are 2b but not 2b + 1 consecutive b-harshad numbers.[3][4] This result was strengthened to show that there are infinitely many runs of 2b consecutive b-harshad numbers for b = 2 or 3 by T. Cai (1996)[3] and for arbitrary b by Brad Wilson in 1997.[5]

In binary, there are thus infinitely many runs of four consecutive harshad numbers and in ternary infinitely many runs of six.

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. 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ⁱ), we increase the value of N by αbⁱ(bⁿ − 1).
If we can ensure that bⁿ − 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ⁿ = 1 modulo all those sums.
If that is not so, but the part of each digit sum not coprime to b divides αbⁱ, then divisibility is still maintained.
(Unproven) The initial sequence is so chosen.

Thus our initial sequence yields an infinite set of solutions.

First runs of exactly $n$ consecutive 10-harshad numbers

The smallest naturals starting runs of exactly $n$ consecutive 10-harshad numbers (i.e., smallest $x$ such that $x,x+1,\cdots ,x+n-1$ are harshad numbers but $x-1$ and $x+n$ are not) are as follows (sequence A060159 in the OEIS):

$n$	1	2	3	4	5
$x$	12	20	110	510	131052
$n$	6	7	8	9	10
$x$	12751220	10000095	2162049150	124324220	1
$n$	11	12	13	14	15
$x$	920067411130599	43494229746440272890	121003242000074550107423034×10²⁰ − 10	420142032871116091607294×10⁴⁰ − 4	unknown
$n$	16	17	18	19	20
$x$	50757686696033684694106416498959861492×10²⁸⁰ − 9	14107593985876801556467795907102490773681×10²⁸⁰ − 10	unknown	unknown	unknown

By the previous section, no such $x$ exists for $n>20$ .

Estimating the density of harshad numbers

If we let $N(X)$ denote the number of harshad numbers $\leq x$ , then for any given $\epsilon >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;[6] furthermore, De Koninck, Doyon and Kátai[7] proved that

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

where $c=(14/27)\log 10\approx 1.1939$ and the $o(1)$ term uses little o notation.

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.[8] 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 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, ... (sequence A187924 in the OEIS)

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.[9] He states that 6804 is "MHN-4" on the grounds that

{\begin{aligned}6804/18&=378\\378/18&=21\\21/3&=7\\7/7&=1\end{aligned}}

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

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

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.
Cooper, Curtis; Kennedy, Robert E. (1993), "On consecutive Niven numbers" (PDF), Fibonacci Quarterly, 31 (2): 146–151, ISSN 0015-0517, Zbl 0776.11003
Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. p. 382. ISBN 1-4020-2546-7. Zbl 1079.11001.
Grundman, H. G. (1994), "Sequences of consecutive n-Niven numbers" (PDF), Fibonacci Quarterly, 32 (2): 174–175, ISSN 0015-0517, Zbl 0796.11002
Wilson, Brad (1997), "Construction of 2n consecutive n-Niven numbers" (PDF), Fibonacci Quarterly, 35: 122–128, ISSN 0015-0517
De Koninck, Jean-Marie; Doyon, Nicolas (November 2003), "On the number of Niven numbers up to x", Fibonacci Quarterly, 41 (5): 431–440.
De Koninck, Jean-Marie; Doyon, Nicolas; Katái, I. (2003), "On the counting function for the Niven numbers", Acta Arithmetica, 106: 265–275, doi:10.4064/aa106-3-5.
Boscaro, Sandro (1996–1997), "Nivenmorphic integers", Journal of Recreational Mathematics, 28 (3): 201–205.
Bloem, E. (2005), "Harshad numbers", Journal of Recreational Mathematics, 34 (2): 128.

External links

Weisstein, Eric W. "Harshad Number". MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 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.

[2] Cooper, Curtis; Kennedy, Robert E. (1993), "On consecutive Niven numbers" (PDF), Fibonacci Quarterly, 31 (2): 146–151, ISSN 0015-0517, Zbl 0776.11003

[HBII382-3] Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. p. 382. ISBN 1-4020-2546-7. Zbl 1079.11001.

[4] Grundman, H. G. (1994), "Sequences of consecutive n-Niven numbers" (PDF), Fibonacci Quarterly, 32 (2): 174–175, ISSN 0015-0517, Zbl 0796.11002

[5] Wilson, Brad (1997), "Construction of 2n consecutive n-Niven numbers" (PDF), Fibonacci Quarterly, 35: 122–128, ISSN 0015-0517

[6] De Koninck, Jean-Marie; Doyon, Nicolas (November 2003), "On the number of Niven numbers up to x", Fibonacci Quarterly, 41 (5): 431–440.

[7] De Koninck, Jean-Marie; Doyon, Nicolas; Katái, I. (2003), "On the counting function for the Niven numbers", Acta Arithmetica, 106: 265–275, doi:10.4064/aa106-3-5.

[8] Boscaro, Sandro (1996–1997), "Nivenmorphic integers", Journal of Recreational Mathematics, 28 (3): 201–205.

[9] Bloem, E. (2005), "Harshad numbers", Journal of Recreational Mathematics, 34 (2): 128.

Divisibility-based sets of integers
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Descartes Refactorable Superperfect