Bonsoir .
Bien, voilà mon interrogation existentielle du soir.

Le but du jeu est d'exprimer des propositions du style "<math>\(n\)</math> est un nombre premier" (on travaille uniquement dans <math>\(\mathbb{N}\)</math>) à l'aide de quelques opérations de base.
On a le droit à : l'addition, la multiplication, <math>\(\forall\)</math>, <math>\(\exists\)</math>, =, les opérateurs logiques <math>\(\wedge \vee \neg\)</math>, les parenthèses.

Par exemple :

"p divise n" (noté <math>\(p|n\)</math>): <math>\(\exists q, pq=n\)</math>
"A implique B" (noté <math>\(A \Rightarrow B\)</math>) : <math>\(\neg A \vee B\)</math>
"p est premier" : <math>\(p \ne 1 \wedge [\forall (q,r), qr=p \Rightarrow (q = 1 \vee r = 1)]\)</math>

Lorsqu'une proposition a déjà été exprimée de la sorte, on peut la réemployer dans les suivantes comme je l'ai fait à l'instant, par souci de simplification. Autre exemple :

"n est une puissance de 2" : <math>\(\forall p, (p \text{ est premier} \wedge p|n) \Rightarrow p = 2\)</math>

Pour vous faire la main, vous pouvez si vous voulez exprimer "n est une puissance de 4", ou encore "<math>\(n>m\)</math>".
A présent, un truc que je n'arrive toujours pas à exprimer malgré mes efforts : "n est une puissance de 10".

Quelqu'un saura-t-il m'y aider ?

ben <math>\(\exists k \in \mathbb{N} , n=10^k\)</math>

J'ai parlé de la mise à la puissance dans les opérations de base ?

Et je précise : pas le droit d'utiliser "..." ou autre pour simuler l'opération puissance, je veux uniquement des formules logiques correctement écrites et sans artifice...

Effectivement, j'ai lu trop vite. ça me paraissait bizare aussi...

Citation : Cyprien_

J'ai parlé de la mise à la puissance dans les opérations de base ?

Et je précise : pas le droit d'utiliser "..." ou autre pour simuler l'opération puissance, je veux uniquement des formules logiques correctement écrites et sans artifice...

Oui tu en as parlé pour les nombres premiers, sur le même modèle que "n est une puissance de 2" tu peux construire "n est une puissance de p" où p est un nombre premier,

"n est une puissance de 10" peut s'exprimer par :
"[pour tout p, (p est premier et p divise n)] => [((p = 5) ou (p=2)) et (10 divise n)]".

Citation : Cyprien_

Bonsoir .
Bien, voilà mon interrogation existentielle du soir.

Le but du jeu est d'exprimer des propositions du style "<math>\(n\)</math> est un nombre premier" (on travaille uniquement dans <math>\(\mathbb{N}\)</math>) à l'aide de quelques opérations de base.
On a le droit à : l'addition, la multiplication, <math>\(\forall\)</math>, <math>\(\exists\)</math>, =, les opérateurs logiques <math>\(\wedge \vee \neg\)</math>, les parenthèses.

Par exemple :

"p divise n" (noté <math>\(p|n\)</math>): <math>\(\exists q, pq=n\)</math>
"A implique B" (noté <math>\(A \Rightarrow B\)</math>) : <math>\(\neg A \vee B\)</math>
"p est premier" : <math>\(p \ne 1 \wedge [\forall (q,r), qr=p \Rightarrow (q = 1 \vee r = 1)]\)</math>

Lorsqu'une proposition a déjà été exprimée de la sorte, on peut la réemployer dans les suivantes comme je l'ai fait à l'instant, par souci de simplification. Autre exemple :

"n est une puissance de 2" : <math>\(\forall p, (p \text{ est premier} \wedge p|n) \Rightarrow p = 2\)</math>

Pour vous faire la main, vous pouvez si vous voulez exprimer "n est une puissance de 4", ou encore "<math>\(n>m\)</math>".
A présent, un truc que je n'arrive toujours pas à exprimer malgré mes efforts : "n est une puissance de 10".

