Author |
Topic: Sum of Powers (Read 1188 times) |
|
tony123
Junior Member
Posts: 61
|
 |
Sum of Powers
« on: Oct 5th, 2007, 2:54pm » |
 Quote  Modify
|
Find the last decimal digit of the sum 1^1 + 2^2 + 3^3 + ... + 2001^2001
|
|
 IP Logged |
|
|
|
JP05
Guest
|
I found it = 1.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Sum of Powers
« Reply #2 on: Oct 6th, 2007, 11:16am » |
Quote Modify
|
That's right, "1^1 + 2^2 + 3^3 + ... + 2001^2001" ends with a 1. 
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sum of Powers
« Reply #3 on: Oct 7th, 2007, 3:37pm » |
Quote Modify
|
Prove it.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JP05
Guest
|
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
|
|
IP Logged |
|
|
|
JP05
Guest
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum of Powers
« Reply #6 on: Oct 8th, 2007, 11:49am » |
Quote Modify
|
Why didn't you just calculate it modulo 10, that'd have saved you some paper 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JP05
Guest
|
I thought about that but I had plenty of paper, after all.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum of Powers
« Reply #8 on: Oct 8th, 2007, 12:47pm » |
Quote Modify
|
on Oct 8th, 2007, 11:49am, towr wrote:| Why didn't you just calculate it modulo 10, that'd have saved you some paper |
|
For that matter, since  (10) = 4, aa (mod 10)  [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) 11 (mod 10) 1 (mod 10)
22 (mod 10) 22 (mod 10) 4 (mod 10)
33 (mod 10) 33 (mod 10) 7 (mod 10)
44 (mod 10) 44 (mod 10) 6 (mod 10)
55 (mod 10) 51 (mod 10) 5 (mod 10)
66 (mod 10) 62 (mod 10) 6 (mod 10)
77 (mod 10) 73 (mod 10) 3 (mod 10)
88 (mod 10) 84 (mod 10) 6 (mod 10)
99 (mod 10) 91 (mod 10) 9 (mod 10)
1010 (mod 10) 02 (mod 10) 0 (mod 10)
1111 (mod 10) 13 (mod 10) 1 (mod 10)
1212 (mod 10) 24 (mod 10) 6 (mod 10)
1313 (mod 10) 31 (mod 10) 3 (mod 10)
1414 (mod 10) 42 (mod 10) 6 (mod 10)
1515 (mod 10) 53 (mod 10) 5 (mod 10)
1616 (mod 10) 64 (mod 10) 6 (mod 10)
1717 (mod 10) 71 (mod 10) 7 (mod 10)
1818 (mod 10) 82 (mod 10) 4 (mod 10)
1919 (mod 10) 93 (mod 10) 9 (mod 10)
2020 (mod 10) 04 (mod 10) 0 (mod 10)
| | 20 | 100 | | So |  (x+k)x+k (mod 10) = 94 4 (mod 10) for any x, and | (x+k)x+k (mod 10) = 470 0 (mod 10) for any x | | | k=1 | k=1 |
| | 2000 | 2001 | | Therefore | kk (mod 10) 0 (mod 10), and | kk (mod 10) = 20012001 (mod 10) 1 (mod 10) | | | k=1 | k=1 |
--SMQ
|
| « Last Edit: Oct 8th, 2007, 1:56pm by SMQ » |
IP Logged |
--SMQ
|
|
|
denis
Uberpuzzler
Gender:
Posts: 1222
|
|
Re: Sum of Powers
« Reply #9 on: Oct 8th, 2007, 1:05pm » |
Quote Modify
|
SMQ, maybe just a typo but 44=256 so how come 44 1 (mod 10)? Should it not be 44 6 (mod 10)? Or does this relation do something I am not aware of?
|
| « Last Edit: Oct 8th, 2007, 1:41pm by denis » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Sum of Powers
« Reply #10 on: Oct 8th, 2007, 1:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum of Powers
« Reply #11 on: Oct 8th, 2007, 1:48pm » |
Quote Modify
|
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 Oct 8th, 2007, 1:43pm, 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 (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
|
| « Last Edit: Oct 8th, 2007, 1:57pm by SMQ » |
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove