Cherche formule - puissance de deux - tableau - arbre

Umbre

Bonjour, je code un petit logiciel sur mon temps libre et je connais peu de choses en maths. Je bloque sur un problème.
Je remplis un tableau imaginaire de n lignes de la façon suivante (ici  n=6 dans mon exemple).


Avec n devenant assez grand, disons n=64 par exemple, si je tire un nombre au hasard entre 1 et 2^n - 1 (nombre de cases du tableau), ai-je un moyen simple de calculer sur quelle ligne il se trouve et dans quelle case ? Et dans l'autre sens, si j'ai un numéro de ligne et une case, puis-je calculer facilement quel nombre elle contient ?
Peut-être est-ce un problème très simple, mais je ne sais pas faire (sauf en générant le tableau case par case jusqu'au nombre ou jusqu'à la position visée).
Merci de l'aide que vous pourrez m'apporter,
Bien à vous.

gerard0

Bonjour.

As-tu essayé d'écrire tes nombres en binaire ?

Cordialement.

LEG

Bonjour 

1) C'est le nombre de cases par ligne qui est égal à  2 puissance n par ligne et non les nombres que tu mets dans les cases ! 
2) Quel rapport on tes nombres par rapport aux cases  et par ligne ?
3) Tes lignes sont numérotées en partant de 0 ce qui te donne bien $2^{0}=1$ ; ligne 0 égale une case ... puis ligne 1 = 2 cases..etc
4) Donc avec $n = 64$ lignes tu as bien $2^{64}$ cases pour la ligne 64 et tu veux savoir dans la nième case de la 64 ème ligne , quel est le nombre que tu as mis ... en vertu de quoi ?
5) Pourquoi à la ligne  n°1 , où il y a 2 cases, tu as placé $33 = 2^{5} + 1$ ?  Alors que tu parles de nombres qui valent $2^{n} - 1$....?

Commence par expliquer ce que tu fais, avec tes nombres, case par case ; de la ligne zéro à la ligne $n = 5$ et non comme tu le dit $n = 6$ ... Peut être que l'on y verra plus clair.... 

lourrran

Le fonctionnement est assez clair.
Pour remplir une case de la ligne n, il faut d'abord avoir rempli les cases 'au-dessus'.
Et on essaie de remplir la dernière ligne, de gauche à droite, avec cette contrainte.

Pour trouver en quelle ligne et quelle colonne se trouve un nombre,un algorithme par dichotomie va fonctionner.

Exemple, on cherche 43
Sur ton exemple avec 6 lignes : 
Si le nombre cherché est 1, il est en ligne 1 , colonne 1
S'il est plus grand que 32, il est dans la partie droite du tableau.
Dans la partie droite, on a 33 en haut, et on a 2 moitiés : les nombres entre 34 et 48, puis ceux entre 49 et 63
33 est le 2ème nombre de la ligne 2, ses 2 enfants directs sont les 3ème et 4ème nombres de la ligne 3.
Le nombre cherché 43 n'est pas le sommet de ce petit arbre, il n'est donc pas en ligne 2
Et à partir de la ligne 3, on a 3 petits arbres (chapeautés par 3,18, 34, 49) 
Le nombre cherché 43 est dans le 3ème arbre, celui chapeauté par 34, parce que 43 est entre 34 et 49.
34 est le 3ème nombre de la ligne 3 ; ses 2 enfants directs sont les 5ème et 6ème nombres de la ligne 4.
Cet arbre se divise à son tour en 2 arbres, chapeautés par 35 et par 42  (les points de la 4ème ligne) 
42 est le 6ème nombre de la ligne 4, ses 2 enfants directs sont les 11ème et 12ème nombre de la ligne 5
43 étant plus grand que 42, il est dans le sous-arbre chapeauté par 42
Et il est le premier élément de cet arbre...
43 est le 11ème nombre de la ligne 5.

Ca se programme '''assez facilement''' si on a une grande expérience de programmation !
    
Et dans l'autre sens, à partir d'un numéro de ligne et de colonne, reconstituer le nombre qui se trouve à cette case, pareil, il faut s'appliquer en programmant ça.

lourrran

Je complète un peu.
N=6 : le nombre de lignes du tableau 
Dans la partie droite, on a 33 en haut, 

Ce nombre 33 ne vient pas de nulle part. C'est $2^{N-1}+1$

A partir d'un noeud quelconque, on a 2 enfants. Quels sont les n° de ces 2 enfants ?

$x$ = le noeud de départ (33 par exemple)
$i$ = la ligne correspondante (i=2 dans ce cas)
Le premier enfant est forcément $x+1$
Et l'autre enfant est $x +  2^{N-i}$

Les 2 enfants de $1$ sont $1+1$ et $1+2^{6-1}$ car $1$ est en ligne 1
Les 2 enfants de $33$ sont $33+1$ et $33+2^{6-2}$ car $33$ est en ligne 2
Les 2 enfants de $34$ sont $34+1$ et $34+2^{6-3}$ car $34$ est en ligne 3

Médiat_Suprème

@Umbre :

Je suppose que cette façon de remplir le tableau est impérative, sinon, il y a d'autres méthodes beaucoup plus simples.
Cette façon de faire a un défaut : on ne peut pas construire le tableau à 6 lignes à partir du tableau à 5 lignes, il faut tout casser et recommencer.
Vous devriez étudier les différences entre une cellule et la cellule à sa gauche, les cellules de gauche étant faciles à calculer..

jmf

@Umbre

Voilà un problème intéressant. Je ne fais que le reformuler avec un vocabulaire adapté.

On a ici un arbre binaire complet de hauteur $h=6$. Il est donc constitué de $2^h-1=63$ étiquettes.