Quelqu'un saura-t-il m'y aider ?

Ca marche ça ? (définition récursive) :
a^b=c signifie : <math>\((b=1 \wedge a=c) \vee (a*a^{b-1} = c)}\)</math>

Pour l'inégalité <math>\(n > m\)</math> :

<math>\((n > m) <=> \exists d, d \neq 0, n - d = m\)</math>

Vous en pensez quoi ?

Citation : jn-drk

Pour l'inégalité <math>\(n > m\)</math> :

<math>\((n > m) <=> \exists d, d \neq 0, n - d = m\)</math>

Vous en pensez quoi ?

C'est tout à fait ça l'idée (enfin, pour pas utiliser la soustraction, tu peux même passer d de l'autre côté, mais c'est chipoter, admettons qu'on a défini la soustraction :p).

Citation : robocop

<citation rid="5790348">Ca marche ça ? (définition récursive) :
a^b=c signifie : <math>\((b=1 \wedge a=c) \vee (a*a^{b-1} = c)}\)</math>

Eh non, c'est la première chose à laquelle j'ai pensé en découvrant ce problème et malheureusement, ce n'est pas acceptable .

Citation : lgndslpgs

<citation rid="5790845">Oui tu en as parlé pour les nombres premiers, sur le même modèle que "n est une puissance de 2" tu peux construire "n est une puissance de p" où p est un nombre premier,

"n est une puissance de 10" peut s'exprimer par :
"[pour tout p, (p est premier et p divise n)] => [((p = 5) ou (p=2)) et (10 divise n)]".

Raté, ça marche bien pour les nombres premiers, mais mal pour les autres nombres. Là, tu filtres tous les nombres de la forme <math>\(2^a5^b, (a,b) \in \mathbb{N}^{*2}\)</math>.

Citation : Cyprien_

"n est une puissance de 10" peut s'exprimer par :
"[pour tout p, (p est premier et p divise n)] => [((p = 5) ou (p=2)) et (10 divise n)]".

Raté, ça marche bien pour les nombres premiers, mais mal pour les autres nombres. Là, tu filtres tous les nombres de la forme <math>\(2^a5^b, (a,b) \in \mathbb{N}^{*2}\)</math>.</citation>

Tu as raison, ça ne filtre pas assez, rajoutons une condition :

"[[pour tout p, (p est premier et p divise n)] => [[((p = 5) ou (p=2)) et (10 divise n)]] et [[pour tout m, (m n'est pas premier et m divise n)] => (10 divise m)]] ".

lgndslpgs : Ta condition ne marche pas : 25(m) divise 100 (n)et 10 ne divise pas 25, alors que 100 est une puissance de 10

Ce que tu nous fais faire, Cyprien, c'est toutes les maths. Tu ne pourras pas faire la puissance de dix sans la récursion (ou récurrence), car déjà à l'origine, la puissance est définie par récurrence à partir de la multiplication (qui est définie par récurrence à partir de l'addition, qui elle-même est définie par récurrence à partir du successeur, dont l'existence est assurée dans l'axiomatique de Peano (les Règles de bases pour construire l'ensemble des nombres entiers))

Ne sois pas si sûr de toi collègue .

J'ai une solution (enfin, normalement...) !

Bien, commençons par définir "a est congru à b modulo n" :

<math>\(a \equiv b \pmod n \Leftrightarrow \exists k, a = b + kn\)</math>

Ensuite, pour <math>\(p\)</math> et <math>\(q\)</math> deux nombres premiers distincts, définissons <math>\(p^q\)</math> :

