Bonjour,

Soit k le nombre dont on recherche la puissance de 2.
Si k est écrit en base 2 alors c'est très facile, il suffit de compter le nombre de zéro à la fin
Seulement convertir un nombre en base 2 reviendrait finalement à faire les tests.

Dans la suite je noterais "log x" pour "log en base 2 de x" et E(x) pour la partie entière de x.
Peut-être calculer n=pgcd (2^(E(log k)+1),k)
En effet, E(log k) + 1 est le nombre de chiffre de k dans son écriture en base 2, donc forcément k <  2^(E(log k)+1) donc le plus grand commun diviseur de ces deux nombres est la plus grande puissance de 2 dans k.

Bonjour,
Convertir le nombre complet en binaire : [latex]n[/latex] est le nombre de zéros à droite

Ajouté : Convertir le nombre en binaire va en général demander plus d'opérations que de diviser le nombre par [latex]2[/latex] jusqu'à ce qu'on ne puisse plus

On peut ne convertir en binaire que les [latex]n[/latex] chiffres de droite, mais on ne saura pas si le nombre initial est divisible par [latex]2[/latex] plus de [latex]n[/latex] fois.

Dans la formule que je donne avec le pgcd, je ne convertit pas n en base 2.

Sinon on pourrait faire une sorte de dichotomie qui permettrait seulement de réduire le nombre de tests.

Ou alors soit k le nombre dont on veut trouver le plus grand n tel que 2^n divise k, Si on note C(k) le nombre de chiffre de k alors n = nombre de zéro à la fin de k * 5^C(k) (ceci vient du fait que 2^n * 5^n = 10^n).

Je n'ai pas d'autre idées pour l'instant.

je demande de me dire combien de fois on peut diviser par 2 ce nombre :
215487945864531245689784516458975421310213021542102458179112 ?

[latex]3[/latex] fois
Il suffit de tester avec 2, 12, 112, 9112
Il est à noter que 112 est divisible 4 fois par 2

Avec ton exemple, tu peux diviser
2 par 2 -> oui
12 par 4 -> oui
112 par 8 -> oui
9112 par 16  -> non

Je ne vois pas mieux

Par dichotomie, ça limite déjà bien. n essais pour un nombre à 2^n chiffres, non ?

(vu que la condition est continue sur les chiffres)

La méthode que je vais décrire, que je baptise "méthode du moindre diviseur" repose sur 2 règles simples:
1 ) Si un nombre est divisible n fois par 2, et un autre m fois par 2, avec m>n, alors la somme est divisible n fois par 2. Il en est de même pour la somme de plus de 2 nombres. 
2)  Si 2 nombres distincts sont divisibles chacun n fois par 2, alors leur somme est divisible au moins n+1 fois par 2.
   
Application à un nombre composé de beaucoup de chiffres:

Les chiffres 2 et 6 sont divisibles 1 fois par 2, le chiffre 4: 2 fois, le chiffre 8: 3 fois. Le chiffre 0 est neutre.
Par ailleurs, un chiffre qui possède k nombres à sa droite est divisible k fois par 2 (1000 est divisible 3 fois)
Ainsi, à chaque chiffre d'un nombre, on attribue son nombre de diviseurs pris isolément.
Par exemple
....12396=...+10000+2000+300+90+6
pour 1: 4
pour 2: 4 (3 dû à la position et 1 dû au chiffre 2)
pour 3: 2
pour 9: 1
pour 6: 1   
Ainsi le nombre peut être modélisé par la suite des diviseurs de chaque chiffre: 44211.

On a une répétition du 1, donc la somme fera au moins 2, il faut calculer le nombre de diviseurs 2 de la somme: pour 96 c'est 5 (mais le fait que ce soit plus que 2 suffit à conclure)

Le nombre se réécrit 4425

Ici, on n'a pas besoin d'analyser plus: le 2 se trouve isolé, ce nombre est divisible 2 fois par 2. A noter que même si on ajoute un chiffre à gauche, ça ne changera rien. En effet, le chiffre supplémentaire à gauche aura 5 chiffres à sa droite, on lui attribuera au moins 5, bien plus que le 2.

Bien entendu, quand on voit un 16 par exemple dans un nombre, on peut directement attirbuer sa valeur 4 (ou plus selon sa position) ça ne change rien au résultat et ça accélère l'analyse.
Normalement, on n'a pas besoin d'aller très loin dans l'observation, les 4 ou 5 derniers chiffres suffisent en général. Et on fait toujours l'analyse pour les plus petites valeurs de diviseur attribuées.

J'espère que c'est assez clair, avec un peu d'entraînement, c'est assez facile d'usage.

12896--->555: 5 divisible 5 fois par 2.
Je vois 12000 (5) 800(5) et 96(5) la somme de 2 "5" donne au moins 6, donc le 5 qui reste est le plus petit.

Plus simple encore 12896: 12800 est très grand d'un point de vue du nombre de diviseurs par 2, plus que 96 qui vaut 5. C'est donc divisible 5 fois.

J'ai rien compris du tout

Désolé, mais ce n'est pas clair pour moi. Je verrais mieux avec un algorithme (éventuellement en pseudo-code) qui montrerait précisément les opérations dans le cas général.

Par exemple, en python, pour la méthode des divisions successives par 2 :

m=12396
k=r=0
while not r : m,r=divmod(m,2); k+=1
print(k-1)