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

Home > Numbers
Multiple Harshad Numbers (Posted on 2016-07-10) Difficulty: 3 of 5
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.)
Some Thoughts 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information