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.)
 The method for part 2 | Comment 4 of 12 |
(In reply to part one by Charlie)

The method used to find MH numbers in my first post will not prove part 2, that the list of such numbers is finite, for two reasons:

1. Testing every number in turn by increments of 1 would take "forever" for such large numbers as would be encountered.

2. We wouldn't know when to stop; there might always be more.

The solution would be to devise a recursive procedure that would start out at 1 and work its way up, with multiples taking the place of divisors, that is, actually being the divisors that would be used on the way down.

Every recursive procedure needs a stopping test so that it does not recurse forever. Of course if there were infinitely many MH numbers, the stopping procedure at some point would never be met, but at least there is a method in place so that eventually it does stop if the cardinality of the set is finite.

The below program's design is to do just that. For example it finds 400362681871113269704732351253634497228532915507726913665761280000, which is the 1017th number on the A114440 list and is a level 34 MH number down to 1. For each MH number that it finds, it tries all multiples of that number, starting at 2 times, until the multiplier (which acts as the divisor going in the other direction) is too large to be produced by summing the digits of the product (the potential MH number) even if all its digits were 9.

This particular implementation crashed when it was required to attempt a 50th level of recursion: apparently beyond the reach of UBASIC, at least for the currently written program. But, having faith in the OEIS statement of finitude, I'm sure the implementation in another language having the sufficient precision of arithmetic and also allowing a sufficient level of recursion, would terminate, thereby showing the list is finite, while, along the way, listing them, though not in order.

An aside: the termination via crash ocurred while processing numbers that eventually go through 7. Those that go through 2 through 6 are shown to be finite in number with, for example, only 54 and 972 going through 6.

4      kill "mhnumbrs.txt"
5      open "mhnumbrs.txt" for output as #2
10      gosub *MHN(1)
20
30      close #2
40      end
50
60      *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,nextMH
130            :print #2, lvl,nextMH
140            :gosub *MHN(nextMH)
150         inc mult
160         nextMH=n*mult
170         nMH=len(str(nextMH))
180       until nMH*9<mult
185       lvl=lvl-1
190       return
200
1070     fnSOD(X)
1080        Sod=0
1090        S=cutspc(str(X))
1100        for I=1 to len(S)
1110          Sod=Sod+val(mid(S,I,1))
1120        next
1130      return(Sod)

