Bonjour,
je suis en fait informaticienne, mais j'ai un problème mathématique à résoudre.
Alors je considère l'espace des nombre entiers.
Je fixe un nombre N d'éléments (par exemple 1000000) (et donc je travaille sur les éléments de 1 à N-1, ou de 0, ce n'est pas trés important).
A partir de là, je construis un graphe de la façon suivante (une skip-Liste binaire si vous connaissez) :
L'axe des ordonnées contient les nombres entiers à traiter.
L'axe des y correspond aux niveaux de l'élément.
Tous les éléments appartiennent au niveau 0.
Les autres niveaux de l'éléments sont déterminés de la façon suivante: si x est divisible par 2, alors il appartient au niveau 1,
s'il est divisible par 4 ( 2 puissance 2), alors il appartient au niveau 2, s'il est divisible par 8 (2 puissance 3)alors il appartient au niveau3... jusqu'au niveau maximal de l'élement qui correspond à log2(x) si x est une puissance de 2.
Ainsi, les éléments impairs n'appartiennent qu'au niveau 0.
l'elément 6 appartient aux niveaux 0 et 1.
8 appartient aux niveaux 0, 1, 2 et 3.
Ma question est la suivante:
je veux déterminer le nombre d'éléments que je parcourt si je traverse le graphe de la façon suivante:
je pars d'un élément x donné et je veux arriver à l'élément N.
Je prends le niveau le plus haut auquel appartient l'élément x
(par exemple 3 pour l'élément 8).
et je regarde le successeur au meme niveau ( ca me donnera 16).
Maintenant je prends l'élément 16 (niveaux 0,1,2,3,4).
Je prends le niveau le plus haut auquel il appartient et je regarde le successeur, ca me donne 32.
Maintenant je prends l'élément 32(niveaux 0,1,2,3,4,5).
Je prends le niveau le plus haut auquel il appartient, soit 5, et je prends le successeur, soit 64 et ainsi de suite.
l'élément 8 étant un cas particulier, je prends un autre exemple.Soit l'élément 5 (niveau 0), son successeur est donc 6.
6 (niveau 0 et 1) a pour successeur de haut niveau (niveau 1) 8.
ensuite pour l'élément 8 celà se passe comme décrit précédemment.
Ce dont j'ai besoin en premier lieu, c'est le nombre d'éléments traversés pour arriver à N.
Etant informaticienne, j'arrive à créer un programme qui permet de calculer ce nombre pour x et N donnés.
Mais ce dont j'ai besoin c'est une formule mathématique ou, faute de pouvoir le faire, une formalisation mathématique du problème.
Une fois ce nombre calculer, mon but était de pouvoir démontrer l'hypothèse suivante:
Pour N donné, il n'existe pas d'éléments x1 et x2 telque:
1. x1 est différent de x2
2. x1 et x2 ont le même niveau maximal (par exemple 4 et et 12 car 4 appartient aux niveaux 0, 1 et 2 et pareil pour l'lémément 12)...
3.les niveaux maximaux de la skip Liste lors de l'insertion de x1 et lors de l'insertion de x2 sont égaux. Par exemple, si j'insère 7, le niveau maximal de la skipListe est 2 ême si 7 n'appartient qu'au niveau 0( car 4 a déjà été inésré et il appartient aux niveaux 0, 1 et 2). Si j'insère 8, le niveau maximal de la skipListe est égale au niveau de l'élément inséré et est égale à 3. Si j'insère 9 le niveau de l'élément est 0 et le niveau de la skip Liste est 3...
4. Le nombre de successeurs de x1 et de x2 est égal.
5. tout ceci est récursif.
Par exemple:
si je prends x1=11, x2=13 et N=16
alors 11->12->16
et 13->14->16
A la première itération on a 11 différent de 13, 11 et 13 appartiennent tous les deux uniquement au niveau 0 et finalement le niveau maximal lors de leurs insertions était 3 (correspondant à l'élément 8).
Maintenant je prends x1=12 (le seccesseur de 11)
et x2=14 (le successeur de 13)
alors on a:
12 appartient aux niveaux (0, 1 et 2) alors que 14 n'appartient qu'aux niveaux (0 et 1).
Ce qui rejoint notre hypothèse.
Je pense en fait à une suite numérique mais je n'arrive pas à formaliser.
On pourrait alors soit travailler en base 2, ou travailler à l'échelle logarithmique.
Ce sont deux pistes ùais je n'arrive à faire aboutir aucune d'entre elles.
Pourriez vous m'aider??
Je vous remercie d'avance pour votre attention et votre aide et espère avoir été assez claire.
Je me tiens à votre disposition pour toute information supplémentaire.
Merci pour tout.
-----
Envoyé par craz_rose 
