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?
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 |
part one