level  MH number
1   2
2   18
3   162
4   2916
5   78732
6   2125764
7   76527504
8   3443737680
9   185961834720
10   10041939074880
10   11715595587360
11   632642161717440
12   45550235643655680
13   3689569087136110080
14   398473461410699888640
15   46621394985051886970880
16   5874295768116537758330880
17   845898590608781437199646720
18   98970135101227428152358666240
19   13360968238665702800568419942400
20   1923979426367861203281852471705600
21   259737222559661262443050083680256000
18   121809397047664526956749127680
12   56937794554569600
11   843522882289920
12   60733647524874240
13   4919425449514813440
14   531297948547599851520
15   52598496906212385300480
7   95659380
1   3
2   27
3   243
4   4374
5   118098
3   486
1   4
2   12
3   108
4   1944
5   52488
6   1417176
5   69984
2   24
3   216
2   36
3   324
4   5832
5   157464
6   4251528
6   5668704
7   153055008
4   8748
5   236196
3   648
4   11664
5   314928
6   8503056
4   17496
5   472392
5   629856
6   22674816
2   48
3   432
3   864
4   15552
5   419904
6   11337408
6   18895680
7   340122240
8   6122200320
9   220399211520
9   275499014400
9   330598817280
10   20827725488640
11   1499596235182080
12   121467295049748480
11   1687045764579840
12   91100471287311360
13   9838850899029626880
7   510183360
7   680244480
5   559872
6   15116544
1   5
2   45
3   405
4   7290
5   196830
6   7085880
7   255091680
8   9183300480
1   6
2   54
3   972
1   7
2   21
3   378
4   3402
5   61236
6   1102248
6   1653372
7   44641044
8   2008846980
9   108477736920
10   6834097425960
11   430548137835480
12   27124532683635240
13   2197087147374454440
7   59521392
8   2678462640
9   144636982560
10   6508664215200
10   7810397058240
11   421761441144960
11   562348588193280
8   3749847696
9   168743146320
9   202491775584
10   9112129901280
11   492055014669120
12   22142475660110400
13   1793540528468942400
12   35427961056176640
13   2550813196044718080
14   160701231350817239040
15   15909421903730906664960
15   17355732985888261816320
16   1874419162475932276162560
13   3188516495055897600
14   286966484555030784000
15   28409681970948047616000
16   2812558515123856713984000
16   3579619928339453999616000
11   574064183780640
12   36166043578180320
5   91854
6   2480058
4   6804
5   122472
6   3306744
7   119042784
8   4285540224
9   192849310080
8   5356925280
9   289273965120
10   15620794116480
11   1124697176386560
12   70855922112353280
13   5101626392089436160
14   459146375288049254400
15   41323173775924432896000
16   4090994203816518856704000
17   331370530509138027393024000
16   5206719895766478544896000
15   45455491153516876185600
16   4909193044579822628044800
17   574375586215839247481241600
18   62032563311310638727974092800
18   67201943587253191955305267200
19   10281897368849738369161705881600
20   1573130297434009970481740999884800
21   226530762830497435749370703983411200
22   30581652982117153826165045037760512000
21   240688935507403525483706372982374400
22   32493006293499475940300360352620544000
23   5263867019546915102328658377124528128000
24   994870866694366954340116433276535816192000
25   196984431605484656959343053788754091606016000
26   46094356995683409728486274586568457435807744000
23   5848741132829905669254064863471697920000
13   5739329691100615680
14   568193639418960952320
15   71592398566789079992320
16   6443315871011017199308800
17   637888271230090702731571200
18   74632927733920612219593830400
19   11418837943289853669597856051200
20   1849851746812956294474852680294400
21   233081320098432493103831437717094400
22   33563710094174279006951727031261593600
23   5437321035256233199126179779064378163200
23   6947687989494075754439007495471149875200
24   1125525454298040272219119214266326279782400
25   212724310862329611449413531496335666878873600
25   243113498128376698799329750281526476432998400
26   45948451146263196073073322803208504045836697600
27   9511329387276481587126177820264160337488196403200
26   48136472629418586362267290555742242333733683200
27   11263934595283949208770545990043684706093681868800
28   2230259049866221943336568106028649571806549010022400
22   35661441975060171444886209970715443200
22   39856905736831956320755175849623142400
23   6815530880998264530849135070285557350400
24   1288135336508671996330486528283970339225600
25   231864360571560959339487575091114661060608000
26   45909143393169069949218539868040702890000384000
27   8263645810770432590859337176247326520200069120000
28   1784947495126413439625616830069422528363214929920000
29   353419604035029861045872132353745660615916556124160000
30   85880963780512256234146928161960195529667723138170880000
29   369484131491167582002502683824370463371185490493440000
30   89784643952353722426608152169322022599198074189905920000
31   21009606684850771047826307607621353288212349360437985280000
31   21817668480421954549665780977145251491605132028147138560000
32   5498052457066332546515776806240603375884493271093078917120000
33   1533956635521506780477901728941128341871773622634969017876480000
34   400362681871113269704732351253634497228532915507726913665761280000
34   455585120749887513801936813495515117535916765922585798309314560000
34   497001949908968196874840160176925582766454653733729961791979520000
31   25857977458277872058863147824764742508569045366692904960000
32   6748932116610524607363281582263597794736520840706848194560000
33   2004432838633325808386894629932288545036746689689933913784320000
34   559236761978697900539943601751108504065252326423491561945825280000
35   156027056592056714250644264888559272634205399072154145782885253120000
34   577276657526397832815425653420499100970583046630700967169884160000
35   171451167285340156346181419065888232988263164849318187249455595520000
36   54007117694882149249047147005754793391302896927535228983578512588800000
34   613356448621797697366389756759280294781244487045119777618001920000
35   149045617015096840460032710892505111631842410351964105961174466560000
36   40242316594076146924208831940976380140597450795030308609517105971200000
37   11951968028440615636490023086469984901757442886124001657026580473446400000
38   3442166792190897303309126648903355651706143551203712477223655176352563200000
38   3980005353470725006951177687794504972285228481079292551789851297657651200000
39   1289521734524514902252181570845419611020414027869690786779911820441078988800000
40   441016433207384096570246097229133506968981597531434249078729842590849014169600000
38   4087573065726690547679587895572734836401045467054408566703090521918668800000
39   1434738146070068382235535351346029927576766958936097406912784773193452748800000
40   516505732585224617604792726484570773927636105216995066488602518349642989568000000
41   204536270103748948571497919687890026475343897665930046329486597266458623868928000000
37   12314148877787300958807902573938772323022819943279274434512234427187200000
37   12676329727133986281125782061407559744288197000434547211997888380928000000
38   3993043864047205678554621349343381319450782055136882371779334839992320000000
39   1329683606727719490958688909331345979377110424360581829802518501717442560000000
40   394916031198132688814730606071409755875001796035092803451347995010080440320000000
40   454751793500880065907871606991320324946971765131318985792461327587365355520000000
39   1473433185833418895386655277907707706877338578345509595186574555957166080000000
40   490653250882528492163756207543266666390153746589054695197129327133736304640000000
41   176635170317710257178952234715575999900455348772059690270966557768145069670400000000
36   42925137700347890052489420737041472149970614181365662516818246369280000
37   13907744614912716377006572318801436976590478994762474655449111823646720000
38   4380939553697505658757070280422452647626000883350179516466470224448716800000
39   1261710591464881629722036240761666362516288254404851700742343424641230438400000
40   431505022280989517364936394340489895980570583006459281653881451227300809932800000
39   1340567503431436731579663505809270510173556270305154932038739888681307340800000
40   434343871111785501031810975882203645296232231578870197980551723932743578419200000
40   470539193704434292784461890539053949070918250877109381145597700927138876620800000
41   160924404246916528132285966564356450582254041799971408351794413717081495804313600000
40   542929838889731876289763719852754556620290289473587747475689654915929473024000000
41   161250162150250367258059824796268103316226215973655561000279827510031053488128000000
42   52245052536681118991611383233990865474457293975464401764090664113250061330153472000000
43   18338013440375072766055595515130793781534510185388005019195823103750771526883868672000000
44   7756979685278655780041516902900325769589097808419126123119833172886576355871876448256000000
42   53696303996033372296933921657157278404303329919227301813093182560840340811546624000000
39   1419424415397991833437290770856874657830824286205458163335136352721384243200000
40   421569051373203574530875358944491773375754813003021074510535496758251120230400000
40   472668330327531280534617826695339261057664487306417568390600405456220952985600000
41   140382494107276790318781494528515760534126352730006017812008320420497623036723200000
42   48010812984688662289023271128752390102671212633662058091706845583810187078559334400000
43   17283892674487918424048377606350860436961636548118340913014464410171667348281360384000000
44   6222201362815650632657415938286309757306189157322602728685207187661800245381289738240000000
43   18148087308212314345250796486668403458809718375524257958665187630680250715695428403200000
44   6696644216730343993397543903580640876300786080568451186747454235721012514091613080780800000
45   2892950301627508605147738966346836858561939586805570912674900229831477406087576850897305600000
46   1093535214015198252745845329279104332536413163812505804991112286876298459501104049639181516800000
44   6859977002504254822504801071960656507430073545948169508375440924397134770532871936409600000
45   2346112134856455149296641966610544525541085152714273971864400796143820091522242202252083200000
46   802370350120907661059451552580806227735051122228281698377625072281186471300606833170212454400000
47   310517325496791264830007750848772010133464784302345017272140902972819164393334844436872219852800000
48   125759516826200462256153139093752664104053237642449731995217065703991761579300611996933249040384000000
49   50932604314611187213742021332969828962141561245192141458062911610116663439616747858757965861355520000000

 Posted by Charlie on 2016-07-10 14:27:26
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 (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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