====== Suite du feu de forêt ======

Il s'agit d'une suite numérique dont la représentation graphique évoque un panache de fumée au-dessus d'un incendie, d'où le nom.

===== Définition mathématique =====

<WRAP box>
$\left(u_n\right)_{n\geq 0}$ dont les valeurs sont toutes dans dans $\mathbb{N}$.

Pour chaque valeur de $u_n$ on choisit la valeur la plus petite pour que, pour $1 \geq k \geq \frac{n}{2}$, $u_n$ ne soit jamais en progression arithmétique avec $u_{n-2k}$ et $u_{n-k}$.
</WRAP>

===== Calcul des premiers termes =====

Bon... dit comme ça c'est très abstrait alors construisons les premiers termes pour comprendre.

Pour $u_0$ et $u_1$ on peut choisir $0$ sans contrainte. C'est à partir de $u_2$ que la contrainte commence à se poser.

**Calcul de $u_2$**

La contrainte exclut des valeurs. La contrainte s'exprime pour tous les $1 \geq k \geq \frac{n}{2}$. Donc ici, on seulement $k=1$.
 
Pour chaque valeur de $k$, il faut envisager $u_{n-2k}$ et $u_{n-k}$ et exclure le terme suivant...

  * avec $k = 1$ on regarde $u_{2-2\times 1} = 0$ et $u_{2- 1} = 0$. 0, 0, ... $u_2$ ne pourra pas être égal à 0.

//En effet, si $u_2$ était égal à 0, cela ferait 0, 0, 0 ce qui serait une progression arithmétique (+ 0 à chaque fois)//

C'était la seule contrainte. On doit choisir pour $u_2$ le plus petit entier acceptable. Donc $u_2 = 1$.

**Calcul de $u_3$**

Là encore, on a seulement $k = 1$.

  * $k = 1$ : $u_{3-2\times 1} = 0$ et $u_{3- 1} = 1$. 0, 1, ... $u_3$ ne pourra pas être égal à 2.

//En effet, si $u_3$ était égal à 2, cela ferait 0, 1, 2 ce qui serait une progression arithmétique (+ 1 à chaque fois)//

On doit choisir $u_3 = 0$

**Calcul de $u_4$**

  * $k = 1$ : $u_{4-2\times 1} = 1$ et $u_{4- 1} = 0$. 1, 0, ... $u_4$ ne pourra pas être égal à -1.
  * $k = 2$ : $u_{4-2\times 2} = 0$ et $u_{4- 2} = 1$. 0, 1, ... $u_4$ ne pourra pas être égal à 2.

On doit choisir $u_4 = 0$

**Calcul de $u_5$**

  * $k = 1$ : $u_{5-2\times 1} = 0$ et $u_{5- 1} = 0$. $\Rightarrow$ 0 exclu.
  * $k = 2$ : $u_{5-2\times 2} = 0$ et $u_{5- 2} = 0$. $\Rightarrow$ 0 exclu.

$u_5 = 1$

**Calcul de $u_6$**

  * $k = 1$ : $u_{6-2\times 1} = 0$ et $u_{6- 1} = 1$. $\Rightarrow$ 2 exclu.
  * $k = 2$ : $u_{6-2\times 2} = 1$ et $u_{6- 2} = 0$. $\Rightarrow$ -1 exclu.
  * $k = 3$ : $u_{6-2\times 3} = 0$ et $u_{6- 3} = 0$. $\Rightarrow$ 0 exclu.

$u_6 = 1$

**Calcul de $u_7$**

  * $k = 1$ : $u_{7-2\times 1} = 1$ et $u_{7- 1} = 1$. $\Rightarrow$ 1 exclu.
  * $k = 2$ : $u_{7-2\times 2} = 0$ et $u_{7- 2} = 1$. $\Rightarrow$ 2 exclu.
  * $k = 3$ : $u_{7-2\times 3} = 0$ et $u_{7- 3} = 0$. $\Rightarrow$ 0 exclu.

$u_7 = 3$

etc.

===== Observations =====

Comme vous le constatez, on commence par faire une liste de valeurs exclues puis on prend le petit entier positif qui n'est pas exclu.

On voit que pour $u_n$ on a $n \div 2$ contraintes, ce qui va exclure au pire $n \div 2$ entiers différents. Donc il suffit de chercher de $0$ à $n \div 2$ compris pour trouver le plus entier qui n'est pas exclu.

Dit autrement, on est certain que $u_n \leq n \div 2$.

===== Implémentation =====

Vous allez pouvoir procéder ainsi :

  * On se fixe un nombre ''N'' de termes à calculer. Par exemple ''N = 100'' dans un premier temps et quand on est sûr que cela fonctionne bien, on peut passer à ''N = 10000'' (temps de calcul beaucoup plus long !)
  * La suite sera stockée dans une liste ''u''. On pourra initialiser ''u = [0, 0]'' pour les deux premiers termes.
  * Pour chaque nouveau terme, on commence par produire la liste des exclus. Puis on cherche le plus petit entier qui n'est pas exclu. Enfin on ajoute ce résultat à la suite de ''u''

Quand on a ''u'', il faut l'afficher :

<code python>
import matplotlib.pyplot as plt

plt.plot(u, 'o') # 'o' pour n'afficher que des points non reliés
plt.show()
</code>