Recreational Math: Harshad-Niven Numbers and Surprising Factorizations
Here's a funny story: A math teacher wanted to motivate his students to practice factorizing numbers, so he told his class, "The first student to find any factor of 2353 will get this piece of candy." All the students bent their heads toward their desks to start testing divisors of 2353, when no sooner did a student in the back row raise his hand and say "13!"
The teacher verified on the chalkboard that 2353 ÷ 13 = 181. He was surprised that his worst student could find a factor before any of the smart ones could, but he gave the winner a piece of candy. He then posed the same challenge, this time with the number 17887. Again, before any of the other children in the classroom could make progress on the problem, the student in the back said "31!" The teacher again confirmed that 17887 ÷ 31 = 577 and gave the student another piece of candy.
The teacher could not figure out why his worst student was finding factors so quickly, so he selected an even larger number for the students. "Class, the first person to find a factor of 644269613 will get the entire bag of candy!" The students' eyes went wide and they set to solving the problem even faster than before. But again, the student in the back was the first to raise a hand and shout "41!" And indeed, the teacher confirmed that 644269613 ÷ 41 = 15713893.
By this time the teacher could no long contain his curiosity. He walked to the back of the math classroom to see how the student had worked out the problems so quickly. He saw only three lines of math work written on the student's paper:
2 + 3 + 2 + 5 = 13
1 + 7 + 8 + 8 + 7 = 31
6 + 4 + 4 + 2 + 6 + 9 + 6 + 1 + 3 = 41
The worst student in the class had not suddenly become better at factoring, but had simply shouted out the sums of the numbers' digits. Yet amazingly, these answers were all correct as factors! The teacher had unwittingly selected numbers whose digits added up to a factor of each number.
The Discovery of Harshad (Niven) Numbers
Numbers that are divisible by the sum of their digits are called Harshad numbers, or sometimes Niven numbers. They were first studied by the Indian mathematician Dattaraya Kaprekar who gave them the name "harshad" which means joy giver in Sanskrit. They were also investigated by the mathematician Ivan Niven.
The simplest Harshad numbers are the two-digit Harshad numbers:
10, 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, 45, 48, 50, 54, 60, 63, 70, 72, 80, 81, 84, 90
For example, 84 is a harshad number because 8 + 4 = 12 and 84 is divisible by 12. (84/12 = 7) It turns out there are infinitely Harshad numbers. One way to prove this is to come up with a never ending sequence of numbers that are always divisible by the sum of their digits. For instance, the powers of 10 will suffice:
10, 100, 1000, 10000, ...
Or, we can use the fact that any number whose digits sum to a multiple of 9 is always divisible by 9. One series that uses this fact is
522, 5022, 50022, 500022, ...
which are all divisible by 5 + 2 + 2 = 9. Of course there are many more Harshad numbers which don't fall into any particularly constructed sequence.
How to Find Harshad Numbers
Just as there is no formula for the nth prime number, there is neither a formula for the nth Harshad number. While it is possible to come up with Niven numbers using methods described in the section above, that will not allow you to generate all the Niven numbers.
For example, any number whose last two digits is a multiple of 4 is also a multiple of 4. This can be used to create ever larger and larger Harshad numbers using the sequence
112, 1012, 10012, 100012,...
But there are many Harshad numbers between the terms of this sequence, for example, 133, 4991, and 51044. The most efficient way to generate Harshad numbers is to run a program that simply checks if the sum of the digits divides evenly into the number.
An interesting fact is that all the factorials up to (and including) 431! are Harshad numbers. Observe the pattern for some small factorials:
- 7! = 5040, and 5040/(5+4) = 560
- 8! = 40320, and 40320/(4+3+2) = 4480
- 9! = 362880, and 362800/(3+6+2+8+8) = 13440
- 10! = 3628800, and 3628800/(3+6+2+8+8) = 13400
- 11! = 39916800, and 39916800/(3+9+9+1+6+8) = 1108800
Distribution of Niven Numbers: How Rare or Dense Are They Among the Integers?
If x is a suitably large integer and N(x) is the number of Harshad numbers less than or equal to x, then
N(x) = [C + o(1)] * x / Ln(x)
which could be interpreted as
N(x) ≈ C * x / Ln(x)
where C = (14/27)*Ln(10) ≈ 1.193933 and o(1) is a function that converges to 0. [See explanation of "little o" notation.] This result was discovered in 2003 using more advanced techniques in number theory.
In layman's terms, let's try to understand the approximation formula with an example. Take x = 100,000. There are exactly 11872 Niven numbers less than or equal to 100,000, so the true value of N(100000) is 11872. The approximation formula says that
≈ (14/27)Ln(10) * 100000 / Ln(100000)
which is in the ballpark of the actual amount 11872.
Consecutive Niven Numbers
While isolated Harshad numbers are relatively rare among the integers, consecutive Harshad numbers are even rarer. Some consecutive pairs include
20 & 21
80 & 81
512 & 513
Consecutive triples are even rarer than consecutive pairs. An example of three consecutive Niven numbers is 511, 512, and 513. You can check that 511/(5+1+1) = 73, 512/(5+1+2) = 64, and 513/(5+1+3) = 57.
In fact, 510, 511, 512, and 513 form a set of four consecutive Harshad numbers. A natural question to ask at this point is what is the longest possible chain of consecutive Harshad numbers? The answer turns out to be 20. In other words, there is no string of 21 or more consecutive Harshad numbers. This was proven in 1993. There are, however, infinitely many strings of consecutive Harshad numbers.
Multiple Niven Numbers
A Harshad number is called a "multiple Harshad number" or "multiple Niven number" if upon dividing it by the sum of its digits you obtain another Harshad number. For example, take the number 3779136. Repeatedly dividing by the sum of digits gives us
- 3779136/(3+7+7+9+1+3+6) = 104976
- 104976/(1+0+4+9+7+6) = 3888
- 3888/(3+8+8+8) = 144
- 144/(1+4+4) = 16
Therefore, 3779136 is a multiple Harshad number four times over. The number 2016502858579884466176 can go through the process above 12 times!
Square Harshad Numbers
The first several square Niven numbers are
1, 4, 9, 36, 81, 100, 144, 225, 324, 400, 441, 576, 900, 1296, 1521, 1764, 2025, 2304, 2401, 2601, 2704, 2916, 3600,...
This set is infinite, just as the set of regular Niven numbers is, and just as the set of square numbers is. Notice that most of the numbers in this small subset are multiples of 9.
Are There Any Prime Harshad Numbers?
The only prime Harshad numbers are the single-digit prime numbers 2, 3, 5, and 7. Beyond that, no prime is divisible by the sum of its digits.