Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
193 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Factorielle allégée

Envoyé par pourexemple 
Factorielle allégée
il y a quatre années
avatar
Bonjour,

la factorielle allégée

On note $(n!)_2$ la factorielle de n alléger de 2, qui est le produit des nombres entre 1 et n, à l'exception des nombres pairs.

Calculer :$(2^{77}!)_2 \mod 2^{101}$

PS : l'usage de la calculatrice est recommandée.

Bonne journée.
Re: Factorielle allégée
il y a quatre années
Dans pas mal de bouquin, ce que tu appelles "factorielle allégée" est noté $(2n)!!$.
Re: Factorielle allégée
il y a quatre années
avatar
Et comment note-t-on la factorielle allégée de 101 : $(n!)_{101}$ ?
Re: Factorielle allégée
il y a quatre années
avatar
Le reste demandé (bien que la question soit mal posée je l'ai comprise de la sorte) est, sauf erreur,:

$1045593516627615941359991749983$

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Factorielle allégée
il y a quatre années
avatar
Peux tu me dire l’ambiguïté que tu vois dans l'énoncé proposé, en effet je ne trouve pas le même résultat que toi ?

De toutes les façons ce qui compte plus que le résultat c'est la méthode pour y arriver, donc si tu pouvais décrire ton algorithme en quelques mots cela serait mieux.
Re: Factorielle allégée
il y a quatre années
avatar
la notation $a \mod{n}$ ne signifie pas le reste dans la division euclidienne de $a$ par $n$.

J'ai mal lu la factorielle. grinning smiley

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Factorielle allégée
il y a quatre années
Je tente : 629631687561599003969942716417
Re: Factorielle allégée
il y a quatre années
avatar
J'aurais aimé que tu me résumes comment tu as procédé, inutile de rentrer dans les détailles trois phrases de moins d'une ligne chacune devrait être amplement suffisante.

Merci.
Re: Factorielle allégée
il y a quatre années
Je n'ai même pas cherché de démo. J'ai regardé l'écriture binaire de $(2^n!)_2$ pour les premières valeurs de $n$, i.e j'ai décomposé $(2^n!)_2$ comme somme de puissances de $2$. Il est facile de conjecturer quelles sont les plus petites puissances de $2$ qui interviennent dans cette décomposition. Et pour les plus grandes, on s'en fiche, puisque pour $n=77$, elles dépasseront $2^{101}$.
En me basant sur ma conjecture, ça donne alors la valeur que j'ai postée.
Re: Factorielle allégée
il y a quatre années
avatar
Bravo, je trouve la même chose que toi, mais pas par le même chemin.

Avant de donner ma solution (qui est simple), j'attends que ceux qui prétendent que cette exercice est classique, donne la solution classique.

A noter que par cette méthode on peut calculer des choses plus biscornues comme :
$(2^{77}!)_{2,3} \mod 2^{101}$ ou encore $\sum \limits_{i\in [0,2^k]} f^i(0) \mod 2^{101}$ avec $f$ un polynôme quelconque, avec $f^2(x)=f(f(x))$.

La seule limite semble être notre imagination ( : j'exagère un peu)



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Re: Factorielle allégée
il y a quatre années
Factorielle allégée=factorielle de Morita.
Gros classique
Re: Factorielle allégée
il y a quatre années
avatar
Aurais-tu un lien vers ce classique ?

Merci.
Re: Factorielle allégée
il y a quatre années
Et donc finalement, quelle est ta solution simple ?
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

J'attends d'avoir un lien vers ce classique ou qu'on explicite clairement le procédé et alors je donnerais la solution que je crois connaître.

Bonne journée.
Re: Factorielle allégée
il y a quatre années
Bon, il semblerait que cette solution simple n'existe pas. Peux-tu nous faire part de tes lumières, maintenant ?
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

C'est bien ce que je me disais...

Mais laissons un jour à ceux qui prétendent que cette énoncé est un classique, pour produire la réponse classique...

Passer ce délai je publierai, la solution que je crois connaître.

Bonne journée.
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

Je t'ai envoyé la réponse par MP.

Bonne journée.
Re: Factorielle allégée
il y a quatre années
Joaopa est un troll. Peux-tu rendre publique ta solution ? Ça ne sert à rien de la dissimuler... Et ça intéresse certains d'entre nous.
Re: Factorielle allégée
il y a quatre années
avatar
Ok, sans problème :
On pose $P_{n}(X)=X(X+1)...(X+n-1)$ on a pour tout $k\in \Z$, $n!|P_n(k)$, et $104! \mod 2^{101}=0$.
Alors pour tout $k \in\Z_{2^{101}}$ $P_{104}(k) \mod 2^{101}=0$.

On travaille dans l'anneau $\Z_{2^{101}}$, alors on pose :
$R_0(X)=2X+1$
$R_{k+1}(X)=R_k(X)\times R_k(X+2^{k}) \mod P_{104}(X)$
On calcule $R_{76}(X) \mod P_{104}(X)$ et $R_{76}(0)=(2^{77})_2 \mod 2^{101}$.

Si vous avez des questions n'hésitaient pas.

Bonne journée.



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Re: Factorielle allégée
il y a quatre années
Sans question et sans réfléxion:
Conséquence directe de Proposition 11.6.15 de Henri Cohen Number theory Vol.2

Signé: le troll
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

Quelqu'un peut-il nous dire ce qu'énoncerait cette proposition ?

Merci.



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

Non, personne ?

Même pas Joaopa ?

Bonne journée.
Re: Factorielle allégée
il y a quatre années
Avec un peu de chance tu trouveras peut être ici:
book
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

Il n'y a pas la p 374, partie 11.6.1.
Mais il parle de la fonction gamma sur les nombres p-adics donc approprie cela n'a qu'un rapport lointain avec la question initiale (calcul de la factorielle allégé).

Bonne journée.
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

En laissant de côté cette polémique avec Jaoapa, êtes vous d'accord pour qualifier de simple la solution proposée ?

PS : du coup c'est moi qui ait besoin de vos commentaires pour faire avancer mes recherches.

Bonne journée.
Re: Factorielle allégée
il y a quatre années
avatar
Bonsoir,

à noter qu'ainsi on peut construire un protocole d'échange de clef secrète.

Bonne soirée.
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

Oui, mais alors il ne serait pas sûr.

Bonne journée.



Edité 4 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Re: Factorielle allégée
il y a quatre années
avatar
Bonjour,

Un nouveau résultat sur la factorielle allégée : [www.les-mathematiques.net]

Bonne journée.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 341, Messages: 1 508 963, Utilisateurs: 27 697.
Notre dernier utilisateur inscrit J-Maths.


Ce forum
Discussions: 5 613, Messages: 67 912.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page