A number is called Harshad if it is divisible by the sum of its digits.
For example 102 is divisible by 3.
This quotient is not Harshad because 34 is not divisible by 7.
108 is a Multiple Harshad Number because the process ends at 1:
108/9=12; 12/3=4; 4/4=1.
Find the Multiple Harshad Numbers below 1000.
Hard bonus: Apparently there are only 15095 of these numbers. Can you prove the list is finite?
(In reply to
The method for part 2 by Charlie)
I had this idea: modify the program so that when it shows an MHN at level 49, instead of trying for level 50, to write the number to a supplement file before continuing. Then the next version of the program would read that file in and start from there rather than from 1. To the program, level 98 would technically be only recursion level 49.
Using this method, I got to numbers up to level 98; and then again to get to level 147. However, as the numbers were getting larger and larger, during the run to get to level 196, the stack overflowed due to the large size of the numbers. It got to a level-186 MHN with 522 digits and gave up trying to do a level 187.
But that indeed is the method by which one could exhaust the numbers. I just don't feel like lowering the level limit, especially as at the limit of 49 (i.e., 49 higher than the preceding run), there seem to be only about 1500 numbers found. Even at that rate we'd have to go 10 rounds to get them all.
|
|
Posted by Charlie
on 2016-07-10 21:13:38 |
re: The method for part 2
