Determine the last six digits of the decimal number given by 7^(3^3002).
The extended precision of UBASIC is of use here:
The last two digits of powers of 7 repeat in a cycle of 4:
07, 49, 43, 01
The last three digits repeat in a cycle of 20, as in the following table of the last 6 digits of these powers of 7:
21 284007
41 568007
61 852007
81 136007
101 420007
121 704007
141 988007
161 272007
181 556007
201 840007
the program being:
10 for I=1 to 40*20 step 20
20 print using(8,0),I,(7^I)@1000000
30 next
From the above table, you can see that the last 4 digits repeat in a cycle of 5 * 20 = 100, so we tabulate for every 100 powers of 7:
1 7
101 420007
201 840007
301 260007
401 680007
501 100007
601 520007
701 940007
801 360007
901 780007
1001 200007
1101 620007
1201 40007
1301 460007
1401 880007
1501 300007
From this we see the last 5 digits repeat in a cycle of 5 * 100 = 500.
But we also notice that the sixth digit from the end is incremented by 1 for every repetition through the cycle of 500 terminal 5 digits, so 10 cycles of the last 5 digits will produce a repetition of the last 6 digits, so that is a cycle of 500 * 5 = 5000.
3^3002 is
2079728620300718345423798488066349561836471608956655431276203871987492001275962
90989154812574463616852290074576255353905354265133756437274517818248266136217643
56693788687777156060717839632488676063160943502334938195902355590039508301313069
00484892548305503906527600244921860564267819848672643008121931279712424696662433
90939948603503931985960890214895835288218744967738832144124766633498119800658307
22002954793923799569704901966583073300996164099418118584636877069394057598294248
13407836154017923699626628159946224932862275102842814118137581960255160611640453
96469486949288152050067178518591163815911680886987427011833813986700647016729349
48621180176650597749108280988742836198992828871786569998239204915151952573462040
80558070339442748583606309836467205614456720578377583830989982229040632017444595
04687285424957155058461739091217482769490690052807269879218870540734718594886443
96615217020591290685465755569603402429618387082668422656202519528893479645848824
51145171094521832921632693375060369253706719349376957476192658300763616503966830
89995784213848930358516776731175596309946662121602576765698018688032885248861429
00074813662311685180817679746487657489858651256268683144008352382682993538953354
63629929973858821717470208967495676929019257936278538066429572037407491929887738
67656479870881694128504272901859288632587695067456545336246109089059378918071967
83890108540085333497949726248859152147330229354934347815928186083890940009
which is congruent to 9 mod 5000.
(The same could be done on a calculator with less precision by repeated multiplication by 3 and taking mod 5000 along the way; plus some shortcut powers by factoring 3002 into 2*19*79)
So the last 6 digits of the number sought is the same as the last 6 digits of 7^9.
Since 7^9 is 40,353,607, those last 6 digits are 353607.
|
|
Posted by Charlie
on 2006-04-18 14:01:35 |
solution
