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
re: The method for part 2 by Charlie)
When my original UBASIC program crashed when attempting to go to the 50th level of recursion in building all the members of Sloane's A114440 (Multiple Harshad Numbers by this puzzle's definition), I thought of a way to have the program automatically reset the recursion level: when the 49th (or to play it safe, 48th) level is reached, put that result out to a new hold file (in addition of course to putting it on the main result file), and, rather than attempt to recurse later, ignore the furtherout branches on the tree until later. After this batch was finished, then start over, using this hold file as new starting points. (The original program had only one starting point: the number 1.)
This went along fine until a couple of places in the program used the str() function to convert numbers to strings: so as to determine the length of a number to see if it had sufficient digits to add up to the multiplier (which serves in the upward path, what a divisor would do in the downward methodology of Harshad numbers), and also to actually separate out the digits for addition. So it crashed at those points when the lengths of the numbers reached 1080, which is apparently the limit for strings.
That was fixed by using base10 logs to determine size (the addition of 2 was just to be safe, before stopping further attempts) and remainder and quotient were used to isolate digits for adding them.
And as the sizes of the numbers increased, every once in a while I had to lower the allowable level of recursion, as stack space kept getting tighter so the level of recursion where it crashed was getting lower. When this happened, the added results from that phase had to be deleted and the phase rerun. Hyphens were used as phase markers to facilitate this.
Then in the next phase it crashed again (the phases being the restarting with the leftovers from the preceding phase), when reading in that phase's input, as that also had a similar limit to the str() function.
To store the holdover numbers, then, I could not use the text files as I had been, but had to learn what UBASIC's author had put into the language to allow files (file1 and file 2 used here) to be treated like arrays, and use those in the program.
The final version, used from phase 15 up (24 phases were used in all) is:
1 Phase=15:LvlOffset=342
2 open "mhnmin15.txt" for input as #1
3 kill "mhnoflo.ubd":open "mhnoflo" as file1(1000) word 542
4 OfloCt=0
5 while eof(1)=0
6 input #1,Ns:N=val(Ns)
7 inc OfloCt:file1(OfloCt)=N
8 wend:close #1
9 kill "mhnoflo2.ubd":open "mhnoflo2" as file2(1000) word 542
10 loop
16 open "mhnumbs.txt" for append as #2
20 DidOne=0:NewOfloCt=0
21 print #2,""
22 Lvl=0:if Phase<4 then MaxLvl=48:else MaxLvl=10
25 for OfloPtr=1 to OfloCt
30 N=file1(OfloPtr)
35 if N>0 then DidOne=1:gosub *MHN(N)
40 next
45
46 close #2
47
50 if DidOne=0 then goto 59
51 inc Phase
52 LvlOffset=LvlOffset+MaxLvl
53 for I=1 to NewOfloCt
54 file1(I)=file2(I)
55 next I
56 OfloCt=NewOfloCt
57 if OfloCt=0 then goto 59
58 endloop
59 end
60
65 *MHN(N)
70 local Mult,NextMH
80 Mult=2:Lvl=Lvl+1
90 NextMH=N*Mult
100 repeat
110 if fnSOD(NextMH)=Mult then
120 :print Lvl+LvlOffset,NextMH
130 :print #2,Lvl+LvlOffset,NextMH
140 :if Lvl<MaxLvl then gosub *MHN(NextMH):else inc NewOfloCt:file2(NewOfloCt)=NextMH
150 inc Mult
160 NextMH=N*Mult
170 NMH=log(NextMH)/log(10)
180 until NMH*9<Mult
185 Lvl=Lvl1
190 return
200
1070 fnSOD(X)
1075 local Sod,S,D
1080 Sod=0
1090 S=X
1100 while S>0
1110 Sod=Sod+S@10
1115 S=S\10
1120 wend
1130 return(Sod)
The output file has 15120 lines: 24 were the hyphen lines () at the start of each phase; 2 were blank lines, at places where I had to delete a phase to start over and apparently left a carriagereturn/linefeed in place; and 15,094 were the MHNumbers. This is one less than the number of MHNumbers, as my list does not include the number 1, as that was treated as the starting point, from which the output was those subsequently derived.
That the program terminated after investigating all branches and subbranches for the formation of MHN's, is proof the set is finite.
The final phase output was all those MHN's that take over 432 steps to reach 1 of which there are four that take 440 such steps, the maximum (these are the longest four in the list linked to in the OEIS entry A114440).
While this took about two days of processing using the command prompt in Windows 7 to run UBASIC, it would have taken weeks using DOSBox, emulating DOS, to run the same UBASIC program, required by later versions of Windows.

Posted by Charlie
on 20160714 11:08:43 