Trouvez le nombre d'entiers n < 1000 tels que
n! soit divisible par 2^(n-1) .
Ne perdez pas de temps avec les logiciels, ça m'étonnerai que vous en ayez un d'aussi puissant...
:lol3: :lol3:
Surchage de données avec la factorielle
15 messages
- Page 1 sur 1
par chan79 » 23 Aoû 2013, 12:40
Le Chat a écrit:Trouvez le nombre d'entiers n < 1000 tels que
n! soit divisible par 2^(n-1) .
Ne perdez pas de temps avec les logiciels, ça m'étonnerai que vous en ayez un d'aussi puissant...
:lol3: :lol3:
salut
ça marche avec 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
par adrien69 » 23 Aoû 2013, 13:11
D'après la formule de Legendre la valuation p-adique de la factorielle vaut
= \sum_{k \geq 1} \left\lfloor{\frac{n}{p^k}}\right\rfloor)
Avec 2 :
= \sum_{k \geq 1} \left\lfloor{\frac{n}{2^k}}\right\rfloor)
Si n n'est pas une puissance de 2, il devient dès lors évident que)
sera strictement plus petit que n-1. Dans le cas contraire par contre c'est bon. D'où le résultat.
Avec 2 :
Si n n'est pas une puissance de 2, il devient dès lors évident que
par adrien69 » 23 Aoû 2013, 13:14
Au pire si vous ne me croyez pas, au moins là c'est calculable sans problème.
par Olympus » 23 Aoû 2013, 13:51
Salut !
Je trouve aussi le même résultat que chan79 puisque le problème revient à trouver les
vérifiant =n-1)
( et ça c'est facile à faire avec un petit prog ).
Je trouve aussi le même résultat que chan79 puisque le problème revient à trouver les
par nodjim » 23 Aoû 2013, 18:04
Peut être plus simplement:
Si un nombre vaut 2^n, il y a dans la factorielle:
2^(n-1) "2" + 2^(n-2) "2" (on ajoute les nombres divisibles par 4) +2^(n-3) "2"+...
Soit au total (2^n -1) "2"
Ce 2^(n-1) représente la divisibilité demandée. Il est évident que si un nombre est différent de 2^n, il lui manquera au moins un "2".
Si un nombre vaut 2^n, il y a dans la factorielle:
2^(n-1) "2" + 2^(n-2) "2" (on ajoute les nombres divisibles par 4) +2^(n-3) "2"+...
Soit au total (2^n -1) "2"
Ce 2^(n-1) représente la divisibilité demandée. Il est évident que si un nombre est différent de 2^n, il lui manquera au moins un "2".
par adrien69 » 23 Aoû 2013, 18:05
C'est plus ou moins comme ça qu'on démontre la formule de Legendre.
par nodjim » 23 Aoû 2013, 18:34
Je m'étais amusé un temps à comparer, dans une factorielle, les puissances de 2, de 3, de 5, de 7 ,de 11...
De mémoire, c'éait le 2^n qui dominait largement, et il me semble qu'il était plus fort que le produit 3^m *5^p * 7^q.
De mémoire, c'éait le 2^n qui dominait largement, et il me semble qu'il était plus fort que le produit 3^m *5^p * 7^q.
par Olympus » 23 Aoû 2013, 19:54
Moi perso j'ai fait un peu plus bourrin ( pas eu le réflexe d'utiliser la formule de Legendre dès le départ mais on arrive à un truc plus ou moins pareil à la fin ) :
On a \right) \left( \prod_{ 0 \leq 2i \leq n-1 } \left( 2i+1 \right) \right) = 2^{\lfloor \frac{n}{2} \rfloor} \left( \lfloor \frac{n}{2} \rfloor \right)! \prod_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( 2i+1 \right))
(*)
Et là ( après avoir réitéré sur!)
au brouillon ) on a envie d'introduire les suites )
, )
et )
définies par :
 \left( \prod_{i=0}^{\lfloor \frac{a_{k-1}-1}{2} \rfloor } \left( 2i+1 \right) \right), \forall k \in \mathbb{N}^* \end{aligned} \right.)
Après, on remarque que si on réitère
fois ce qu'on a fait pour obtenir la formule (*) on obtient :
(**)
Mais la suite)
stationne en zéro à partir d'un certain rang 
( par exemple  }{ \ln \left( 2 \right) } \rfloor + 1)
).
Ainsi en remplaçant par dans (**) on obtient :
( 
étant impaire, tout ce que j'ai fait ici en fait c'est juste aboutir à un truc qui ressemble plus ou moins à la formule de Légendre, puisque 
n'est autre que la valuation 2-adique de 
)
On montre facilement que<n)
(***)
Maintenant, si
avec 
, alors )
La majoration (***) nous donne alors immédiatement=0)
.
Ainsi le problème revient à trouver les entiers vérifiant =n-1)
et ça c'est facile à faire en écrivant un programme ( avec la formule pour démontrée ici ou la formule de Légendre ), j'en ai d'ailleurs fait un en C : http://pastebin.com/kPG4ZWBs
On a
Et là ( après avoir réitéré sur
Après, on remarque que si on réitère
Mais la suite
Ainsi en remplaçant
On montre facilement que
Maintenant, si
La majoration (***) nous donne alors immédiatement
Ainsi le problème revient à trouver les entiers
par adrien69 » 23 Aoû 2013, 20:10
Franchement tu m'as perdu à la seconde ligne (ce genre de preuve me donne des boutons).
par adrien69 » 23 Aoû 2013, 20:11
Tu serais pas algébriste ? "Plus on complique et plus c'est clair".
par Olympus » 23 Aoû 2013, 21:07
adrien69 a écrit:Tu serais pas algébriste ? "Plus on complique et plus c'est clair".
:ptdr: :ptdr:
Nan en fait j'ai totalement perdu de tête la formule de Légendre ( longtemps que j'ai pas touché à l'arithmétique ), du coup j'ai commencé à faire un truc moche, mais bon disons que c'est le genre de preuves qu'on ne peut comprendre que si on les refait au brouillon
( ie écrire la première ligne de ma preuve, puis refaire le même procédé mais pour E(n/2) à la place de n et ainsi de suite, on voit apparaître les termes de mes trois suites et c'est pourquoi je les ai introduites ^^ )par adrien69 » 23 Aoû 2013, 21:50
Olympus a écrit::ptdr: :ptdr:
Nan en fait j'ai totalement perdu de tête la formule de Légendre ( longtemps que j'ai pas touché à l'arithmétique ), du coup j'ai commencé à faire un truc moche, mais bon disons que c'est le genre de preuves qu'on ne peut comprendre que si on les refait au brouillon
Il est hors de question que je fasse ça par moi-même. Je veux bien que tu sois masochiste, ne m'oblige pas à l'être
15 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 9 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :