Le dragon du Fused

[Morphocode]

On prend le bandage Fused qui ne possède que trois rotations H, D, A
Soit T une formule par ex T = HA'DHDAH,
on pose T* = DA'HDHAD , on lit T à l'envers et on remplace H<->D et A<->A' .


On a une suite de formules ainsi définies:

F0 = H
F1 = H.A.D
F2 = (HAD).A.(HA'D)
F3 = (HADAHA'D).A.(HADA' HA' D)
F4= (HADAH A' DAHA DA' HA' D).A.(HADAH A' DA' HA DA' HA' D)
..... etc ....

Donc à chaqu' étape on passe de T à T.A.T*

Comme il y a un nombre fini d'états dans le Fused on tombe forcement sur un état déjà donné par une formule. La première fois qu'on tombe sur un état avec une formule déjà écrite, cette formule là se nomme dragon du Fused, par exp si à l'étape 17 on tombe (pour la 1er fois) sur l'état de F3 = (HADAHA' D).A.(HADA' HA 'D), alors le dragon du Fused est
dragon = F3 = (HADAHA' D).A.(HADA' HA' D)

Question: Trouver le dragon du Fused ==> (on peut faire un progamme informatique pour le trouver)


NOTE : Il est intéressant de savoir quelle est la longueur de Fn, |Fn| = ?? .

Spoiler: Afficher

On pose : |Fn| = un
Si on observe bien, on voit que la longueur de Fn vérifie
un+1 = 2un + 1 (2 fois avant +1 = longueur suivante)
on a donc une suite récurrente, pour trouver un en fonction de n on pose:
vn = un + 1
d'où
vn+1 = un+1 + 1 = 2un + 1 + 1
vn+1 = 2un + 2 = 2( un + 1) = 2vn
C'est une suite géométrique de raison 2, d'où
vn = = 2n v0
or vn = un + 1
d'où
un = 2n v0 - 1
or v0 = u0 + 1 = 1+1 = 2

un = 2n+1 - 1
|Fn|= 2n+1 - 1

On voit que la longueur de la formule Fn augmente très très vite ! , on se demande quelle est la longueur L du dragon ?
elle est forcement 1 ≤ L ≤ 26.

REMARQUE :
Pour les suites récurrentes de la forme
un+1 = aun + b ; a ≠ 0,1 et b ≠ 0
on utilise la stratégie suivante :
on essaie de trouver une suite géométrique vn de raison a qui relie à la suite un le plus simple possible. On pose:
vn = un + c
on cherche donc c
vn+1 = un+1 + c = aun + b + c
vn+1 = avn
a(un + c) = aun + b + c
aun + ac = aun + b + c
d'où
ac = b + c
c = b/(a-1)

d'où
vn = un + b/(a-1)
Une fois trouvé vn, on trouve alors un

vn = anv0
un = anv0 - b/(a-1)
et
v0 = u0 + b/(a-1)