All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Multiple Harshad Numbers (Posted on 2016-07-10)
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?

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Moby Dick has been captured -- part 2 solved | Comment 7 of 12 |
(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 further-out 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 base-10 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=Lvl-1
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 carriage-return/line-feed 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 sub-branches 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 2016-07-14 11:08:43

 Search: Search body:
Forums (0)