Suite de Prouet-Thue-Morse

La suite de Prouet-Thue-Morse est une suite de chiffres 0 ou 1. Le premier chiffre de la suite, t(0) vaut 0. Les autres chiffres sont définis par récurrence : t(2n)=t(n) et t(2n+1)=1-t(n).

Le début de la suite est : 0110100110010110

Si on extrait les chiffres t(6) à t(11), ils forment la séquence 011001, qui peut être interprêtée comme un nombre écrit en binaire, dont la valeur, écrite en base 10 est 25 (représentation des nombres en binaire).

Les entrées du problème sont deux indices n1 et n2 (n2>n1). Vous devez répondre en donnant (en base 10) la valeur du nombre représenté par les chiffres t(n1) à t(n2). Si l'entrée était (n1=6,n2=11), vous devriez répondre 25.

Le coin tuto

Changement de base

Python propose quelques fonctions de changement de base. bin et hex transforment un nombre entier en une chaîne de caractère contenant la représentation du nombre en binaire ou héxadécimal. De son côté, int transforme une chaîne en entier, et on peut préciser la base :

>>> bin(25)
'0b11001'
>>> bin(25)[2:]
'11001'
>>> hex(25)
'0x19'
>>> int("19",16)
25