The number $512$ is interesting because it is equal to the sum of its digits raised to some power: $5 + 1 + 2 = 8$, and $8^3 = 512$. Another example of a number with this property is $614656 = 28^4$.
We shall define $a_n$ to be the $n$th term of this sequence and insist that a number must contain at least two digits to have a sum.
You are given that $a_2 = 512$ and $a_{10} = 614656$.
Find $a_{30}$.
Prima idea: fare un loop per \(n\) da 1 in poi e vedere quali numeri verificano la condizione richiesta. Il controllo può essere effettuato guardando se la candidata base (somma delle cifre di \(n\)) elevata ad un opportuno esponente (ricavabile tramite dei logaritmi) risulta pari al numero \(n\). Il loop si ferma quando incontriamo il 30esimo valore che soddisfa il criterio. Questo metodo funzionerebbe ma risulta in realtà molto lento, dato che effettuiamo i controlli su ogni numero che incontriamo, e se il numero target è molto grande (sarà in effetti nell'ordine di \(10^{14}\)) ciò vuol dire fare molti controlli, che sono anche costosi perché ciascuno richiede calcoli di potenze e logaritmi.
Questo piccolo esempio mostra quanto ci mette anche solo per arrivare al 13esimo numero.
i = 0
n = 11
@time while i<13
global i, n # questione di scope
sum_digits = sum(digits(n))
if sum_digits != 1
x = round(log10(n)/log10(sum_digits))
if n == sum_digits^Int(x) # rifacciamo il controllo per evitare errori dovuti ad approssimazioni
i += 1
println("$i) $n = $sum_digits^$(Int(x))")
end
end
n += 1
end1) 81 = 9^2
2) 512 = 8^3
3) 2401 = 7^4
4) 4913 = 17^3
5) 5832 = 18^3
6) 17576 = 26^3
7) 19683 = 27^3
8) 234256 = 22^4
9) 390625 = 25^4
10) 614656 = 28^4
11) 1679616 = 36^4
12) 17210368 = 28^5
13) 34012224 = 18^6
15.631573 seconds (272.21 M allocations: 6.950 GiB, 3.93% gc time, 0.60% compilation time)
Seconda idea: precalcolare un insieme di valori base^esponente = valore, e scorrere su questi valori per vedere se soddisfano la condizione che la base sia pari alla somma delle loro cifre. Questo metodo diventa veloce perché filtriamo via il ricavare l'esponente opportuno a cui elevare la base, e perché non scorriamo più su tutti i numeri da 1 in poi, ma solo su quelli effettivamente ottenibili come una qualche base elevate ad un qualche esponente.
# creiamo il dizionario che contiene la chiave (base, esponente) e il valore corrispondente (base^esponente)
d = Dict{Tuple{Int, Int}, Int}()
# lo popoliamo, come precalcolo per lo step successivo
println("precomputation step")
@time for base in 2:70
for exp in 2:30
d[(base, exp)] = base^exp
end
endprecomputation step
0.070654 seconds (115.57 k allocations: 5.486 MiB, 99.73% compilation time)
# lo ordiniamo per scorrere sui numeri in ordine crescente
sorted_pairs = sort(collect(d), by = x -> x[2])
i = 0
@time for (k,v) in sorted_pairs
if sum(digits(v)) == k[1]
global i += 1
println("$i) $v = $(k[1])^$(k[2])")
end
end1) 81 = 9^2
2) 512 = 8^3
3) 2401 = 7^4
4) 4913 = 17^3
5) 5832 = 18^3
6) 17576 = 26^3
7) 19683 = 27^3
8) 234256 = 22^4
9) 390625 = 25^4
10) 614656 = 28^4
11) 1679616 = 36^4
12) 17210368 = 28^5
13) 34012224 = 18^6
14) 52521875 = 35^5
15) 60466176 = 36^5
16) 205962976 = 46^5
17) 612220032 = 18^7
18) 8303765625 = 45^6
19) 10460353203 = 27^7
20) 24794911296 = 54^6
21) 27512614111 = 31^7
22) 52523350144 = 34^7
23) 68719476736 = 64^6
24) 271818611107 = 43^7
25) 1174711139837 = 53^7
26) 2207984167552 = 58^7
27) 6722988818432 = 68^7
28) 20047612231936 = 46^8
29) 72301961339136 = 54^8
30) 248155780267521 = 63^8
31) 3904305912313344 = 54^9
32) 81920000000000000 = 20^13
33) 5430070304767207435 = 67^23
0.021146 seconds (31.07 k allocations: 1.209 MiB, 92.36% compilation time)
e quindi il 30esimo numero risulta essere \(248155780267521 = 63^8\). Possiamo infine wrappare tutto in una funzione e trovare anche numeri più alti che soddisfano il criterio. Per quelli veramente alti serve anche passare dal tipo Int al tipo BigInt:
function big_test(ub_base, ub_exp)
d = Dict{Tuple{Int, Int}, BigInt}()
for base in 2:ub_base
for exp in 2:ub_exp
d[(base, exp)] = BigInt(base)^exp
end
end
sorted_pairs = sort(collect(d), by = x -> x[2])
i = 0
for (k,v) in sorted_pairs
if sum(digits(v)) == k[1]
i += 1
println("$i) $v = $(k[1])^$(k[2])")
end
end
end
@time big_test(500,70)1) 81 = 9^2
2) 512 = 8^3
3) 2401 = 7^4
4) 4913 = 17^3
5) 5832 = 18^3
6) 17576 = 26^3
7) 19683 = 27^3
8) 234256 = 22^4
9) 390625 = 25^4
10) 614656 = 28^4
11) 1679616 = 36^4
12) 17210368 = 28^5
13) 34012224 = 18^6
14) 52521875 = 35^5
15) 60466176 = 36^5
16) 205962976 = 46^5
17) 612220032 = 18^7
18) 8303765625 = 45^6
19) 10460353203 = 27^7
20) 24794911296 = 54^6
21) 27512614111 = 31^7
22) 52523350144 = 34^7
23) 68719476736 = 64^6
24) 271818611107 = 43^7
25) 1174711139837 = 53^7
26) 2207984167552 = 58^7
27) 6722988818432 = 68^7
28) 20047612231936 = 46^8
29) 72301961339136 = 54^8
30) 248155780267521 = 63^8
31) 3904305912313344 = 54^9
32) 45848500718449031 = 71^9
33) 81920000000000000 = 20^13
34) 150094635296999121 = 81^9
35) 13744803133596058624 = 82^10
36) 19687440434072265625 = 85^10
37) 53861511409489970176 = 94^10
38) 73742412689492826049 = 97^10
39) 179084769654285362176 = 106^10
40) 480682838924478847449 = 117^10
41) 671088640000000000000 = 40^13
42) 8007313507497959524352 = 98^11
43) 21048519522998348950643 = 107^11
44) 23316389970546096340992 = 108^11
45) 2518170116818978404827136 = 108^12
46) 14076019706120526112710656 = 86^13
47) 146853371345156431381127623 = 103^13
48) 166507350731038802170609664 = 104^13
49) 213292826014568334917410816 = 106^13
50) 240984500018808097135911707 = 107^13
51) 2017516459574609153391845376 = 126^13
52) 2670419511272061205254504361 = 91^14
53) 4491199828872408503792328704 = 134^13
54) 4946966739525117513427734375 = 135^13
55) 13695791164569918553628942336 = 146^13
56) 101472439712019470540189876224 = 118^14
57) 283956682347124706942551243009 = 127^14
58) 667840509835890864312744140625 = 135^14
59) 2759031540715333904109053133443 = 107^15
60) 4219782742781494680756610809856 = 154^14
61) 80643984127232967094095054209024 = 134^15
62) 100712557719971285024106952523776 = 136^15
63) 225179981368524800000000000000000 = 80^17
64) 534138422146939893094821310496768 = 152^15
65) 649846542388350180836518064717824 = 154^15
66) 3411353329548244127894995329875968 = 172^15
67) 9585753470490322141591520062265281 = 133^16
68) 27328356228554426163172505624313856 = 142^16
69) 30394579970238968448638779635802999 = 199^15
70) 248314265639726167358751235626296641 = 163^16
71) 442779263776840698304313192148785281 = 169^16
72) 1326958063637576800539947579727410881 = 181^16
73) 1441151880758558720000000000000000000 = 80^19
74) 2235968621526344925885872579239957441 = 187^16
75) 4372327021734283642004853327592915343 = 143^17
76) 13508517176729920890000000000000000000 = 90^19
77) 91397407411741874683083843738640173291 = 171^17
78) 1215766545905692880100000000000000000000 = 90^20
79) 4849687664788584363858837602739217760256 = 216^17
80) 17358494027033103736099033196316709617664 = 172^18
81) 43472473122830653562489222659449707872441 = 181^18
82) 109418989131512359209000000000000000000000 = 90^21
83) 413335079574020313162122296733856201171875 = 155^19
84) 527343255303841790870720812082050804460293 = 157^19
85) 2672551590126744157608054674761577307202131 = 171^19
86) 3333311951341729629204978703084632004627637 = 173^19
87) 7868517635232348294810549301360397124911821 = 181^19
88) 9847709021836112328810000000000000000000000 = 90^22
89) 17896754443176031520198514559819163143441509 = 189^19
90) 100794437067515115687082154498875335492959343 = 207^19
91) 1424201691977055041360709423546231879609039601 = 181^20
92) 20864448472975628947226005981267194447042584001 = 207^20
93) 1887620149539230539058375534310517606114631604199 = 199^21
94) 10315908977942302627204470186314316211062255002161 = 169^22
95) 24878997722115027320114677422679960727691650390625 = 225^21
96) 191540580003116921429323712183642218614831262597249 = 193^22
97) 2524144100572738110818511483976079134636146367057489 = 217^22
98) 5597774487475881147025802420102991163730621337890625 = 225^22
99) 13266270948476060794645310906489108110454554997293056 = 234^22
100) 95780971304118053647396689196894323976171195136475136 = 256^22
101) 449987958058483731145152266240000000000000000000000000 = 140^25
102) 3104307401943398225947002752118451297846365869366575104 = 234^23
103) 5233476330273605372135115210000000000000000000000000000 = 90^28
104) 8127668947035784909216000925230737687249003559134429184 = 244^23
105) 90843464823339216026868859800411987382769274486334892911 = 271^23
106) 4301431178848799040411011070519998467949638490834092425216 = 252^24
107) 10945383723441507344727857527190282349078513578188038209536 = 262^24
108) 12795621425112113141935148247655082376252275523500373035251 = 211^25
109) 40719913064560249818128041081360346218088750603039104925501 = 221^25
110) 106027789261962824452408289529751186963631266312359757479936 = 288^24
111) 210281019656164214863109519134145127118463502897144582373376 = 236^25
112) 1606938044258990275541962092341162602522202993782792835301376 = 256^25
113) 1771446674072174508225286450717886232339530422363435486157057 = 257^25
114) 2606229663144729566039563623004841124284699624933480197086501 = 261^25
115) 11534379242395753535341914088376535713095348879804515254117557 = 277^25
116) 51922968585348276285304963292200960000000000000000000000000000 = 160^28
117) 55660922447187573821761251863649846565640419423580169677734375 = 295^25
118) 60574909849697616383534878613708060571267806502808902095077376 = 296^25
119) 71681420304936976905470042438674147582874433584558631779565568 = 298^25
120) 77943464916384201250278947277627946518095789363103497073007499 = 299^25
121) 1551484788048185532684923506896493070316489557389975896963919057 = 337^25
122) 42536043213832457558766474492498614961439017908885402928656941056 = 306^26
123) 46301788027092145989912680349353041288862842956233592928809850249 = 307^26
124) 98144088987499163964447513503423764631060866947422283598781218816 = 316^26
125) 188005374836229120894273278138806956375747747317139671689960882176 = 324^26
126) 11915044326770568568475280859619597548448212930716574192047119140625 = 305^27
127) 14214648924317288818903192867251383675680892787563713029144624026443 = 307^27
128) 70938903323020164041464952207191804150246813586391508579254150390625 = 265^28
129) 1073296814898316170984211740926491941610861783219864941022659022422016 = 292^28
130) 1392889173388510144614180174894677204330000000000000000000000000000000 = 170^31
131) 2511087676118693443561250442594506891646159404533693480446335986028401 = 301^28
132) 27827079189650067530362843798136778294857459122407403567332450459713536 = 328^28
133) 1108396998497832141082413001966113061944395007879909314215183258056640625 = 305^29
134) 2576082658793001301315775246063496590502176287623802384243874806611574784 = 314^29
135) 6992258384610037749654907908844932162839569400603068061172962188720703125 = 325^29
136) 12971924951512854051451981749206985529326629699255039169557612260367532032 = 332^29
137) 28175847678049304974714539037469518611387968114539900203818707238059119461 = 341^29
138) 40254497110927943179349807054456171205137000000000000000000000000000000000 = 170^33
139) 852816467445062775684393634550197158767987961376797522357621036567913851518976 = 396^30
140) 1302170364000761783417759323245917816834217981806298630860569507247916171413731 = 331^31
141) 2491252276737353900429116760717192733564626177316000157084543963667389912973312 = 338^31
142) 5144688242860438508840629192066311739620174720237734553723377443969180364701696 = 346^31
143) 12443711599231750233024365514839090159964049355547483009723854179287614678368256 = 356^31
144) 24782373219955756593141390684102264036204870195928189896094374893403847801176064 = 364^31
145) 31963033635613871188281081201771130829717935180966383659489717372826121949469583 = 367^31
146) 152829236972828514288963875267195881407232795380332800664366406458863375861415936 = 386^31
147) 165592215068078950681452294706487190780651185048178515989054812983286611871777963 = 387^31
148) 10927366588345647443779494878694325141601296667965958851853959496465593861483768307 = 443^31
149) 69600958265429357262384513189947161678833860890586039771065083991610603249028038656 = 388^32
150) 1086195238781730826486019042992192234284970013421290033658379460246112028282838843392 = 352^33
151) 2080256094756505306208596361132964602239968006816514218251401517925975683043965119079 = 359^33
152) 11408522273327637976303026412230988152573608558409273567493767241007838689860043931648 = 378^33
153) 120603276874866998083402398673047310378821583119226685139356502990783968735332522786816 = 406^33
154) 431828082425008338966455055687350146766971824197388194726109669963748770639807619530752 = 422^33
155) 466908868873284478299614289120627638881652621991398693081830641970668582517202217366183 = 423^33
156) 9597824637451542033104235916921705589422583418057010838370758360563520945915209417591689 = 387^34
157) 80631612511707529718899522220925984083299761507562808680375746583297934432626088045707264 = 412^34
158) 1630095296502146224606081625885212511192327485259750644417779438464164023361962517129592832 = 378^35
159) 4065466584510989297966864691622953337018005524518005291262546137720014342342410695954399232 = 388^35
160) 4263376574603679940868286208947466366968141231118089886935493766118288147799515712075905889 = 463^34
161) 39356089472755184720357893431981316074529738547199653666013760308073925159305248426399105024 = 414^35
162) 787370185364257677856107651948636556789109661591860448320936137088731733986177170486283628251 = 451^35
163) 1577401034790263847611143500349705894762986143512986053009867901435365564828855350030306902016 = 388^36
164) 5599422865207443516278087162672625751400385895765096099959820018376686174589159548193599775493 = 477^35
165) 38474309771589407811495360376101333228957008848509303417374219555134075140828732662813688856576 = 424^36
166) 827180612553027674871408692069962853565812110900878906250000000000000000000000000000000000000000 = 250^40
167) 6745476311272347640330461502667869649910099068035831839740094461762638476604282359291101004693504 = 414^37
168) 12544043342250126364781063288980149095386304527494136064357808464289003026338335329668276770857941 = 421^37
169) 13694957397509751252040454603690149498896290391054037795048250354131843256400203058749357384794112 = 422^37
170) 35485601003420318171584941981236496965167280623364925388791645658704306238438238057161623947356273 = 433^37
171) 681389097589837766781760841058319030242642765733341666227799211029252104727299727980950272293057989 = 469^37
172) 1274031085097784415815236894035739864590378402477536550527757888961229028618096882840941563318146797 = 477^37
173) 2357459976474945363936435174540389306292527977513158808229467883399566223451984114944934844970703125 = 485^37
174) 5016402325920920699751838873979521559748994678536584612959033138268812304813764058053493499755859375 = 495^37
175) 294674406038174646601897395953306525149181581822458665194228858696522698422182609467327986112317620224 = 468^38
176) 319571486769633912620645834456351625183799457128937241460837829972719237117103572423065677705444196841 = 469^38
177) 6034444764301926099398767225037966746150282982201748550057984000000000000000000000000000000000000000000 = 280^42
178) 27390962865270456500312485443250171965874909004612907841052568775779764643847160157209749056291010090049 = 449^39
179) 5991610576301463240909279602209380656282135908947517788114928581644775462104410132863506440172426562545601 = 441^40
180) 64540767108105163797333975251277008364274346777082186685500781547147187499220123855972044830264254451941376 = 468^40
181) 292045669268989424051611986595665315608228315109246408600883995691482504483909232582218146313417410557771776 = 486^40
182) 473100469521271006192863350442976592898182185804617086324545945600000000000000000000000000000000000000000000 = 280^44
183) 608426270054842929256063688447931973737861223448671189171192111878636288818561306470655836164951324462890625 = 495^40
184) 1134576070110189270529855753262617597022737676242181030601009360530580741226193805749539168839147251073810432 = 432^41
185) 75199745536708272048931194007661747314218309504310971218838010255639548140536886933290454412039001772350899851569 = 487^42
186) 3460507475500936578540841060343370561610120325042096084113109656683932204309173949514221684630288919281896853070581 = 461^43
187) 10804695562359870518299193703899148848724015728610899282651377959960576000000000000000000000000000000000000000000000 = 360^45
188) 104309403484756922445160376100044452427960695571016643340612957613273343992921606953092755091448632354725917399271499 = 499^43
189) 3889690402449553386587709733403693585540645662299923741754496065585807360000000000000000000000000000000000000000000000 = 360^46
190) 137032772235232212194333623130258016365360407551749249561179409371017870000000000000000000000000000000000000000000000000 = 270^49
191) 372561595210378274207233937350874800780999862581666093319654464721679687500000000000000000000000000000000000000000000000 = 350^47
192) 4544665223678420453018145322135642541657563147842170567232748157740310690000000000000000000000000000000000000000000000000 = 290^49
193) 1793425102043152552209503172265155970005554068135751862124211286446805941573967601173036127149649438150082178478762155311104 = 478^46
194) 1877944508893233281587362192715149196869044938545410448866468981413670579521000000000000000000000000000000000000000000000000 = 370^48
195) 11027242749461874052167896330862729183956786504112635314316726529059077488640000000000000000000000000000000000000000000000000 = 340^49
196) 45638795413271338590386157325482163095672483166254096431657671928405761718750000000000000000000000000000000000000000000000000 = 350^49
197) 181477395416686362804636185321682727926984364020265242095297768435971428188160000000000000000000000000000000000000000000000000 = 360^49
198) 23519470446002552619480849617690081539337173577026375375550590789301897093185536000000000000000000000000000000000000000000000000000 = 360^51
199) 4818291821103903991966428618497405708782048713433741634401243580192384759503364270089000000000000000000000000000000000000000000000000000000 = 370^54
200) 244060935614376048905075508812749091366937113481559315007326191067484865223123910372818117000000000000000000000000000000000000000000000000000000000 = 370^57
201) 33411942085608081095104837156465350608133690835625470224502955557138678049045663330038800217300000000000000000000000000000000000000000000000000000000000 = 370^59
202) 59868228263066087813842817839365466702986287421791885051451787514217361968429514669588234633216000000000000000000000000000000000000000000000000000000000 = 460^57
203) 919830726093055390540659348609628347241360477428516324184197687568618535185978345701348601128550400000000000000000000000000000000000000000000000000000000000 = 440^59
204) 178079228571615523608671649890824048025927388430160760362060672313284548412005407727781089178487357440000000000000000000000000000000000000000000000000000000000000 = 440^61
205) 126462243384781145263479730532454467979528658735288778476527493228704648184285544259174116391013379280490000000000000000000000000000000000000000000000000000000000000 = 490^61
206) 3483222019150087290906367725765158038860604776315729218075578227857117741864010261964290002242715875008010000000000000000000000000000000000000000000000000000000000000000 = 430^64
207) 5824228738434357322434036590082369091753194215438155001822259090811561080269775914075580658391118049621582031250000000000000000000000000000000000000000000000000000000000000000000 = 450^67
0.052579 seconds (417.40 k allocations: 41.641 MiB, 11.23% compilation time)