Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-12-2014 15:07:14

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

sivisible par 2

On sait que la condition nécessaire et suffisante pour qu'un nombre soit divisible n fois par 2 est que le nombre formé par les n derniers chiffres l'est aussi.
Mais comment trouver n sans avoir à faire forcément tous les tests jusqu'à échec ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 15-12-2014 21:11:28

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Divisble par 2

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 lol
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.


Il y a sûrement plus simple.

 #3 - 15-12-2014 21:16:19

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4905

Divisble par 2

En l'écrivant en base 2 ?

Vasimolo

 #4 - 16-12-2014 06:01:00

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

Divisible pa 2

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

 #5 - 16-12-2014 11:25:15

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

Divisible parr 2

Unanimement, la réponse est de convertir le nombre en base 2: ça marche, et c'est efficace, mais quelque part, c'est faire la division par 2 de tout le nombre. La question posée se réfère aux chiffres à droite du nombre, et ne passe pas par la conversion en base 2.

 #6 - 16-12-2014 18:41:32

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

Divisiblee par 2

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.

 #7 - 17-12-2014 08:13:54

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

divisoble par 2

Pardonnez loi d'avoir écrit cette énigme un peu vite, en rédigeant la réponse je me suis aperçu d'un bug....

 #8 - 17-12-2014 18:36:22

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Divisibel par 2

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.


Il y a sûrement plus simple.

 #9 - 18-12-2014 07:54:21

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

Divisile par 2

Après remise au point de ma petite méthode, je relance le sujet et donne du temps supplémentaire. Pour décourager ceux qui seraient tenté de maintenir l'écriture en base 2, je demande de me dire combien de fois on peut diviser par 2 ce nombre :
215487945864531245689784516458975421310213021542102458179112 ?

 #10 - 18-12-2014 08:36:03

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

divisuble par 2

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

 #11 - 18-12-2014 09:23:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

iDvisible par 2

D'accord, énigmatus. Donc la question, je la repose: est il possible, sans avoir forcément à faire toutes les divisions depuis le nombre unité à 1 chiffre jusqu'au nombre à k chiffres, de prédire combien de fois on peut diviser par 2 les grands nombres ?

 #12 - 18-12-2014 09:40:06

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

Divisible pr 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 sad

 #13 - 18-12-2014 20:25:14

unecoudée
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 206

Diviisible par 2

salut.

si je prend le nombre poste #9    il termine par 179112

je prend l'unité  2  -->  elle se divise par 2    tant que ça fonctionne je continue.

je prend 12 et le divise par 2²  --> ça fonctionne encore .

je prend 112  et le divise par 2^3 = 8  --> ça fonctionne toujours . je continue  ;

je prend 9112  et le divise par 2^4 = 16  --> et là ça donne un nombre décimal .

et là je m'arrête   .  le grand nombre est donc  divisible par 8  = 2^3

on peut  précéder 9112  de n'importe quel chiffre ex 29112 , il ne se divisera pas par 16.

 #14 - 18-12-2014 20:41:12

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,661E+3

diviqible par 2

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)

 #15 - 19-12-2014 09:28:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

Divisible par

Gwen, non, oublie la piste base 2.
Unecoudée, voir mon message précédent: éviter le test systématique des derniers chiffres. On peut voir plus vite que ce test, sans être obligé de faire des divisions à chaque fois.

Un indice: regarder la division par 2 des chiffres pris isolément et selon leur position...

 #16 - 21-12-2014 17:27:02

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

duvisible par 2

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.

 #17 - 21-12-2014 17:56:34

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

divisivle par 2

nodgim a écrit:

J'espère que c'est assez clair

Pourrais-tu expliquer ton raisonnement pour 12896 ? Merci

 #18 - 21-12-2014 18:11:04

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

duvisible par 2

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.

 #19 - 21-12-2014 18:13:10

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,661E+3

Divvisible par 2

J'ai strictement rien compris lol

La somme de 2 5 donne au moins 6 hmm
5 divisible 5 fois par 2 hmm

 #20 - 21-12-2014 18:14:15

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

Divsible par 2

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.

 #21 - 21-12-2014 18:16:45

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

Diivsible par 2

gwen27 a écrit:

J'ai strictement rien compris lol

La somme de 2 5 donne au moins 6 hmm
5 divisible 5 fois par 2 hmm

Tu n'a pas compris la méthode générale ou l'application sur ce nombre ?

 #22 - 21-12-2014 18:19:40

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,661E+3

Divisible par 22

J'ai rien compris du tout sad

 #23 - 21-12-2014 18:20:46

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3137

dibisible par 2

Es tu au moins d'accord avec les règles 1 et 2 énoncées ?

 #24 - 21-12-2014 18:35:38

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 430

Divisible pra 2

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 :

Code:

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

 #25 - 21-12-2014 18:44:51

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,661E+3

Divisibel par 2

nodgim a écrit:

Es tu au moins d'accord avec les règles 1 et 2 énoncées ?

Bah non... sad

2 est divisible par 2
4 aussi

Et 6 ne l'est pas 2 fois mais si tu sous-entends "exactement n fois", alors oui smile

De la même façon 14 1 fois, 2 aussi mais 16 4 fois... je sais que tu as écrit "au moins" mais ce "au moins" est trop vague à mon goût.

Je soupçonne que ça coince si n est supérieur au nombre de chiffres des nombres.

Elle donne quoi l'astuce pour 9216 ? En détail !

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
16-06-2011 Enigmes Mathématiques
P2T
Divisible par 7 par Vasimolo
14-09-2009 Enigmes Mathématiques
P2T
Nombre divisible par 30 par gabrielduflot
06-07-2009 Enigmes Mathématiques
P2T
Gâteau 4 par Vasimolo
19-04-2010 Enigmes Mathématiques
30-03-2015 Enigmes Mathématiques
P2T
Jeux à deux 1 par Vasimolo
12-03-2011 Enigmes Mathématiques
P2T
Problème de Cluj par SaintPierre
25-03-2011 Enigmes Mathématiques
P2T
25-05-2011 Enigmes Mathématiques
25-03-2011 Enigmes Mathématiques

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete