wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sum of Powers
        
(Message started by: tony123 on Oct 5th, 2007, 2:54pm)
Title: Sum of Powers
Post by tony123 on Oct 5th, 2007, 2:54pm
Find the last decimal digit of the sum 1^1 + 2^2 + 3^3 + ... + 2001^2001
Title: Re: Sum of Powers
Post by JP05 on Oct 5th, 2007, 3:13pm
I found it = 1.
Title: Re: Sum of Powers
Post by Grimbal on Oct 6th, 2007, 11:16am
That's right, "1^1 + 2^2 + 3^3 + ... + 2001^2001" ends with a 1.   ::)
Title: Re: Sum of Powers
Post by ThudanBlunder on Oct 7th, 2007, 3:37pm
Prove it.
Title: Re: Sum of Powers
Post by JP05 on Oct 8th, 2007, 11:42am
After 19 pencils and 407 pieces of paper I get

62445943596933665023923094895458744549218343603974464915942504299692
       3348831437519734835371654302653472558338668437115725691746954537314
       5379002192037595166993287598236056143375273383470303700734176610361
       4329498901396153347349980083791659937183031970591773089520808137197
       6387140705277647596680421306634688532697265122445978370182914765902
       6716026018037027188892307343519279547843192812967092003947344769499
       7655446199436888769146385788898614530372984508624072102970493419288
       3919970258110681099165226318632651328021430147886584164142806348277
       5675619591477594058212320824840051660670656073526645237615716083140
       3622884811487202578948053214343714742562411139771165533912240526566
       2810759654984635450713035462314329634937560127774413396086567813874
       7078943330963293112054971521642765732278188161697702533401156041951
       2132943780520332867892220427440014946203768784045703025759870554906
       8730997341812597112663372682157620563613823265800657478189092784083
       8902658968672690403552541350336470129056725620597549670908276206541
       7068587501628939825138439023019987325228933762129472457029069742967
       7323075235457453997698335437670452249075899675829250367632092573103
       0824753018182201286807965984206118675066949091329663142338387319693
       0077429282152085813316773479333481580377768115862247570021849094533
       1765539332935696362126894458421338352187465957489123056438700490435
       9857205666787963697787968899754416478847125450852246085377612411773
       6957780124194105943264748439151047752332745314568888070235477051593
       9365660121468671404418402746186802952916298266144066854154249970112
       3653529697785843450051915147282490846251785672879851755175455347759
       0140863811842947488196506559360953743636727991374549288910341518301
       4163149003197575571831104906658958422909630822797095304606299534978
       4001319498987576822828772904982596894191469730542761856852596287142
       2887573064920981144402165317506194208100469652039975512829516769766
       8350897765718563926141743092471936664744541630149389659272359051319
       6749288596331103812064355461543768091083425915327518424749841061725
       4115888105914114750485912589768490514482066134708797269222652986780
       1977826852529088228209837598712593028712635011538286972052932028778
       1951619351053062227012190960431078972062738476819034818067222647615
       6840315295681655072630468613971563812441752962491815338623730848846
       3671618878910658051748251687047571158958633870984046091078408166081
       6008729400681877059551531966866805032014888885458040140565953077453
       1124901032767115565786520601456485716561498747421527897471456777292
       9033622932968178821832753996121415235797106352560777936960870163083
       2448201666522632764943239886543223912794494785328658241119659969012
       0750982011769523186743275772341878294791533936355560550123586692071
       0469302003385227797821485305625733046674978861689472676733492806165
       7338832191824794756141790489023818823266629986328926255511756852651
       1239954567134213931396108685134934180029252147004054282361085210539
       0747660133435120664291368449461024633400088239637147831345902469970
       6846383994876724845878629569224631303976638658680857614134689799873
       5807637602174138712908033656810647451035073702384734968153071526277
       2746753132311659825579142941572964189931907503923546394984805731560
       4704666798111703920129626872041360193147394366307270751846909834305
       9602918352430632693404890218766697584790823131571311321285701358779
       1940220978375417643810883349697544197853913478896304119838859277664
       7248540340885668203127626877601201382544380668352085729017421507219
       4366587070596313093770435645643235501280648935104969293790890409927
       0069050635477098948997959156906178633482849514588726125549767475620
       8057187214498220847695633777818624224232362625922609985742415496645
       4746393023226410618932372829291420339628385419145215636992810698393
       7975917564595654562469771625048593897907898462872376176723595651772
       2122544300803212395369696815169908600011078702014785171269191703142
       4005726278913603067294423654511237055687284643969999045740847304614
       8775684390684471353501184176211558664629758840187453656584615153000
       3695233873573037921029508572950988641548855063337628223491348148916
       0796503717077705017927663623566961326313068937877775132327648881601
       6173468650369863833254441620694578650673821422609828804067676934871
       6977702060056528855305723307043335129637834422167856472838245531474
       3055593545359216469687431985724549584483966570029902834136377954576
       3229137275480928996024300088655878664962464256636211681104186966892
       2000802082007939088324036107189498928574691785506769124870091644115
Title: Re: Sum of Powers
Post by JP05 on Oct 8th, 2007, 11:43am
continued...

  6186778488477620027247582252358374233303008055584786946434027256925
       1667614344776558083090711265779160452074252951003223832415798040225
       1721934556259446882062266351012052440017500617409062449501313426559
       3373759341762312544541907370512259988160761689083829054127706521209
       6559706693136151698985282496171948329782883209532939276617572722513
       3912295350512098242655419953426425311274447379555431248049194251844
       7578307401376023519446094153100929635926344704698410782607722281022
       5299727837403696683913460211781449329238622327434376931794148972975
       5907807785675996810671355523133277047501462127001709324404222536643
       2017032418367314388216851437827862751643504825386678349288548752096
       8485472506059749706591083796385843752345880066221551120375603953084
       5869660796861834457596457775378327114177685948136572704326822794101
       5804693372028133635537567974341143150225633441303281453177578251888
       9835385303048688716941866384973610364319649646290550369770626242036
       2577884381405185595884688746890580018291982496233121366822816317546
       0299139784099280898479908386342430339181938798437557715015741439196
       1146323893989002768444953089550206521460718897651735726276879905397
       9052100601356599101634792550282755313318892830796778201396790217372
       4409482482950021126453638490562662999954448397339039189166831799992
       5390630349674008468541750510474588576830318747360612689770794983832
       3796595862839860136927964353055179447548075051524087301269203353486
       8752727464223420924049952139178517311934039176925870823111031119683
       0153108820403376955179143736668149255675324362241514758767592238340
       9187316433725461254294075240063008810718763585705947277616419163783
       6160949617811306994475290076323796178982918708206757772190159832007
       9224729782922921429141486513206729200664214539627741172048849253769
       6214849122364192668563334168183562928874722387399108614691482385034
       3466618752731587871599703394302948206061810942656041011089976130621
       4288116843032783042012698686591107603839121572902048286835536800751
       6163756084441834034158692478056262130986915560978545349260410495900
       2365426710140383073452707479779899170196281441573207973532729591915
       5035081119651694846865247004914777573799012744855068631575204084084
       986899042353332621456794028630940532901  <--- there it is
Title: Re: Sum of Powers
Post by towr on Oct 8th, 2007, 11:49am
Why didn't you just calculate it modulo 10, that'd have saved you some paper :P
Title: Re: Sum of Powers
Post by JP05 on Oct 8th, 2007, 11:54am
I thought about that but I had plenty of paper, after all.
Title: Re: Sum of Powers
Post by SMQ on Oct 8th, 2007, 12:47pm

on 10/08/07 at 11:49:59, towr wrote:
Why didn't you just calculate it modulo 10, that'd have saved you some paper :P

For that matter, since http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(10) = 4, aa (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif [a (mod 10)a (mod 4)] (mod 10) (with the exception of 0th powers -- see posts below), so the pattern repeats every 20:

11 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 11 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 (mod 10)
22 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 22 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 4 (mod 10)
33 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 33 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 7 (mod 10)
44 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 44 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)
55 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 51 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 5 (mod 10)
66 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 62 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)
77 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 73 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 3 (mod 10)
88 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 84 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)
99 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 91 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 9 (mod 10)
1010 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 02 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0 (mod 10)
1111 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 13 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 (mod 10)
1212 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 24 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)
1313 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 31 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 3 (mod 10)
1414 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 42 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)
1515 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 53 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 5 (mod 10)
1616 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 64 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)
1717 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 71 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 7 (mod 10)
1818 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 82 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 4 (mod 10)
1919 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 93 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 9 (mod 10)
2020 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 04 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0 (mod 10)
.
 20100
So  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (x+k)x+k (mod 10) = 94 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 4 (mod 10) for any x, and  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (x+k)x+k (mod 10) = 470 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0 (mod 10) for any x
k=1k=1
.
20002001
Therefore  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif kk (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0 (mod 10), and  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif kk (mod 10) = 20012001 (mod 10) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 (mod 10)
k=1 k=1

--SMQ
Title: Re: Sum of Powers
Post by denis on Oct 8th, 2007, 1:05pm
SMQ, maybe just a typo but 44=256 so how come 44 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 (mod 10)? Should it not be 44 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 6 (mod 10)? Or does this http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif relation do something I am not aware of?
Title: Re: Sum of Powers
Post by Obob on Oct 8th, 2007, 1:43pm
It is only true that aphi(n) = 1 (mod n) if a is relatively prime to n.  So the analysis is a bit more complicated.
Title: Re: Sum of Powers
Post by SMQ on Oct 8th, 2007, 1:48pm
Yeah, fixed now -- it still works (although I have yet to find a reference to back me up I have never encountered a situation where it fails) if you avoid raising to the 0 power (i.e. use 4th powers where you would expect 0th powers).  I just forgot that step -- i.e. I'm an idiot. :-[


on 10/08/07 at 13:43:51, Obob wrote:
It is only true that aphi(n) = 1 (mod n) if a is relatively prime to n.  So the analysis is a bit more complicated.

But consecutive powers are still cyclic (obviously by pigeon-hole), and the cycle-length still divides http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif(n) for every a, it's just that the cycle may not contain a value of 1 for a not relatively prime to n.  (Right?  That's the part I can't find a reference to back me up on, but I have never discovered a case where it's not true...)

--SMQ


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board