La suite du lézard est une suite infinie, composée de 0 et de 1 uniquement, et a la remarquable propriété suivante :
Si on retire de la suite les termes de rang 3, 6, 9, etc, ce qui reste est la suite elle-même. De même, les nombres enlevés forment la même suite. Il existe deux suites non triviale (non triviale = qui contient à la fois des 0 et des 1). L'une commence par 0, et l'autre par 1. Voici le début de la suite qui commence par 0 :
0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1
0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0
0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
En ne lisant que les caractères en gras, vous retrouvez la suite complète. En lisant uniquement les caractères qui ne sont pas en gras, vous retrouvez aussi la suite complète.
Dans ce défi, on vous donne en entrée le rang d'un des termes de la suite (par exemple 11). Relevez les 16 chiffre binaires à partir de ce rang. Dans l'exemple du rang 11, cela donne : 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1. La suite obtenue est l'écriture en binaire d'un nombre compris entre 0 et 65535. Dans le cas du rang 11, le nombre obtenu est 34061. C'est ce nombre que vous devez fournir en sortie.