Harshad number
Encyclopedia
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 were defined by D. R. Kaprekar
, a mathematician
from India
. The word "Harshad" comes from the Sanskrit
(joy) + (give), meaning joy-giver. The Niven numbers take their name from Ivan M. Niven
from a paper delivered at a conference on number theory
in 1997. All integers between zero
and n are Harshad numbers in base n.
Stated mathematically, let X be a positive integer with m digits when written in base n, and let the digits be ai (i = 0, 1, ..., m − 1). (It follows that ai must be either zero or a positive integer up to n − 1.) X can be expressed as
If there exists an integer A such that the following holds, then X is a Harshad number in base n:
The first 50 Harshad numbers with more than one digit in base 10 are :
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.
is not a Harshad number, since 9 + 9 = 18, and 99 is not evenly 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.
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.
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.
proved in 1994 that, in base 10, no 21 consecutive integers are all Harshad numbers. She also found the smallest 20 consecutive integers that are all Harshad numbers; they exceed 1044363342786.
In binary
, there are infinitely many sequences of four consecutive Harshad numbers; in ternary
, there are infinitely many sequences of six consecutive Harshad numbers. Both of these facts were proven by T. Cai
in 1996.
In general, such maximal sequences run from N · bk - b to N · bk + (b-1), where b is the base, k is a relatively large power, and N is a constant. Interpolating zeroes into N will not change the sequence of digital sums, so it is possible to convert any solution into a larger one by interpolating a suitable number of zeroes, just as 21 and 201 and 2001 are all Harshad numbers base 10. Thus any solution implies an infinite class of solutions.
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.
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
.
and went on to show that 2016502858579884466176 is MHN-12. The number 10080000000000 = 1008·1010, which is smaller, is also MHN-12. In general, 1008·10n is MHN-(n+2).
Numeral system
A numeral system is a writing system for expressing numbers, that is a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner....
, is an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
that is divisible by the sum of its digits
Digit sum
In mathematics, the digit sum of a given integer is the sum of all its digits,...
when written in that base. Harshad numbers were defined by D. R. Kaprekar
D. R. Kaprekar
Dattaraya Ramchandra Kaprekar was an Indian mathematician who discovered several results in number theory, including a class of numbers and a constant named after him...
, a mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
from India
India
India , officially the Republic of India , is a country in South Asia. It is the seventh-largest country by geographical area, the second-most populous country with over 1.2 billion people, and the most populous democracy in the world...
. The word "Harshad" comes from the Sanskrit
Sanskrit
Sanskrit , is a historical Indo-Aryan language and the primary liturgical language of Hinduism, Jainism and Buddhism.Buddhism: besides Pali, see Buddhist Hybrid Sanskrit Today, it is listed as one of the 22 scheduled languages of India and is an official language of the state of Uttarakhand...
(joy) + (give), meaning joy-giver. The Niven numbers take their name from Ivan M. Niven
Ivan M. Niven
Ivan Morton Niven was a Canadian-American mathematician, specializing in number theory. He was born in Vancouver. He did his undergraduate studies at the University of British Columbia and was awarded his doctorate in 1938 from the University of Chicago. He was a member of the University of Oregon...
from a paper delivered at a conference on number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
in 1997. All integers between zero
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
and n are Harshad numbers in base n.
Stated mathematically, let X be a positive integer with m digits when written in base n, and let the digits be ai (i = 0, 1, ..., m − 1). (It follows that ai must be either zero or a positive integer up to n − 1.) X can be expressed as
If there exists an integer A such that the following holds, then X is a Harshad number in base n:
The first 50 Harshad numbers with more than one digit in base 10 are :
- 1010 (number)10 is an even natural number following 9 and preceding 11.-In mathematics:Ten is a composite number, its proper divisors being , and...
, 1212 (number)12 is the natural number following 11 and preceding 13.The word "twelve" is the largest number with a single-morpheme name in English. Etymology suggests that "twelve" arises from the Germanic compound twalif "two-leftover", so a literal translation would yield "two remaining [after having ten...
, 1818 (number)18 is the natural number following 17 and preceding 19.In speech, the numbers 18 and 80 are sometimes confused. When carefully enunciated, they differ in which syllable is stressed: 18 vs 80 . However, in dates such as 1864, or when contrasting numbers in the teens, such as 17, 18, 19, the stress...
, 2020 (number)20 is the natural number following 19 and preceding 21. A group of twenty units may also be referred to as a score.-In mathematics:*20 is the basis for vigesimal number systems....
, 2121 (number)21 is the natural number following 20 and preceding 22.-In mathematics:Twenty-one is the fifth discrete Semiprime and the second in the family. With 22 it forms the second discrete Semiprime pair...
, 2424 (number)24 is the natural number following 23 and preceding 25.The SI prefix for 1024 is yotta , and for 10−24 yocto...
, 2727 (number)27 is the natural number following 26 and preceding 28.- In mathematics :Twenty-seven is a perfect cube, being 33 = 3 × 3 × 3. 27 is also 23 . There are exactly 27 straight lines on a smooth cubic surface, which give a basis of the fundamental representation of the E6 Lie algebra...
, 3030 (number)30 is the natural number following 29 and preceding 31.-In mathematics:30 is the sum of the first four squares, which makes it a square pyramidal number.It is a primorial and is the smallest Giuga number....
, 3636 (number)36 is the natural number following 35 and preceding 37.- In mathematics :36 is both the square of 6 and a triangular number, making it a square triangular number...
, 4040 (number)40 is the natural number following 39 and preceding 41.Despite being related to the word "four" , 40 is spelled "forty", and not "fourty"...
, 4242 (number)42 is the natural number immediately following 41 and directly preceding 43. The number has received considerable attention in popular culture as a result of its central appearance in The Hitchhiker's Guide to the Galaxy as the "Answer to the Ultimate Question of Life, the Universe, and...
, 4545 (number)45 is the natural number following 44 and followed by 46.- In mathematics :Forty-five is a triangular number, a hexagonal and 16-gonal number, a Kaprekar number, and a Harshad number....
, 4848 (number)48 is the natural number following 47 and preceding 49. It is one third of a gross or four dozens.- In mathematics :Forty-eight is a double factorial of 6, a highly composite number. Like all other multiples of 6, it is a semiperfect number. 48 is the second 17-gonal number.48 is in abundance...
, 5050 (number)This article discusses the number fifty. For the year 50 CE, see 50. For other uses of 50, see 50 50 is the natural number following 49 and preceding 51.-In mathematics:...
, 5454 (number)54 is the natural number following 53 and preceding 55.-In mathematics:54 is a 19-gonal number. Twice the third power of three, 54 is a Leyland number. 54 can be written as the sum of three squares in three different ways: 7^2 + 2^2 + 1^2 = 6^2 + 2 = 2 + 2^2 = 54. It is the smallest number with...
, 6060 (number)60 is the natural number following 59 and preceding 61. Being three times twenty, 60 is called "three score" in some older literature.-In mathematics:...
, 6363 (number)63 is a natural number following 62 and preceding 64.-In mathematics:Although a number of the form 2n - 1, 63 is not a Mersenne prime since n is not prime and 63 is certainly not prime either. It is a Woodall number and a Harshad number. It is a highly cototient number. It is a repdigit in base 4...
, 7070 (number)70 is the natural number following 69 and preceding 71.-In mathematics:Its factorization makes it a sphenic number. 70 is a Pell number and a generalized heptagonal number, one of only two numbers to be both. Also, it is the seventh pentagonal number and the fourth 13-gonal number, as well as the...
, 7272 (number)72 is the natural number following 71 and preceding 73. It is half a gross or 6 dozen .-In mathematics:...
, 8080 (number)80 is the natural number following 79 and preceding 81.- In mathematics :The sum of Euler's totient function φ over the first sixteen integers is 80....
, 8181 (number)81 is the natural number following 80 and preceding 82.-In mathematics:Eighty-one is the square of 9 and the fourth power of 3. Like all powers of three, 81 is a perfect totient number. It is a heptagonal number and a centered octagonal number. It is also a tribonacci number, and an open meandric...
, 8484 (number)84 is the natural number following 83 and preceding 85.- In mathematics :Eighty-four is the sum of the first seven triangular numbers , as well as the sum of a twin prime...
, 9090 (number)90 is the natural number preceded by 89 and followed by 91.- In mathematics :*Because 90 is the sum of its unitary divisors , it is a unitary perfect number, and because it is equal to the sum of a subset of its divisors, it is a semiperfect number. 90 is a pronic number. But it is also a...
, 100100 (number)100 is the natural number following 99 and preceding 101.-In mathematics:One hundred is the square of 10...
, 102102 (number)102 is the natural number following 101 and preceding 103.-In mathematics:102 is an abundant number and semiperfect number. It is a sphenic number...
, 108108 (number)108 is the natural number following 107 and preceding 109.- In mathematics :One hundred [and] eight is an abundant number and a semiperfect number...
, 110110 (number)110 is the natural number following 109 and preceding 111.It is also known as "eleventy", a term made famous by linguist and author J. R. R...
, 111111 (number)111 is the natural number following 110 and preceding 112. It is the lowest positive integer requiring six syllables to name in American English, or seven syllables in Canadian and British English...
, 112112 (number)112 is the natural number following 111 and preceding 113.-In mathematics:One hundred [and] twelve is an abundant number and a heptagonal number...
, 114114 (number)114 is the natural number following 113 and preceding 115.-In mathematics:*One hundred [and] fourteen is an abundant number, a sphenic number and a Harshad number. It is the sum of the first four hyperfactorials, including H...
, 117117 (number)117 is the natural number following 116 and preceding 118.-In mathematics:One hundred seventeen is the smallest possible length of the longest side of a Heronian tetrahedron .117 is a pentagonal number.In base 10, it is a Harshad number.-In other fields:One hundred seventeen is also:* The...
, 120120 (number)120 is the natural number following 119 and preceding 121. 120 was known as "the great hundred", especially prior to the year 1700, from the Teutonic Hundert which equalled 120. The number 100, now known commonly as "one hundred" was then known as "the small hundred". It is also known as...
, 126126 (number)126 is the natural number following 125 and preceding 127.-In mathematics:One hundred [and] twenty-six is a pentagonal pyramidal number, and a decagonal number as well as a pentatope number....
, 132132 (number)132 is the natural number following 131 and preceding 133.-In mathematics:132 is the sixth Catalan number. It is a pronic number, the product of 11 and 12. As it has 12 divisors total, 132 is a refactorable number....
, 133133 (number)133 is the natural number following 132 and preceding 134.-In mathematics:133 is an n whose divisors added up divide φ. It is an octagonal number and a Harshad number...
, 135135 (number)135 is the natural number following 134 and preceding 136.-In mathematics:This number in base 10 can be expressed in operations using its own digits in at least two different ways...
, 140140 (number)140 is the natural number following 139 and preceding 141.-In mathematics:140 is an abundant number and a harmonic divisor number...
, 144144 (number)144 is the natural number following 143 and preceding 145. 144 is a dozen dozens, or one gross.-In mathematics:It is the twelfth Fibonacci number, and the largest one to also be a square, as the square of 12 , following 89 and preceding 233.144 is the smallest number with exactly 15 divisors.144 is...
, 150150 (number)150 is the natural number following 149 and preceding 151.- In mathematics :*150 is the sum of eight consecutive primes...
, 152152 (number)152 is the natural number following 151 and preceding 153.-In mathematics:152 is the sum of four consecutive primes...
, 153153 (number)One hundred fifty-three is the natural number following one hundred fifty-two and preceding one hundred fifty-four.-Mathematical properties:...
, 156156 (number)156 is the number equal to 100 + 50 + 6, following 155 and followed by 157.-In mathematics:It is a pronic number, a dodecagonal number, a refactorable number and a Harshad number.156 is a repdigit in base 5 .-In the military:...
, 162162 (number)162 is an even natural number between 161 and 163.-In mathematics:162 is divisible by 2, 3, 6, 9, 18, 27, 54, and 81. But there is no positive integer such that its divisors add up to 162, hence 162 is an untouchable number....
, 171171 (number)171 is the natural number following 170 and preceding 172.-In mathematics:* 171 is an odd number* 171 is a composite number* 171 is a deficient number* 171 is a Harshad number, divisible by the sum of its digits...
, 180180 (number)180 is the natural number following 179 and preceding 181.-In mathematics:180 is an abundant number, with its proper divisors summing up to 366. 180 is also a highly composite number, a positive integer with more divisors than any smaller positive integer...
, 190190 (number)190 is the natural number following 189 and preceding 191.-In mathematics:* 190 is an even number* 190 is a centered nonagonal number* 190 is a composite number* 190 is a deficient number, as 170 is less than 190...
, 192192 (number)192 is the natural number following 191 and preceding 193.-In mathematics:* 192 is an even number* 192 is the sum of ten consecutive primes...
, 195195 (number)195 is the natural number following 194 and preceding 196.-In mathematics:* 195 is an odd number* 195 is a composite number* 195 is a deficient number, as 141 is less than 195* 195 is a Harshad number* 195 is a lucky number...
, 198198 (number)198 is the natural number following 197 and preceding 199.-In mathematics:* 198 is an even number* 198 is an abundant number, as 270 is greater than 198* 198 is a composite number* 198 is a Harshad number, divisible by the sum of its digits...
, 200200 (number)200 is the natural number following 199 and preceding 201.The number appears in the Padovan sequence, preceded by 86, 114, 151 ....
.
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 is not a Harshad number. For example, 9999 (number)
99 is the natural number following 98 and preceding 100.-Mathematics:99 is the ninth repdigit, a palindromic number and a Kaprekar number...
is not a Harshad number, since 9 + 9 = 18, and 99 is not evenly 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.
For a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
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.
Although the sequence of factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
s starts with Harshad numbers in base 10, not all factorials are Harshad numbers. 432! is the first that is not.
Consecutive Harshad numbers
H.G. GrundmanHelen G. Grundman
Helen G. Grundman is a professor of mathematics at Bryn Mawr College.In 1994 Grundman proved that sequences of more than 20 consecutive Harshad numbers in base 10 do not exist. Grundman also found the smallest sequence of 20 such numbers. Each number in this sequence has more than 44 billion...
proved in 1994 that, in base 10, no 21 consecutive integers are all Harshad numbers. She also found the smallest 20 consecutive integers that are all Harshad numbers; they exceed 1044363342786.
In binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
, there are infinitely many sequences of four consecutive Harshad numbers; in ternary
Ternary numeral system
Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...
, there are infinitely many sequences of six consecutive Harshad numbers. Both of these facts were proven by T. Cai
T. Tony Cai
T. Tony Cai , is a Chinese statistician. He is the current Dorothy Silberberg Professor and Professor of Statistics at the Wharton School of the University of Pennsylvania...
in 1996.
In general, such maximal sequences run from N · bk - b to N · bk + (b-1), where b is the base, k is a relatively large power, and N is a constant. Interpolating zeroes into N will not change the sequence of digital sums, so it is possible to convert any solution into a larger one by interpolating a suitable number of zeroes, just as 21 and 201 and 2001 are all Harshad numbers base 10. Thus any solution implies an infinite class of solutions.
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
Jean-Marie De Koninck
Jean-Marie De Koninck, CM, CQ is a Quebec mathematician. He has served as a professor at Université Laval since 1972 and is the creator of the road safety program Opération Nez Rouge,or "Red Nose Operation", a system preventing people from drinking and driving.- Biography :He is the son of the...
and Nicolas Doyon; furthermore, De Koninck, Doyon and Kátai proved that
where c = (14/27) log 10 ≈ 1.1939.
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 sumDigit sum
In mathematics, the digit sum of a given integer is the sum of all its digits,...
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
11 (number)
11 is the natural number following 10 and preceding 12.Eleven is the first number which cannot be counted with a human's eight fingers and two thumbs additively. In English, it is the smallest positive integer requiring three syllables and the largest prime number with a single-morpheme name...
.
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. He states that 6804 is "MHN-3" on the grounds thatand went on to show that 2016502858579884466176 is MHN-12. The number 10080000000000 = 1008·1010, which is smaller, is also MHN-12. In general, 1008·10n is MHN-(n+2).