Si on parcourt cet arbre en profondeur (DFS = "Deep First Search"), on obtient les étiquettes successives $a_1,a_ 2, a_3, \ldots, a_{63}$ (ici $a_i=i$ mais c'est pas le plus important).

Si on le parcourt en largeur (BFS = "Breadth First Search"), on obtient $b_1=a_1,b_2=a_2,b_3=a_{33},b_4=a_{3},b_5=a_{18},\ldots,b_{62}=a_{62},b_{63}=a_{63}$.

Ainsi $b_{i}=a_{\sigma(i)}$, où $\sigma$ est une permutation de $E_n=\{1,2,\ldots,n\}$

Si on caractérise cette permutation (et son inverse), on doit pouvoir répondre à la question posée.

LEG

lourrran a dit :

Je complète un peu.
N=6 : le nombre de lignes du tableau 

    : Quel est le nombre dans la case n° 18014398509481084... à la ligne $2^{55}$ 

Je pense que même si ta méthode marche... @Médiat_Suprème à mis le doigt sur le problème et qu'il faut tout refaire ...

En appliquant une méthode permettant d'inscrire la véritable valeur de la case N° x par rapport à la ligne $2^{n}$ sachant que les lignes sont numérotés de 0 à n ;  ce qui permet de connaître le nombre de cases par ligne et donc dans chaque moitié du tableau.... d'après le sujet qui est  posé...

@lourrran , car  je ne suis pas tout fait de ton avis ...mais c'est un détail je peux me tromper ... :

Les 2 enfants de 1 sont 1+ $2^{0}$  et 1+$2^5$  car 1 est en ligne 0  ..... et en vertu de quoi ?
 
car si (je suppose ) il y avait eut 8 lignes donc la ligne N° 7 donne 128 cases alors dans la 128 ème il aurait inscrit 256-1 = 255 ...? et quel nombre dans la case 2 ,  ligne n° 1...?

Umbre

Bonjour, merci d'avoir pris le temps de me répondre.

@LEG
Pardon de ne pas avoir été assez précis. Dans mon esprit n est le nombre de lignes que possède le tableau. Le tableau donné en exemple possède bien 6 lignes, donc n=6. Il possède bien au total (2^6) -1 = 63 cases. Par ailleurs, ces cases contiennent bien tous les nombres entre 1 et 63, mais rangés dans un ordre bien précis.
Voilà ce que je peux affirmer :

1) Le tableau possède n lignes.
2) Le tableau possède (2^n) -1 cases.
3) Si les lignes sont numérotées de 0 à n-1, alors une ligne p possède bien 2^p cases, comme tu l'as dit.
4) Les cases contiennent tous les entiers compris entre 1 et (2^n) - 1.
5) Ces nombres sont placés dans un ordre précis que je ne saurais pas expliquer simplement. Pour comprendre, regarder l'exemple est plus simple. Il suffit de remarquer la position du nombre 1, puis du nombre 2, puis 3, 4, 5... etc dans l'ordre. Vous comprendrez vite la logique de remplissage.

Je cherche une relation mathématique simple entre un nombre et sa position (ligne et case si possible) dans le tableau, cette relation est nécessairement dépendante de n, comme l'a remarqué @mediat_Suprème. Cette façon de remplir est importante pour moi, mais elle n'aura d'intérêt que si je trouve une relation simple et peu calculatoire entre un nombre et sa position (au moins la ligne).

Le voici en binaire, selon la suggestion de @gerard0

Merci encore de votre aide,
Je vous souhaite une bonne journée.

PS : Pardon, beaucoup d'autres réponses ont été données pendant que je rédigeais mon message, je dois aller travailler, mais je lirai tout cela avec attention ce soir.

jmf

Je sais pas si ça fait avancer le schmilblick, mais voici du code OCaml pour jouer avec ça.

Tout d'abord la définition du type arbre binaire (avec des étiquettes de type 'a non spécifié):

type 'a arbre = | Vide | Noeud of ('a arbre) * 'a * ('a arbre);;

Ensuite une fonction pour créer un arbre binaire complet de hauteur $h$ sur les étiquettes $1,2,\ldots,2^h-1$ (mais attention, c'est dans l'ordre croissant pour le parcours en largeur).

let complet h =
  let rec aux e h = match h with
    | 0 -> Vide
    | _ -> Noeud(aux (2*e) (h-1), e, aux (2*e+1) (h-1))
  in aux 1 h;;

La fonction suivante donne la liste des étiquettes d'un arbre binaire dans un parcours en profondeur:

let en_profondeur a =
  let rec aux l a = match a with
    | Vide -> l
    | Noeud(g, e, d)
      -> e :: aux (aux l d) g
  in aux [] a;;

Enfin la fonction suivante renvoie la liste des étiquettes de l'arbre fabriqué par la fonction complet, mais quand on le parcourt en profondeur. Cela va donc nous donner la permutation inverse de la permutation $\sigma$ dont je parle dans mon précédent message.

let permut n = en_profondeur (complet n);;

Par exemple, avec un arbre complet de hauteur 4:


permut 4;; - : int list = [1; 2; 4; 8; 9; 5; 10; 11; 3; 6; 12; 13; 7; 14; 15]

# permut 5;;

- : int list = [1; 2; 4; 8; 16; 17; 9; 18; 19; 5; 10; 20; 21; 11; 22; 23; 3; 6; 12; 24; 25;  13; 26; 27; 7; 14; 28; 29; 15; 30; 31]

# permut 6;;

- : int list = [1; 2; 4; 8; 16; 32; 33; 17; 34; 35; 9; 18; 36; 37; 19; 38; 39; 5; 10; 20;  40;

                   41; 21; 42; 43; 11; 22; 44; 45; 23; 46; 47; 3; 6; 12; 24; 48; 49; 25;

                   50; 51; 13; 26; 52; 53; 27; 54; 55; 7; 14; 28; 56; 57; 29; 58; 59; 15; 30; 60; 61; 31; 62; 63]

Voila, c'était pour jouer avec cette question, et si ça peut donner des idées....

lourrran

LEG, avec 6 lignes, le 2ème nombre de la 2ème ligne est $2^{6-1}+1$
Et plus généralement , avec N lignes, le 2ème nombre de la 2ème ligne est $2^{N-1}+1$

