RSS Feed
Precedenta

Problema 361

04 Decembrie 2011

Subșir al șirului Thue-Morse


Șirul Thue-Morse {Tn} e un șir binar care satisface:

  • T0 = 0
  • T2n = Tn
  • T2n+1 = 1 - Tn

Primii câțiva termeni ai lui {Tn} sunt:
01101001100101101001011001101001....

Fie {An} șirul de numere întregi sortate astfel încât reprezentarea lor binară apare ca subșir in {Tn}.
De exemplu, numărul zecimal 18 e scris 10010 în baza 2. 10010 apare în {Tn} (de la T8 la T12), deci 18 e un termen al șirului {An}.
Numărul zecimal 14 e scris 1110 în baza 2. 1110 nu apare deloc în {Tn}, deci 14 nu e un termen al șirului {An}.

Primii câțiva termeni ai șirului An sunt:

n0123456789101112
An012345691011121318

Se poate verifica că A100 = 3251 și ca A1000 = 80852364498.

Găsește ultimele 9 cifre ale sumei .


>> Vezi problema originală <<