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 : 2953

diviqible 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

Divisibl 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 : 4733

Divisible par

En l'écrivant en base 2 ?

Vasimolo

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

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

divisibme par 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 : 2953

divisible pat 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 : 400

Divisible par

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 : 2953

Divvisible 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

Divisilbe 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 : 2953

Divisiblle 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 : 400

divisoble 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 : 2953

divosible 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 : 400

Divissible 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 sad

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

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

Divisiblle 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,469E+3

DDivisible 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 : 2953

divisible pae 2

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 : 2953

Divisible par

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 : 400

Diviisible 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 : 2953

Divisible paar 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,469E+3

Diivsible 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 : 2953

Divisilbe 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 : 2953

divisiblz 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,469E+3

Divisbile par 2

J'ai rien compris du tout sad

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

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

iDvisible 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 : 400

Divisible parr 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,469E+3

Divisible par

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 (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
16-06-2011 Enigmes Mathématiques
P2T
Nombre divisible par 30 par gabrielduflot
06-07-2009 Enigmes Mathématiques
P2T
Divisible par 7 par Vasimolo
14-09-2009 Enigmes Mathématiques
P2T
Carré parfait par airone
11-10-2014 Enigmes Mathématiques
06-11-2013 Enigmes Mathématiques
10-09-2008 Enigmes Mathématiques
P2T
Passera, passera pas ? par Alexein41
24-01-2011 Enigmes Mathématiques
P2T
Rangement par gabrielduflot
02-07-2013 Enigmes Mathématiques
P2T
Fausse prémonition par Franky1103
22-10-2013 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