Quel est le nombre dans la case n° 18014398509481084... à la ligne $2^{55} $?
Ca dépend !
La donnée essentielle, c'est le nombre total de lignes.
Par exemple, s'il y a 100 lignes, la ligne n°80 commence par 80.
A chaque nouveau terme, on ajoute $2^{21}-1+k$ 
Pourquoi 21 et comment déterminer $k$ ?
Pourquoi 21 : parce qu'on est en ligne L=80, sur un total de N=100 lignes : $21= N-L+1$
k(i)=alternativement 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4 ...
k(i) est la valuation 2-adique de i.

Donc par exemple, le 1000ème terme de la ligne 80, sur un tableau de 100 lignes, ce serait $80 + 1000*(2^{21}-1)$ + la somme des $v_2(i)$ pour i entre 1 et 1000-1
Et cette somme, elle se calcule assez bien.

Certes, si la question était différente, si on remplissait ligne par ligne, l'exercice serait beaucoup plus facile. 
Mais Umbre n'aurait pas posé la question.

Bon...tout ça, c'est écrit à la volée... ... sans grandes vérifications. Si on a 10 lignes et qu'on est en ligne 80, est-ce qu'on ajoute $2^{21}-1+k$ ou $2^{20}-1+k$ entre 2 termes consécutifs ? Il me semble que c'est la 1ère proposition, mais il faudrait s'appliquer un peu pour l'affirmer avec certitude.
Et idem, il peut y avoir ici ou là des imprécisions.

LEG

Ok Lourrran ; 

Mais il y a un problème , c'est que :
Umbre se trompe ...! 

2) Le tableau possède (2^n) -1 cases. Non ! faux . c'est $2^n$ cases, tu n'as qu'à les compter ...!

3) Si les lignes sont numérotées de 0 à n-1 , Faux !  pourquoi de 0 à n-1 ? de 0 à n point barre ... Ne confond pas avec ton dernier nombre,  qui lui est = à :  $2^{n} -1$ = $2^{6} - 1 = 63$

qu'il indique l'ordre précis qu'il a utilisé dans les différentes cases , 32 dans une première partie du tableau car il y a 32 cases ...etc  
Comment tu as défini l'ordre précis de ses 32 valeurs ...?

 Car il te dit qu'il y a 63 cases dans son tableau de 6 lignes ...?
 Hors pour moi il y en a 64 , car à moins d'être aveugle et nul $2^6=64$ cases ... et non 63 , qui est bien la valeur du dernier nombre dans la 64 ème case, donc le nombre $2^{6} - 1= 63$ qui indique aussi le nombre de nombres = 64 cases  - 1 puisqu'il commence avec le chiffre 1...


 D'autant qu'il veut utiliser le nombre de cases = $2^n$ par rapport au N° de la ligne $n$ et la valeur du dernier nombre qui est égal à $2^{n+1} - 1$ valeur de la dernière case de la dernières ligne.
 Déjà qu'il numérote ses ligne soit en partant de 1 ou de 0 ; de sorte que le premier terme de la ligne $n$ soit $n$ ou $n+1$ ce qui permet de garder ses puissances de 2 qu il veut utiliser...

Car même en étant nul en math : $2^0 = 1$ valeur de la première ligne et du seul terme ligne N°0...et non pas 2¹ = 1 ...!
Puisqu'il veut utiliser $2^n$ pour ses calculs.

Math Coss

Je pense que ce serait plus lisible en remplaçant 1 par 63, 2 par 62 et plus généralement $k$ par $2^n-k$ et en écrivant le nombre correspondant en binaire.

lourrran

@LEG

Soit tu n'as pas lu son premier message, soit tu ne l'as pas compris.
Je vais t'accorder le bénéfice du doute : tu n'as strictement rien compris.

jmf

@LEG

Je pense qu'on devrait éviter ce ton un peu agressif. Surtout que dans un arbre binaire complet de hauteur 6, comme ici, il y a bien
1+2+2^2+...+2^5 = 2^6-1 = 63 cases.
Mais je suis peut-être "aveugle et nul"?

Umbre

LEG a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2349111/#Comment_2349111

[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]

Je demande l'aide de personnes gentilles et plus fortes que moi. Toi non seulement tu es agressif, mais tu ne sais pas compter. Je te suggère de les compter toi-même à la main une par une.

Merci beaucoup aux autres, en particulier lourran et jmf, pour votre aide bienveillante, je vous répondrai ce soir plus en détail à tête reposée.
Bonne journée à tous.

Médiat_Suprème

Comme je le disais plus haut, l'étude des différences entre 2 cellules semble mener à la solution :

1		0
2		0																31
3		0								15								16								15
4		0				7				8				7				9				7				8				7
5		0		3		4		3		5		3		4		3		6		3		4		3		5		3		4		3
6		0	1	2	1	3	1	2	1	4	1	2	1	3	1	2	1	5	1	2	1	3	1	2	1	4	1	2	1	3	1	2	1

LEG

("Autant pour moi pour le nombre de cases... mais il n'y a aucune agressivité , simplement une erreur ")

Médiat_Suprème 

Effectivement, mais cela veut dire qu'en fonction du nombre de lignes du tableau il faut recalculer toutes les différences... pour remplir le tableau .?

Si on prend n=8 lignes 
Ligne 2 , deux cases avec 2, et 129

Car suivant l'énoncé 255 est la valeur de la dernière cellule ligne 8 , la ligne 8  comporte 2^7 = 128 cellules
La valeur 128 devrait se trouver dans la cellule 64 ligne 8 

8 ........................                      ........   128...

Bon courage pour le programme....

Médiat_Suprème

Vu la façon dont le tableau est rempli, il est évident que toute formule dépend du nombre de lignes (en plus du numéro de ligne et de colonne), comme déjà signalé dans mon premier message.

Umbre