<math>\(n = p^q \Leftrightarrow n \equiv p \pmod q \wedge (n \text{ est une puissance de p}) \wedge [\forall m, m < n \Rightarrow (m \equiv p \pmod q \Rightarrow m \text{ n'est pas une puissance de p})]\)</math>

(Conséquence du petit théorème de Fermat, ce qui se trouve entre crochets signifiant simplement que n est le plus petit entier à vérifier la congruence et à être une puissance de p.)

A présent, on peut définir "n est une puissance de 10", mais ma solution est très laborieuse écrite en entier, je vous expose donc l'idée générale et donne après les cas particuliers. :

<math>\(\exists (p_1,p_2,p_3,p_4,p_5,p_6, p_7), (p_1, ..., p_7 \text{ sont premiers ou nuls})\wedge n=2^{p_1+...+p_7}5^{p_1+...+p_7}\)</math>

Ca, c'est le cas de base. Sauf qu'il est possible que certains des <math>\(p_i\)</math> soient nuls, il faut rapidement définir <math>\(p^0\)</math>, ce qui ne devrait pas poser de souci .
Autre cas particulier : un ou plusieurs des <math>\(p_i\)</math> est égal à 2 ou 5. Dans ce cas, je n'ai pas trouvé beaucoup mieux que d'introduire autant de propositions en disjonction que de cas possibles avec un ou plusieurs <math>\(p_i\)</math> valant 2 ou 5, et de remplacer ces termes directement par la constante <math>\(10^2\)</math> ou <math>\(10^5\)</math>.

Bref, c'est une solution très laborieuse, mais elle marche... Il est peut-être possible de la raccourcir en fait en s'autorisant des soustractions dans l'exposant ou encore plus de <math>\(p_i\)</math>, mais bref, maintenant que j'ai écrit tout ça, je ne l'efface plus .

Citation : Aniem

lgndslpgs : Ta condition ne marche pas : 25(m) divise 100 (n)et 10 ne divise pas 25, alors que 100 est une puissance de 10

Effectivement, j'écarte ce souci :

"[[pour tout p, (p est premier et p divise n)] => [[((p = 5) ou (p=2)) et (10 divise n)]] et [[pour tout m, (m n'est pas une puissance d'un nombre premier et m divise n)] => (10 divise m)]] ".

Citation : lgndslpgs

Citation : Aniem

lgndslpgs : Ta condition ne marche pas : 25(m) divise 100 (n)et 10 ne divise pas 25, alors que 100 est une puissance de 10

Effectivement, j'écarte ce souci :

"[[pour tout p, (p est premier et p divise n)] => [[((p = 5) ou (p=2)) et (10 divise n)]] et [[pour tout m, (m n'est pas une puissance d'un nombre premier et m divise n)] => (10 divise m)]] ".

200 vérifie la condition
De manière générale, Tout <math>\(2^a5^b\)</math> avec a et b non nuls vérifie ta condition il me semble

Cyprien_ : anéfé, ça a l'air de marcher, mais j'ai une question (peut-être bete, mais bon) : Une fois avoir défini <math>\(p^q\)</math>, pourquoi ne pas dire <math>\(n = 10^q \Leftrightarrow (\exists q, n = 2^q5^q)\)</math> ?
Bon, tu m'a prouvé tort sur ce point-là, mais j'emets tout de même de sérieux doutes quant au fait de pouvoir écrire n'importe quelle propriété sans passer par la récurrence... Même si je me souviens d'un exercice de caml de bluestorm qui consistait à faire du récursif sans "rec", on trichait car on utilisait une fonction définie avec "rec". Tout de même, on doit pouvoir passer aux propriétés sur <math>\(\mathbb Q\)</math>(et encore, j'ai parfois des doutes, même si par la construction même des rationnels, on doit facilement pouvoir les écrire qu'avec des entiers, quoique pour les propriétés de densité, j'ai des doutes...) on même l'ensemble des nombres algébriques, mais peut-on obtenir des propriétés sur des ensembles indénombrables? Peut-on exprimer (à long terme bien entendu) le théorème des valeurs intermédiaires ?

Pour la définition de l'inégalité, jn-drk a proposé une solution mais personne n'a répondu : à toi, je répondrais, que tu as montré la différence : en effet, si d est négatif, on a n-d = m => n < m et non n > m...
Le problème consiste donc simplement à dire qu'un nombre est positif ou non

AH oui c'est vrai ça n'arrange même pas le problème du 25.

si puisque 25 est une puissance d'un nombre premier, mais ça n'arrange que le 25 et autres

accessoirement, si seuls 2 et 5 divisent n, et que m divise n sans être une puissance d'un un nombre premier, alors automatiquement 10 divise m ... donc ta deuxième implication est une tautologie ... un peu inutile pour exprimer une propriété non?

Citation : lgndslpgs

"[[pour tout p, (p est premier et p divise n)] => [[((p (<- quel est ce p ?) = 5) ou (p (<- quel est ce p ?) =2)) et (10 divise n)]] et [[pour tout m, (m n'est pas une puissance d'un nombre premier et m divise n)] => (10 divise m (<- quel est ce m ?) )]] ".

Citation : Aniem

Cyprien_ : anéfé, ça a l'air de marcher, mais j'ai une question (peut-être bete, mais bon) : Une fois avoir défini <math>\(p^q\)</math>, pourquoi ne pas dire <math>\(n = 10^q \Leftrightarrow (\exists q, n = 2^q5^q)\)</math> ?

Eh bien... q doit être un nombre premier pour que ça marche, à la limite, c'est p qui n'aurait pas besoin d'en être, il suffirait que q ne divise pas p. Pour avoir q premier, je suis obligé de décomposer comme en bourrinant .

Citation : Aniem

Bon, tu m'a prouvé tort sur ce point-là, mais j'emets tout de même de sérieux doutes quant au fait de pouvoir écrire n'importe quelle propriété sans passer par la récurrence... Même si je me souviens d'un exercice de caml de bluestorm qui consistait à faire du récursif sans "rec", on trichait car on utilisait une fonction définie avec "rec". Tout de même, on doit pouvoir passer aux propriétés sur <math>\(\mathbb Q\)</math>(et encore, j'ai parfois des doutes, même si par la construction même des rationnels, on doit facilement pouvoir les écrire qu'avec des entiers, quoique pour les propriétés de densité, j'ai des doutes...) on même l'ensemble des nombres algébriques, mais peut-on obtenir des propriétés sur des ensembles indénombrables? Peut-on exprimer (à long terme bien entendu) le théorème des valeurs intermédiaires ?

Je n'ai jamais dit que c'était possible, mais à vrai dire, je tenais la proposition "n est une puissance de 10" d'un ami (encore un collègue ) qui m'assurait que c'était possible, donc je l'ai cru...
Après, je ne sais absolument si c'est de notre niveau de vouloir poursuivre plus loin...

Citation : Aniem

Pour la définition de l'inégalité, jn-drk a proposé une solution mais personne n'a répondu : à toi, je répondrais, que tu as montré la différence : en effet, si d est négatif, on a n-d = m => n < m et non n > m...

Je lui avais répondu, et j'avais dit au départ qu'on ne considérait que des entiers naturels, donc ça marche tout à fait ce qu'il a écrit .

@lgndslpgs : j'ai cherché pendant pas mal de temps une solution "simple" ou, au moins, élégante... Malheureusement je n'ai rien trouvé de mieux que le coup de décomposer à l'arrache l'exposant éventuel...

Citation : Thomash

Citation : lgndslpgs

"[[pour tout p, (p est premier et p divise n)] => [[((p (<- quel est ce p ?) = 5) ou (p (<- quel est ce p ?) =2)) et (10 divise n)]] et [[pour tout m, (m n'est pas une puissance d'un nombre premier et m divise n)] => (10 divise m (<- quel est ce m ?) )]] ".

Effectivement, il faut simplement sortir le "pour tout p" et le "pour tout m" de leurs crochets je pense .


Personne pour le "n est une puissance de 4" ? Je vous rassure, ça se fait en une très courte ligne en fait .

Le principe de récurrence est fondamental, c'est lui qui permet de définir les entiers. Pourquoi donc n'en veux-tu pas dans ton formalisme ?

Parce que ce n'est pas "mon" formalisme ? Quelqu'un m'a énoncé un problème, je n'ai fait que le reprendre ici.

Et honnêtement, ça fait un peu partie du défi : avec la récurrence, tout deviendrait franchement trop simple là .