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