@jmf Merci pour ce code. Je ne connais pas vraiment le OCaml, j'utilise principalement le c++. Ton code semble générer un arbre où les numéros ne sont pas dans le bon ordre, ou alors je n'ai pas bien compris. Je précise incidemment que je ne génère pas réellement un arbre complet dans mon programme, je ne génère que certains nœuds. En les mettant dans une liste ordonnée, un nœud parent précède toujours immédiatement ses enfants, c'est tout l'intérêt car l'arbre est construit de telle façon que chaque nœud ait une valeur supérieure à celle de ses parents.

Mais peu importe pour les détails d'implémentation. Pour que mon programme fonctionne, j'ai besoin de calculer rapidement le numéro d'un nœud quelconque, et inversement je dois aussi pouvoir calculer simplement la ligne et la colonne du nœud sur lequel se trouve un nombre quelconque.

J'ai déjà réussi à réaliser cela en laissant des "trous". Je bidouille pour que les écarts sur une ligne soient constants.  Avec cette solution le calcul de devient très simple. Avec une simple division j'obtient la ligne et la colonne ! Mais c'est certainement sous-optimal et il y a un gaspillage de ressources puisque beaucoup de valeurs ne sont pas utilisées.

Un nombre i quelconque se trouve à la ligne l = i%n et à la case i/(n*(2^(n-1-l))) 

(J'aimerais utiliser le LateK du forum comme vous, mais je n'ai pas trouvé la commande).

Un exemple, toujours avec n=6 pour illustrer :

Je n'aime pas trop cette solution très gourmande.

Merci beaucoup @lourrran, j'ai l'impression que tu as trouvé la solution, mais j'ignore ce qu'est la "valuation 2-adique." Sont-ce les valeurs des différences que @Médiat_Suprème a calculées ? Je ne sais pas comment générer cette suite de nombres. Quelles seraient les formules pour mettre en relation ligne-colonne et numéro de case ?

Totalement d'accord avec Médiat_Suprème et LEG pour dire que le tableau, la place des éléments, ainsi que la formule, s'il en existe une, dépendent entièrement du nombre de lignes. Ce n'est pas un problème, s'il faut le fixer, disons n=32.

Voici pour @Math Coss dont j'ai suivi le conseil :

@LEG aucun soucis, il m'arrive très souvent de me tromper aussi

Merci encore à tous de vous intéresser au problème.

lourrran

Valuation 2-adique : 
Si $n$ est un entier quelconque $v_2(n)=$ le plus grand entier $k$ tel que $2^k$ divise $n$
Et donc 
Si $n$ est impair, $v_2(n)=0$
si $n$ est pair, sans être multiple de $4$ , $v_2(n)=1$
si $n$ est multiple de $4$, sans être multiple de $8$, $v_2(n)=2$   etc etc 

Application dans ton exemple initial : 
Sur la dernière ligne, le 4ème espace est entre 10 et 13 ; à cet endroit, on remonte de 2 lignes dans l'arbre. Idem pour le 12ème espace (entre 25 et 28), idem pour le 20ème espace (entre 41 et 44) et idem pour le 28ème espace (entre 56 et 59)
Ces emplacements (4, 12, 20 et 28), ce sont les nombre qui sont des multiples de 4 qui ne sont pas des multiples de 8 (des multiples impairs de 4)
Ce sont les nombres tels que $v_2(n)=2$

La somme des $v_2(i)$ pour tous  les entiers $i$ entre $1$ et $k$ ... c'est un exercice 'classique', qui a été évoqué sur ce forum il y a quelques mois, c'est rapide à calculer.

A l'occasion, (ce Week-end ?) je peux te faire 3 fonctions pour :
1/ générer le tableau
2/ retrouver le n° de ligne et de colonne pour un entier donné, et un nombre de lignes donné.
3/ retrouver le contenu d'une case imposée.

Ce ne sera pas du C++, mais tu devrais pouvoir le traduire.

Edit :
 mais je pense que d'autres intervenants trouveront une heure ou deux, ce soir ou demain pour te faire ça, et directement en C++.

LEG

re 
je vois que tu viens de modifier ton tableau ... par rapport à celui du début de message , qui avait une certaine logique avec les puissance de 2 .
La il n'y a plus rien .
pour générer la suite de nombre de nombres de Médiat  il y avait une logique ... 

la ligne 6  la dernière cellule valait $2^6 - 1 = 63$ ;  la ta ligne 5 , la dernière cellule vaut 191 ??? soit la cellule 16 = 184 de la ligne 4 augmenté de 7.
donc la ligne en dessous n°5 pour chaque valeur de la ligne n° 4, tu augmentes de 1 à gauche et de 7 à droite 

$4+7 = 11$ première valeur de la cellule n°1 et ensuite 16+1 et 16+7 ...etc même avec ton premier tableau il ne peut pas y avoir une valeur ou augmentation constante par cellule ; tu vois bien que la remarque de <Mediat> avec les différences entre les valeurs de cellules, ne sont pas et ne seront pas régulières .Ce qui implique de connaître la ligne précédente , pour en déduire les valeurs des cellules de la ligne suivante ...à mon avis ...

Ligne 1  tu as 2 cellule avec 1 et 97 , comment tu as défini 97  ?

ensuite tu rajoutes 98/2 = 49 à droite des cellules ligne 2
50/2 = 25, puis ligne 3, tu rajoutes 25  à droites des cellules de la ligne 2 et tu augmente des 1 à gauche des cellules 
26/2 = 13...etc ligne 4 tu rajoutes 13  à droites des cellules de la ligne 3
14/2 = 7 ..etc ligne 5 , que tu rajoute à droite 

Ce qui te donne 6 ;12 ; 24 ; 48 de différences entre ces 5 valeurs {7,13,25,49 ,97} ...


Sur ton premier tableau c'était simple puisque avec 6 lignes, ligne  2 cela  te donnait cellule 2 : $1 + 2^{6-1} = 33$ puis pour la ligne 3 tu avais dans la cellule 4 : $33 + 2^{5-1} = 49 $ et cellule 3 tu as 33+1 = 34  ; cellule 2 , c'est $2 + 2^{5-1} = 18 $.etc 

À la base tu fais 8 lignes = 256 cellule ; sans savoir la valeur de la ligne 1 cellule 2, comment tu pourrais dires ligne 8 cellule 9 , qu'elle est sa valeur ?

 Puisqu'elle serra fonction de la cellule 5 augmenté de 1, de la ligne 7,  ("qui comportera 128 cellules")...

Umbre

lourrran a dit :

Valuation 2-adique : 
A l'occasion, (ce Week-end ?) je peux te faire 3 fonctions pour :

 mais je pense que d'autres intervenants trouveront une heure ou deux, ce soir ou demain pour te faire ça, et directement en C++.

Merci beaucoup ! Je n'en demande pas tant je ne voudrais pas être un poids  Je veux bien la formule qui exprime la somme des valuations 2-adiques, et une méthode pour calculer le numéro de ligne et de colonne pour un entier donné (un calcul direct qui n'exige pas de parcourir l'arbre si possible). Je pourrai coder moi-même ensuite sans vous embêter davantage. Encore un grand merci pour toute l'aide apportée. Bonne soirée à tous !

Umbre

@LEG
En fait, il s'agit de ma solution actuelle qui fonctionne mais qui n'est pas optimale. Je veux la laisser tomber, mais si tu tiens à comprendre, quelques explications :
Je me suis juste arrangé
1) pour que le reste de la division par 6 d'un nombre donne immédiatement sa ligne
2) pour que les écarts entre deux colonnes soient constants sur une ligne, afin de trouver facilement la case.
3) Le tout en conservant l'ordre (auquel je tiens) des cases du premier tableau que j'avais présenté.

Mais peu importe, je veux abandonner cette solution. Ce que propose @lourrran répond bien mieux au problème je crois.

lourrran

Si $n$ est un entier , la somme des $v_2(i)$ pour $i$ entre $1$ et $n$ vaut $E(n/2) + E(n/4) +E(n/8) + .... +E(n/2^k)$

Où $E$ est la fonction partie entière, 

Si n est de l'ordre de 5000 par exemple, on n'a plus 5000 trucs à calculer et à additionner, mais seulement une douzaine.

lourrran

Bon, j'ai craqué. 
Voici une fonction en Python qui donne le n° de ligne et de colonne à partir du nombre.
Par exemple, pour X=63 et N=6, cette fonction renvoie (6,32) 

Les pros de Python vont dire que c'est très mal écrit, mais  je fais 20 minutes de Python tous les 6 mois à peu près, 

from math import pow as power 


def WhereIs(X,N):
    '''
    N est le nombre de lignes
    X est le numéro recherché

    '''
    numlig = 1 
    numcol = 1 
    ici = 1
    if X > power ( 2,N) -1 :
        return[0,0]
    if X==ici :
        return[1,1]       
    while ici != X:
        delta = power ( 2, N-numlig ) 
        if X == ici + 1 :
            return[numlig+1, numcol*2-1]
        elif X == ici + delta:
            return[numlig+1, numcol*2]
        elif X > ici + delta :
            ici = ici+delta
            numlig = numlig +1 
            numcol = 2 * numcol
        elif X < ici + delta :
            ici = ici+1
            numlig = numlig +1 
            numcol = 2 * numcol-1     
        
for i in range(63):
    ii = i+1
    print  ( "i=" + str(ii) + " lig,col = " )
    print ( WhereIs(ii,6))

Tu peux la tester sur ce lien ;  https://www.onlinegdb.com/online_python_interpreter

lourrran

Et l'autre fonction : pour un n° de ligne et un n° de colonne, et un nombre total de lignes donné, retrouver le nombre contenu dans cette case :

from math import pow as power 
from math import trunc

def QuoiDansCase(lig, col, N):
    if lig > N:
        return 0
    if col > power(2,lig-1):
        return 0
    X = lig
    Delta = power(2, N-lig+1)-1
    X = X + (col-1)*Delta
    k=2 
    ccol = col-1
    while k <= ccol :
        X = X + trunc( ccol/k)
        k = k*2
    return X    

N=6
ncol = 1 
for ilig in range(N):
    ilig0= ilig+1
    print ( " ligne = " + str(ilig0) )
    for icol in range(ncol) :
        icol0 = icol+1
        print( str(QuoiDansCase(ilig0,icol0, N)  ) + " " + str(icol0 ) )
    ncol=ncol *2    

LEG

Boniour
@lourrran : ton programme fonctionne bien , mais il lui faudrait uniquement la ligne fixée et la colonne au lieu de toutes les lignes et les colonnes .
par exemple :
j'ai rentré N = 6 et col = 5 il aurait dû afficher  6.13.5 et sans passer par toutes les valeurs du tableau ...
Pour N = 8 et col = 61 , le résultat  124 .. 
il ne lui reste plus qu'à ....en C++  ; en gardant le tableau en mémoire ram et afficher uniquement la  ligne , valeur , col ex : 8, 124, 61
Mais peut être qu'il faut modifier ton programme python car "" il affiche des valeurs inutiles ...""  d'après ce que j'ai pu constater...

lourrran

