Calcul du maximum d'une somme de composantes

Gimli

Bonjour,

J'ai un problème qui me semble compliqué. Je ne sais pas comment l'aborder.

J'ai un vecteur de taille $N$ où toutes les composantes $x_2$, $x_3$, ..., $x_N$ sont égales à $0$, sauf la première $x_1$ qui a pour valeur entière positive $k<N$, telle que $k$ s'écrit comme une puissance de $2$.

J'ai un algorithme qui se déroule de la manière suivante :

1) Soit $i$ le plus grand indice tel que $x_i \geq 2$ :
1.1) Si $x_i \geq 4$, alors :
1.1.1) $x_i=x_i-4$
1.1.2) $x_{i+1}=x_{i+1}+2$
1.2) Sinon, si $2 \leq x_i \leq 3$ alors :
1.2.1) $x_i=x_i-2$
1.2.2) Soit $j$ le plus grand indice tel que $x_j \geq 2$ :
1.2.2.1) $x_j = x_j - 2$
1.2.2.2) $x_{j+1} = x_{j+1} + 1$
1.2.2.3) $x_{i+1} = x_{i+1} + 1$
2) Retourner au point 1)

Cet algorithme se termine lorsque toutes les composantes sont nulles sauf une seule qui doit valoir $1$.

Je cherche à déterminer la valeur maximale que peut prendre $\sum_{i=2}^N x_i$, sur toutes les étapes.

Y aurait-il des heuristiques pour obtenir une valeur approchée de ce maximum ?

Je vous remercie pour votre aide.

Gimli