Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Combien de fois peut-on diviser p! par 2? Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=luthin]Que des bonnes réponses ou presque, avec diverses méthodes. On a un bon aperçu de ce qu'il était possible de faire. Les réponses de Rivas et Scarta sont très complètes. Ca ne veut pas dire qu'il n'y a pas de choses intéressantes dans les autres messages. Je me permets de faire quelques remarques: [u]gabrielduflot:[/u] Il y a quelques erreurs de frappe et ton argument qui te permet de conclure me parait douteux. Il y a un facteur 2 de plus "entre" [latex]2^n+1[/latex] et [latex]2^{n+1}[/latex] que dans [latex](2^n)![/latex] et donc... [u]shadock:[/u] Ton "semblant de logique pure" m'a bien fait rire (ce n'est pas du tout méchant ou moqueur)! :lol: [u]scarta:[/u] Réponse qui me semble excellente. Très malin la démonstration de la question 2. Sinon, dans le dernier paragraphe, il faut lire "p est un nombre [u]impair[/u]". [u]franck:[/u] Oui, ça ressemble un peu à ça! :D [u]yanyan:[/u] La formule de Legendre, merci pour la référence, je ne connaissais pas. Ca répondait effectivement à ma question initiale. Si je l'avais su ou même deviné (elle se comprend assez bien en fait), j'en aurais pas fait une énigme. Ceci dit, il me semble que le résultat que je vous propose de démontrer n'en est pas moins intéressant... :) [u]Yannek:[/u] Bien vu ta première équation, ça permet de traiter la question 1 et le bonus d'un coup! Bon après le "on obtient", ça reste un peu mystérieux pour moi. Ne devrait-on pas lire "b" à la place de "n" au dessus de tes deux dernières sommes? :/ [u]rivas:[/u] Une autre excellente réponse. C'est très clair, merci. :) [u]Nicouj:[/u] Il me semble qu'à la place de "[latex]\lfloor\frac{p}{2^{\log_2{p}}}\rfloor[/latex] multiples de [latex]2^n[/latex]", il faut lire "[latex]\lfloor\frac{p}{2^{\lfloor\log_2{p}\rfloor}}\rfloor[/latex] multiples de [latex]2^{\lfloor\log_2{p}\rfloor}[/latex]", et idem pour la borne sup de la somme qui suit. Il doit y avoir aussi une petite coquille à la troisième équation en partant de la fin. Bon, après tout ça, j'ai pas intérêt à raconter n'importe quoi, ..., si c'est pas déjà fait! :D En fait, personne n'a utilisé la première question pour répondre à la deuxième... Je vous fais donc voir comment j'ai procédé, c'est pas plus malin, mais c'est juste ce qui m'a permis "de tomber" sur ce résultat que je trouve assez joli: [latex]k=p-b[/latex]. Je cherche donc la plus grande puissance [latex]n_1[/latex] de 2 dans [latex]p![/latex]. Elle est donnée par: [latex]n_1=E(\log _2 p)[/latex] Pour visualiser, on a: [latex]p!=\underbrace{1.2.3.2^2.5...2^3...2^{n_1}}(2^{n_1}+1)...p[/latex] D'après la première question, dans l'accolade, on a [latex]k_1=2^{n_1}-1[/latex] facteurs 2. Il faut alors se convaincre qu'il y a autant de facteurs 2 dans le reste [latex]\frac{p!}{(2^{n_1})!}[/latex]que dans [latex](p-2^{n_1})![/latex]. Et là, même principe, je cherche la plus grande puissance [latex]n_2[/latex] de 2 dans [latex](p-2^{n_1})![/latex]. Elle est donnée par: [latex]n_2=E\left((\log _2 (p-2^{n_1})\right)[/latex]. Et on pourra alors ajouter à [latex]k[/latex], un autre terme [latex]k_2=2^{n_2}-1[/latex]... En observant l'expression des [latex]n_i[/latex], on comprend qu'il correspondent, dans l'écriture binaire de [latex]p[/latex], aux puissances de 2 qui ont un poids non nul. Autrement dit, si [latex]p=\sum_{i=0}^{n_1}b_i2^i[/latex], on aura: [latex]k=\sum_{i=0}^{n_1}b_ik_i=\sum_{i=0}^{n_1}b_i(2^i-1)[/latex], soit [latex]\fbox{k=p-b}[/latex] A noter que ces résultats se généralisent pour une base entière [latex]a>1[/latex] quelconque. En effet, on peut écrire [latex](a^n)!=a^kr[/latex], avec [latex]k\in\mathbb{N}[/latex] et [latex]r\in\mathbb{N}^[/latex] non divisible par [latex]a[/latex]. Alors: [latex]\fbox{k=\frac{a^n-1}{a-1}}[/latex] De même, si [latex]b_a[/latex] est la somme des chiffres d'un entier [latex]p[/latex] en écriture de base [latex]a[/latex], alors, on peut diviser [latex]p![/latex] par [latex]a[/latex] au maximum [latex]k[/latex] fois avec: [latex]\fbox{k=\frac{p-b_a}{a-1}}[/latex] Merci à tous les participants! :)[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez (numériquement) à la petite énigme suivante : Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?* Retour Résumé de la discussion luthin 06-11-2010 19:47:18 Voici un autre problème que je me suis posé récemment: Question 1: Vous n'aurez pas de mal à vous convaincre que quelque soit l'entier [latex]n[/latex] positif ou nul, on peut écrire: [latex](2^n)!=2^k r[/latex], où [latex]k\in\mathbb{N}[/latex] et [latex]r[/latex] est un entier impair. Alors, je vous demande d'exprimer [latex]k[/latex] en fonction de [latex]n[/latex]. Question bonus: Profitez-en pour exprimer également [latex]r[/latex] en fonction de [latex]n[/latex] (sans faire intervenir [latex](2^n)![/latex]). Spoiler : Indice:. Question 2: C'est la question initiale que je me suis posé. Considérons un entier [latex]p[/latex] positif ou nul et notons [latex]b[/latex], la somme de ses chiffres en écriture binaire. Alors, au maximum, combien de fois peut-on diviser [latex]p![/latex] par 2? Spoiler : Indice: La question 1 n'est pas anodine... Amusez-vous bien. 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