La boucle demande explicitement d'afficher toute les valeurs.
Pour le 2ème programme, si tu remplaces toute la fin  (à partir de la ligne N=6 ...) 
par 
print( str(QuoiDansCase( 6, 5 , 6 )) 
tu auras bien uniquement le contenu de la ligne 6, colonne 5, dans le cas où le tableau contient 6 lignes en tout.
Tu es toujours dans l'idée que le nombre total de lignes ne sert à rien. Et donc tu ne peux pas suivre la discussion.

jmf

@lourran et @Umbre

Je viens avec une autre approche du calcul de la position (ligne,colonne) d'un entier X dans un tableau de hauteur N.

Pour les explications, je reprends le tableau initial de @Umbre.



Ce tableau, je l'appelle T(6,1) car il est de hauteur 6, et on trouve 1 à sa racine.
La racine 1 de T(6,1), elle a deux tableaux enfants : de gauche à droite, T(5,2) et T(5,33)
De même, les deux tableaux enfants de T(5,33) sont T(4,34) et T(4,49).
Plus généralement, le tableau T(h,r) (hauteur h, racine r) contient les entiers $2^h-1$ entiers de l'intervalle $I_{r,h}=[r,r+2^h-2]$.
Si $h>1$, la racine $r$ de $T=T(h,r)$ a les deux tableaux enfants $T_g=T(h-1,r+1)$ et $T_d=T(h-1,r+2^{h-1})$.

Imaginons qu'on veuille chercher le couple (ligne,colonne) dans $T(h,r)$ d'un entier $x$ de $I_{r,h}$. Il y a  trois cas.
Si $x=r$, le résultat est $(1,1)$.
Si $r<x<r+2^{h-1}$, alors la recherche se fait dans $T_g$. Si celle-ci renvoie $(l,c)$, alors le resultat dans $T$ est $(l+1,c)$
Si $r+2^{h-1}\le x<2^h-1$, alors la recherche se fait dans $T_d$. Si celle-ci renvoie $(l,c)$, alors le resultat dans $T$ est $(l+1,c+2^{l-1})$ (l'augmentation au niveau du numéro de colonne vient de ce que, dans le tableau $T$, il faut ici "passer" par dessus les $2^{l-1}$ éléments de la ligne $l$ du tableau $T_g$.

Donc voici ma fonction.
On suppose que les arguments initiaux $H,X$ ($H$ hauteur de l'arbre de départ, et $X$ entier cherché) vérifient bien $1\le X\le 2^H-1$.
Tout repose bien sûr sur l'utilisation d'une fonction récursive aux, qui prend en argument la hauteur $h$ du sous-arbre courant, et la racine $r$ de celcui-ci. Cette fonction récursive est appelée initialement avec les arguments $H$ et $1$. La complexité est en $O(H)$ car à chaque itération il y a un seul appel récursif et la hauteur courante de l'arbre diminue de $1$. 

def lignecol(H,X):   
    def aux(h,r):
        if X == r: return (1,1)
        m = 2**(h-1)
        if X < r + m:
            (l,c) = aux(h-1,r+1)
            return (l+1,c)
        (l,c) = aux(h-1,r+m)
        return (l+1,c+2**(l-1))
    return aux(H,1)

LEG

@lourrran

(" Où tu as vue, que j'ai dit que le nombre de ligne ne sert à rien ... Tu plaisantes, sinon comment tu vas inscrire les valeurs ligne 64 cellule 88 ? D'autant que le n° d'une ligne te donne le nombre de cellules de la ligne...")

Je viens de tester avec ta ligne de code , en rajoutant la 3ème accolade
print( str(QuoiDansCase( 6, 5 , 6 )))

Ça va très vite pour avoir  tout de suite la valeur recherchée à l'écran de la dernière ligne n et uniquement pour un tableau de n ligne("même si le programme continue de calculer")


j'ai pris: la cellule 700
N 64
ncol = 1 

print( str(QuoiDansCase( 64, 700 , 64 )))

Résultat 1455

je pense que c'est ce qu'il cherche... même pour N = 128 par ex et colonne 30700 on a le résultat tout de suite .... Sauf que si on demande une cellule X ligne n - y ; pour ce types de tableau avec n=128 , et ben pas de résultat ....

Bonne continuation

lourrran

@LEG
Ton dernier message confirme que tu n'as toujours pas compris le besoin...
Pour écrire une valeur en ligne 64 et en cellule 88,  .. comment je fais ?  Je ne sais pas faire, parce que l'énoncé est incomplet. Il faut 3 paramètres, et non 2.
D'ailleurs, autre indice, tu écris nombre de ligne   et moi, j'écris nombre de lignes

@jmf
Je ne passe pas par la récursivité, mais c'est exactement la même idée dans ma fonction WhereIs()
A chaque étape, je cherche dans quel demi-arbre le nombre cherché va se trouver.
Pour expliquer un peu les noms des variables dans ma fonction WhereIs(), j'ai une portion d'arbre, chapeautée par le nombre $ici$, (par exemple $ici$ vaut 33), et cette portion d'arbre se divise en 2 sous-arbres, l'un chapeauté par le nombre $ici+1$ et l'autre chapeauté par le nombre $ici+delta$  ($34$ et $49$ en l'occurrence)
Plutôt que tester si le nombre cherché vaut $ici+1$ ou $ici+delta$, je devrais tester s'il vaut $ici$
Pour un code un peu plus performant, et un peu plus court.

jmf

lourrran a dit :
Plutôt que tester si le nombre cherché vaut $ici+1$ ou $ici+delta$, je devrais tester s'il vaut $ici$

Oui c'est vrai, c'est la même idée, et on est d'accord sur tout, mais je pense que le point de vue récursif est plus raccord avec cette notion d'arbre binaire. Le code est plus facile à écrire et à lire (IMHO).

jmf

@Umbre

J'ajoute une petite fonction qui renvoie le numéro placé en ligne L et colonne C dans un arbre de hauteur H.
On suppose que les arguments sont corrects ($1\le L\le H$ et $1\le C\le 2^{L-1}$).

Là aussi, j'utilise une fonction récursive d'arguments $h,l,c,r$ où $h$ est la hauteur de l'arbre courant, $(l,c)$ le couple (ligne,colonne) visé dans cet arbre courant, et $r$ la racine de celui-ci.

Si $l=1$, on renvoie la racine, et sinon:
Si $c\le 2^{l-2}$, on cherche dans le sous-arbre gauche, et sinon dans le droit (en actualisant comme il faut les paramètres d'appel de la fonction aux, et notamment le couple $(l,c)$ visé).

def cherche(H,L,C):
    def aux(h,l,c,r):
        if l == 1: return r
        cm = 2**(l-2)
        if c <= cm: return aux(h-1,l-1,c,r+1)
        return aux(h-1,l-1,c-cm,r+2**(h-1))
    return aux(H,L,C,1)

LEG

@lourrran
Tu veux dire que ton code marche uniquement pour un tableau de N = 6 lignes...?

car pour N =8 il fonctionne tout aussi bien ...print( str(QuoiDansCase( 8, 120 , 8 ))) uniquement pour la ligne 8....

N=8 et cellule 120 , résultat 240 c'est le bon résultat ... (suivant sa méthode pour la dernière la ligne de son tableau avec N rentrée  )

pour N=64 cellule 88 résultat 233 

Mais tu as raison pour cette phrase [Pour écrire une valeur en ligne 64 et en cellule 88,  .. comment je fais ?  Je ne sais pas faire ]:

Par contre il me semble que si on veut la valeur de la cellule 163, à ligne 26 pour un tableau de 31 ligne, ou  la valeur d'une cellule = 153331 par exemple avec en entrée  :

int main() {
  lieu(31,153331);

C'est à dire un tableau de 31 lignes ....il faut faire tout le tableau en mémoire, du fait de l'incrémentation des cellules où elles dépendent les unes des autres des 5 lignes précédentes....,ou encore des 6 lignes précédentes pour un tableau de $2^{6}-1$ cellules ; afin d'éditer le résultat ,    [ N° col et N° cellule] ...

 C'est ce qu'à fait @Marco dans son 2ème programme ci dessous , qui fonctionne très bien pour 31 lignes , j'ai testé (64 , 15333175) ;
20 minutes après il tournait toujours plus de $10^{19}$ cellules.....

lourrran

@LEG
si on veut dans un tableau de 64 lignes la valeur de la cellule 63, à ligne 32 ....il faut faire tout le tableau et l'éditer..

Encore une stupidité.  Et pire, tu prétends que c'est ce que j'aurais dit.

Allez, j'active la fonction 'ne plus voir les messages de LEG', ce que j'aurais dû faire dès le premier message.

@jmf
Globalement d'accord sur le bénéfice lié à la récursivité.
J'avais ma fonction, j'ai voulu partager ça aussitôt avant d'aller au dodo ...  mais c'est clair que c'est du brouillon pas très présentable.

marco

J'ai écrit un programme en C++ qui renvoie le contenu de la case $(l,c)$ où $l$ est le numéro de la ligne, et $nblignes$ le nombre de lignes. C'est la même idée.

#include <iostream>
using namespace std;

long contenu(long nblignes,long l,long c) {
  long n=nblignes-1;
  long k=l-1;
  long x=c-1;
  long i,s;
  s=1;
  for(i=0;i<k;i++) {
    if((x>>i)%2==0) {
      s++;
    }
    else {
      s=s+(1<<(n-k+1+i));
    }
  }
  return s;
}

int main() {
  long i,j,a;
  for(i=1;i<=6;i++) {
    for(j=1;j<=(1<<(i-1));j++) {
      a=contenu(6,i,j);
      cout<<a<<" ";
    }
    cout<<"\n";
  }
}

marco

J'ai écrit le programme en C++ qui donne l'emplacement de la case en fonction de la valeur dans la case:

#include <iostream> 
using namespace std;

void lieu(long nblignes,long x) {
  long i,j,n;
  n=nblignes-1;
  i=0;
  j=0;
  x--;
  while(x!=0) {
    if(x>=(1<<(n-i))) {
      j=(j<<1)+1;
      x=x-(1<<(n-i));
    }
    else {
      j=j<<1;
      x--;
    }
    i++;
  }
  cout<<"ligne : "<<(i+1)<<" colonne :"<<(j+1)<<"\n";
}

int main() {
  lieu(6,46);
}

Umbre

Navré, j'étais au travail toute la journée, et j'ai manqué beaucoup de messages. Je me sens gêné d'occuper autant de neurones (bien plus capables que les miens !) sur mes pauvres problèmes. J'ai eu le temps hier soir de tester le code de @lourrran que je remercie vivement. Il fonctionne parfaitement et je serai capable de l'adapter à mes besoins. J'ai d'ailleurs commencé à coder une version c++. Bravo à @marco qui me devance et qui a fini le travail avant moi . Le code de @jmf me semble très intéressant aussi, je l'étudierai plus tard, car avec mes lubies informatiques, les copies (pas de science, je vous rassure) s'accumulent dangereusement. Merci à tous, c'est une grande chance d'avoir une aide de cette qualité, donnée si généreusement !
Je lirai en détail tous vos posts (que je m'efforce de comprendre) plus tard dans la soirée.

marco

Merci @AD , je n'arrivais pas à mettre du code dans un message. J'ai bien trouvé Code dans un menu déroulant, mais ça ne donnait pas un résultat lisible. Comment fait-on ?

AD

Bonsoir Marco

Je ne sais pas faire, j'y arrive en bidouillant le html jusqu'à ce que ça marche. Ce n'est pas une méthode recommandable !

AD

lourrran

Les 2 morceaux de code que j'ai postés, c'est avec le style code de la barre d'outils

marco

Merci AD et lourrran.

jmf

@marco

Poster du code c'est pas hyper facile, faut bien le reconnaître.
J'ai compris un truc, c'est qu'il ne faut pas copier/coller plusieurs lignes simultanément.
Je copie/colle ligne par ligne donc, en faisant des retours-chariot au fur et à mesure.

marco

Merci. J'y suis finalement arrivé en supprimant les instructions <code> et </code>, et en conservant <pre class="CodeBlock">

depasse

Bonsoir
pour le fun, une formule "close".

Si
$\bullet~ v $ désigne la $2$-valuation,
$\bullet~ \forall n \in \mathbb {N^*},\  n:=2^{i_n}+j_n$, (où $2^{i_n} \leq n <2^{i_n+1}$).
Alors
$\bullet~ \forall h \in \mathbb {N^*},\ \forall n \in [[1, 2^h[[$,
la cellule numérotée $n$ dans l'arbre de hauteur $h$ contient le nombre $$i_n+1+v\big((2^{h-i_n}j_n)!\big)$$ Enfin, il me semble...
Cordialement.
Paul.

LEG

Bonjour @depasse
Je ne suis pas sûr, que cela soit aussi simple qu'il n'y paraît, car une cellule a plusieurs antécédents, et le nombre d'antécédents dépend  du nombre de lignes $h$ du tableau et de la partie du tableau ou cette cellule se trouve, c'est-à-dire sa colonne $X_n$, où $n$ et le N° de la ligne et par conséquent de la valeur de ses antécédents : des cellule $X_n$.

Supposons pour un tableau de $2^{28} - 1$ cellules :
1) Qu'une cellule se trouve dans la colonne $41$ ligne $n=21$ pour un tableau de $h=28$ lignes, combien a-t-elle d'antécédents et quel sont-ils ?
Sachant que la valeur $V$ de cette cellule vaut :  $V_n = 10514$ .
2) Valeur de la cellule numéroté 127 : combien a-t-elle d'antécédents ? Qu'elles sont ses antécédents ? Et leurs valeurs ?

lourrran

@depasse
Tu parles de la cellule numérotée $n$ dans l'arbre de hauteur $h$.

Ok, mais prenons par exemple $n=1$.
Dans l'arbre de hauteur $h$, on a plusieurs cellules qui sont numérotées 1. On en a une sur chaque ligne.

Pour identifier une cellule, il faut 3 paramètres : la cellule numérotée $n$ dans la ligne numérotée $\ell$, dans l'arbre de hauteur $h$.

depasse

Bonjour
Merci pour vos réponses

Ma numérotation des cellules:
Le numéro de la racine est $1$
$\forall n \in \mathbb {N^*}$, la cellule numérotée $n$ a deux filles: la gauche est numérotée $2n$ et la droite $2n+1$.
Deux cellules distinctes ont des numéros différents. On a ainsi un arbre infini numéroté une fois pour toutes.
Si on veut l'arbre de hauteur $h$ on ne s'occupe que des cellules numérotées de $1$ à $2^h-1$. Chacune contient un nombre qui est donné, j'espère, par ma formule.

Une idée est de considérer la hauteur comme le temps, les cellules comme des chambres d'hôtel, les nombres contenus dans ces cellules comme des voyageurs.
Quelle est la suite des chambres où est passé monsieur $43$?
Quelle est la suite des clients qui ont fréquenté la chambre $217$?

Cordialement
Paul

LEG

depasse a dit :
$\forall n \in \mathbb {N^*}$, la cellule numérotée $n$ a deux filles: la gauche est numérotée $2n$ et la droite $2n+1$.
 Chacune contient un nombre qui est donné, j'espère, par ma formule.

C'est bien pour cela que je t'ai demandé pour un arbre de hauteur (h=28) soit $2^{28}-1$ cellules : valeur de la cellule $n=127$  et valeur de la cellule $n=1001$
De plus la cellule $n=1001$ est la fille de quelle cellule, ligne $n-1$ ? est-ce de valeur V :  $V_{n-1} +1$ ou $V_{n-1} + 2^{28-(n-1)} $ ...?
Parce que sauf erreur : une cellule numéroté $n$ ligne $l_n$ donnera bien deux filles ...  mais une numéroté n+1 sûrement pas ...!
C'est la valeur de la cellule numéroté $n$ qui augmente de 1 et de $2^{28-(l-1)}$
Elle donnera donc bien une fille cellule numéroté $X_n$  à la ligne $l+1$ de valeur $V+1$ et une fille à la ligne $l+1$ de valeur $V+2^{28-(l)}$ à la cellule numéroté $X_{n+1}$ ...
Exemple, toujours pour cet arbre ou tableau : la cellule mère ligne $l=19$ numéroté $n=904$ , de valeur $V = 8210$ donnera bien deux filles à la ligne ligne $l+1=20$ de valeurs $V+1 = 8211$  cellule $n=904+72=976$ et $V = 8210+2^{28-19} = 8722$ cellule $n=904+73=977$
Donc on peut avoir pour une fille plusieurs antécédents qui ont augmentés plusieurs fois de 1 ...+1 +1 ou plusieurs fois de $2^{28-(l-1-1..}$
Le nombre d'antécédents est fourni par la ligne dans la partie du tableau où se trouve la cellule $n$ dans l'exemple ci-dessus, on est dans la puissance $n=5$ il y aura 5 antécédents pour la cellule $n=977$.

depasse

A LEG

Au sommet de mon arbre est la racine (c'est bizarre une racine en haut mais c'est fréquent en maths). Cette racine est numérotée $1$.
Elle est sur la ligne $0$ et sur la colonne $0$. Il n'y a qu'elle sur la ligne $0$.
Cette racine numérotée $1$ a deux filles: la gauche numérotée $2$ (=2 fois le numéro de sa mère, en l'occurrence 2 fois le numéro de la racine, à savoir $2*1$) et la droite  numérotée $3$  (=2 fois le numéro de sa mère plus $1$, en l'occurrence 2 fois le numéro de la racine plus $1$, à savoir $2*1+1$). Ces deux filles sont sur la ligne $1$. La fille gauche est sur la colonne $0$ et la droite sur la colonne $1$ etc...

1
23
4567
89101112131415

Avec ma numérotation, la mère de la cellule numérotée $1001$ est la cellule numérotée $500$.
Sur la ligne $i$ on lit, de gauche à droite, les $2^i$ entiers , $2^i+0, 2^i +1,......, 2^i +2^i -1$.
Si $0\leq k<2^i $, $2^i+k$ est sur la colonne $k$.

Ainsi, sous réserve que la ligne la plus haute soit la ligne $0$ et la colonne la plus à gauche soit la colonne $0$, si l'on se demande en quelles ligne et colonne se trouve la cellule numérotée $n$ on trouve le $i_n$ et le $j_n$ que j'ai explicités dans mon précédent message.

Fort de ce renseignement qui donne ligne et colonne, on peut calculer par ma formule le nombre qui se trouve dans dans la case numérotée $n$ lorsque la hauteur $h$ de l'arbre est donnée.

En espérant avoir été plus clair
Cordialement
Paul