suite d’Hofstadter

ANALYSE

La suite d’Hofstadter est définie par ses deux premiers termes et une relation de récurrence faisant intervenir des termes précédents (mais pas les deux immédiatement précédents).
u(1) = u(2) = 1 et pour n > 2, u(n) = u(n-u(n-1)) + u(n-u(n-2))

Les premiers termes de cette suite sont :
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, 14, 16, 16, 16, 16, 20, 17, 17, 20, 21, 19, 20, 22, 21, 22, 23, 23, 24, 24, 24, 24, 24, 32, 24, 25, 30, 28, 26, 30, 30, 28, 32, 30, 32, 32, 32, 32, 40, 33, 31, 38, 35, 33, 39, 40, 37, 38, 40, 39