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
part one by Charlie)
First of all, let me apologize for the uneven breaking of that largest MH number. I realized after posting that it was much too long, and then I broke it apart by eyeballing the break points.
I modified the program to annotate the length of the path (number of iterations) to 1:
12 2
18 2
21 2
24 2
27 2
36 2
42 2
45 2
48 2
54 2
63 2
72 2
81 2
84 2
108 3
162 3
216 3
243 3
324 3
378 3
405 3
432 3
486 3
648 3
756 3
864 3
972 3
1296 3
1458 3
1944 4
2916 4
3402 4
4374 4
5832 4
6804 4
7290 4
8748 4
11664 4
13122 4
13608 4
15552 4
17496 4
23328 4
26244 4
34992 4
39366 4
52488 5
61236 5
69984 5
78732 5
91854 5
118098 5
122472 5
157464 5
183708 5
196830 5
236196 5
314928 5
354294 5
367416 5
419904 5
472392 5
559872 5
629856 5
839808 5
944784 5
1062882 5
1102248 6
1417176 6
1653372 6
2125764 6
2480058 6
3306744 6
4251528 6
4408992 6
4960116 6
5668704 6
6613488 6
7085880 6
8503056 6
9920232 6
DefDbl A-Z
Dim crlf$, harshad(10000), hLevel(10000), MHct, md
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For n = 1 To 9
harshad(n) = n
hLevel(n) = 1
Next
MHct = 9
For n = 10 To 10000000
If isMHarshad(n) Then
MHct = MHct + 1
harshad(MHct) = n
hLevel(MHct) = hLevel(md) + 1
Text1.Text = Text1.Text & n & Str(hLevel(MHct)) & crlf
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 s = 1 Then isMHarshad = 1: Exit Function
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 If
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
|
|
Posted by Charlie
on 2016-07-10 13:06:36 |
re: part one
