Problema #6 – Află ultimele trei cifre ale sumei puterilor lui 7

Aflați ultimele trei cifre ale numărului:

N = 7^1 +7^2 + 7^3 + ....+ 7^{2008}.

Observăm că:

7^1 + 7^2+7^3+7^4 = 7 +49 +343+2401=350+2450=2800

Vom grupa termenii lui N câte patru pentru a putea să-i dăm factor comun de două ori: o dată cea mai mică putere din grupa de patru, apoi suma puterilor lui șapte de la unu la patru.

N= 7^1 +7^2 + 7^3 + ....+ 7^{2008}  {\implies} \\\;\\\\\implies N=(7^1 + 7^2+7^3+7^4) + 7 ^4\cdot(7^1 + 7^2+7^3+7^4)+...\\\;\\\;\;\;\;\;\;\;\;\;\;\;\;+...+7^{2004}\cdot(7^1 + 7^2+7^3+7^4) \implies\\\;\\\\\implies N=(7^1 + 7^2+7^3+7^4) \cdot( 1 + 7 ^4+...+7^{2004})\implies \\\;\\\\\implies N = 2800\cdot ( 1 + 7 ^4+7 ^8+7 ^{12}+...+7^{2004})\implies\\\;\\\\\implies N = 2800+2800\cdot ( 7 ^4+7 ^8+7 ^{12}+...+7^{2004})\implies \\\; \\\\\implies N = 2800+2800\cdot [ 7 ^4\cdot(1+7 ^4+7 ^{8}+...+7^{2000})]

Notăm cu U₃(N) ultimele 3 cifre ale numărului N și observăm că ultimele trei cifre ale produsului 2800 cu 7 la puterea 4 sunt 800.

 N = 2800+2800\cdot [ 7 ^4\cdot(1+7 ^4+7 ^{8}+...+7^{2000})] = \\\;\\=2800+2800\cdot  7 ^4 + 2800\cdot  7 ^4\cdot(7 ^4+7 ^{8}+...+7^{2000})

 U_3(2800\cdot 7 ^4 )= 800\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\\\\;\\
 U_3(800\cdot 7 ^4 )= 800\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\\\\;\\
U_3(N) =   \\\;\\
 = U_3(2800) +  U_3(2800⋅7^4)+ U_3(2800⋅7^4)\cdot U_3(7 ^4+...+7^{2000}) = \\ \;\\=800+800+800\cdot U_3(7 ^4+7 ^{8}+...+7^{2000})= \\\;\\= 800  +800+ 800\cdot U_3( 7 ^4\cdot(1+7 ^4+7 ^{8}+...+7^{1996})) = \\\;\\=800 + 800+800\cdot U_3(  7 ^4) +800\cdot U_3(7 ^4+7 ^{8}+...+7^{1996})) = \\\;\\=800+800+800\cdot U_3(  7 ^4)+800\cdot U_3(  7 ^4\cdot(1+7 ^4+...+7^{1992})) =\\\;\\=...=U_3(800\cdot502) =1600 \implies \\\;\\\implies U_3(N)=600

Later Edit

Inițial ne-a dat 800, dar am verificat cu programul python de mai jos…. Calculasem greșit numărul de numere adunate care se termină în 800…

def main():

    N=0
    t=1
    idx=0
    while idx < 2008:
        idx = idx + 1
        t = t * 7
        N = N + t

    print(N%1000)


if __name__ == "__main__":
    main()

Ca o curiozitate, rezultatul sumei este:

105635803065330843019975725783385147304213157992326374862148877061623927031494399923623618364503782494957543048909059904902606231142474598551480377411060052693373269571689077951061297541906489954304794656884794575237020381173469579041985576661647778474116623481271291893340352800884595910044512105642375708910279914558654422519671393063166574235038665440452695274277448684591456852835441590087268568728147218392875154426282384011886558312730816556611990784492997665205328121394502230340633734342506583442687231317631237414382052269896746204791976188282371273008982071184997890940138155353801147589966915683894773818043327884021415831766620162641199873117163800340650421802137427895635349596865206822062498260645205481516477507484189785982264578369447186796004073972681094131561620882338810182129848931403359147679376764378213425511915055431464277184646585807417325470827046590131563818558698621245029677527077205379286761438598239168823880431527706076508209536256041939323373212586418262111215265688288589146505565248819366917519981600351672277051896525665527456140386738728863984265444991036282135890962343352563476352729048356829449736339390400641375255626309988418623057358785141682387771667282299338124714840282840030634265566760864057468855639589459028508237178778904437008641544324040404665940217003133101044772939016420373374876916298682240289263020963253067469096367922039381272341559186793838904092839904369736913680425898874696100191788815179239072163048908995981948052290599945755948005856167882830147170395132294973932164568218162123105611219220033315055562124012826727189207821166205381161661654821500172796153909847040090929644057894330713969511624095214612779187444015894733048125600