![]() |
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:
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | … |
An | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 13 | 18 | … |
Se poate verifica că A100 = 3251 și ca A1000 = 80852364498.
Găsește ultimele 9 cifre ale sumei .