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 part one | Comment 1 of 12
The numbers 1 through 9 are of course multiple Harshad numbers. In addition to those, through 10,000,000, the following are multiple Harshad numbers as defined in the puzzle:

12
18
21
24
27
36
42
45
48
54
63
72
81
84
108
162
216
243
324
378
405
432
486
648
756
864
972

----------- solution to original puzzle stops here, with 36th MH number

1296
1458
1944
2916
3402
4374
5832
6804
7290
8748
11664
13122
13608
15552
17496
23328
26244
34992
39366
52488
61236
69984
78732
91854
118098
122472
157464
183708
196830
236196
314928
354294
367416
419904
472392
559872
629856
839808
944784
1062882
1102248
1417176
1653372
2125764
2480058
3306744
4251528
4408992
4960116
5668704
6613488
7085880
8503056
9920232

These 81, together with the first 9, make up the first 90 Multiple Harshad numbers.

Taking that last one

9920232 / 27 = 367416
 367416 / 27 =  13608
  13608 / 18 =    756
    756 / 18 =     42
     42 /  6 =      7
      7 /  7 =      1

DefDbl A-Z
Dim crlf$, harshad(10000), MHct


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 For n = 1 To 9
   harshad(n) = n
 Next
 
 MHct = 9
 
 For n = 12 To 10000000
  If isMHarshad(n) Then
    Text1.Text = Text1.Text & n & crlf
    MHct = MHct + 1
    harshad(MHct) = n
  End If
 Next
 
 
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

Function isMHarshad(n)
  If n < 10 Then isMHarshad = 1: Exit Function
  s = sod(n)
  If n Mod s > 0 Then isMHarshad = 0: Exit Function
  low = 1: hgh = MHct
  lkup = n / s
  DoEvents
  Do
    md = Int((low + hgh) / 2)
    If harshad(md) < lkup Then
      low = md + 1
    ElseIf harshad(md) > lkup Then
      hgh = md - 1
    Else
      isMHarshad = 1
      Exit Function
    End If
  Loop Until low > hgh
  If harshad(md) = lkup Then isMHarshad = 1 Else isMHarshad = 0
End Function

Function sod(n)
  s$ = LTrim(Str(n))
  tot = 0
  For i = 1 To Len(s$)
   tot = tot + Val(Mid(s$, i, 1))
  Next
  sod = tot
End Function

The 15095th (largest) such number is

1084464230395358729932151438017082487888975184391965518658152244719602291
5013498755182422783168249743964253744721999890517357463607557093872677041563756654749597073829754535969423346925824806
60444123117894183362026904307484194943533374289213175436767660095097341776774
737704214452219362042142821400148498683673386805499498461216483217433922113783701769988
332099212066552174647398316255439210412526487664089968857007109138790524864928123175632
81491911243925427378877369142768640406323066824797472131147967140977568412789256710759
050409656222035706522393291677890231411695839455220245836396027648440861440543344125146
66794357803245807219597400899217668506865459495834831489909678
7905903269227303672466102253350452074656943436672832591933669507219965857
30118894402624162399404426144503547718692814107138420936301106286615600332822535921841
758178666499361272326153553003350453435945619719470682453850227925538297220603452527881
4354951808365156295137852239659582806470869382588169461649156300693104208166972689007
4865290348600834734599766478437790255612666824099267434364355484351860734906370740873815309182436
21501901195914047236424084375593247227970958601139272341797395550196589930052572977357562548
3069870019644473846768589175846921947404031033007197765680719106360203110870455555886
0664475868432527724451032696584219891472321740800000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000

according to http://chesswanks.com/seq/b114440.txt, referenced by Sloane's A114440.

An alternative definition of Multiple Harshad numbers does not require going all the way down to 1, as in Sloane's A235507 which requires only that the first quotient also be a Harshad number. This seems to be common parlance, as this sequence is the first Sloane sequence obtained via a Google search for Multiple Harshad number, and within that first Google result page is

http://hubpages.com/education/Recreational-Math-Harshad-Numbers-are-Divisible-by-the-Sum-of-Their-Digits

showing:

   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!

BTW, that referenced number does not go all the way to 1. The sum of the digits is 108, and the sequence of divisors and quotients is:

 108   18671322764628559872 
 99   188599219844732928 
 99   1905042624694272 
 63   30238771820544 
 54   559977255936 
 72   7777461888 
 63   123451776 
 36   3429216 
 27   127008 
 18   7056 
 18   392 
 14   28 

from

    4   kill "multhars.txt"
    5   open "multhars.txt" for output as #2
   10   N=2016502858579884466176
   20   while N>1
   25   Tot=0
   30   Ns=cutspc(str(N))
   40   for I=1 to len(Ns)
   50      Tot=Tot+val(mid(Ns,I,1))
   60   next
   70   if N@Tot=0 then
   80    :print #2,Tot,:N=N//Tot:print #2,N
   85    :else end
   90   wend
  100   close #2

Edited on July 10, 2016, 12:51 pm
  Posted by Charlie on 2016-07-10 12:43:17

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 (4)
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