Les théorèmes compris entre 1 et 1000000
Je ne dispose pas d'outil de programmation au bahut, quelqu'un pourrait-il produire un fichier avec tous les théorèmes (linéaires) *** compris entre 1 et 1000000. C'est 10mn de programmation, je remercie infiniment qui voudra bien avoir envie pour lui-même aussi, de le faire.
*** Soit $p$ la fonction qui à un entier $n$ associe le nième nombre premier**. Les théorèmes sont les éléments du plus petit ensemble $E$ qui contient tous les nombres de la forme $x\times p(x)$ et qui est stable par l'opération suivante:
La définition n'étant pas très parlante, il suffit, pour savoir si un nombre $n$ est un théorème qu'il puisse être factorisé sous une forme
$$ a\times p( p(b) \times c) \times d$$
telle que $cd$ et $ab$ soit tous deux des théorèmes, ce qui vous permet d'avoir une récurrence facile (jusqu'à 10^6, le crible d’Ératosthène permet d'avoir un tableau réalisant $p$ facilement)
Un grand merci à qui publiera cette liste, j'ai hâte de savoir à quoi elle ressemble, et surtout si elle ressemble à un ensemble déjà connu autrement.
Remarque: cet ensemble est NP-complet, mais quand on le lit directement écrit. Présentement, comme on ignore la complexité réelle de la factorisation des entiers, ça compense et peut-être cet ensemble est-il "très simple".
** $p(1)=2; p(2)=3; p(3)= 5; p(4) = 7; p(5) = 11; etc$
*** Soit $p$ la fonction qui à un entier $n$ associe le nième nombre premier**. Les théorèmes sont les éléments du plus petit ensemble $E$ qui contient tous les nombres de la forme $x\times p(x)$ et qui est stable par l'opération suivante:
si $p(a) \times b\in E$ et $a\times c\in E$ alors $bc\in E$
La définition n'étant pas très parlante, il suffit, pour savoir si un nombre $n$ est un théorème qu'il puisse être factorisé sous une forme
$$ a\times p( p(b) \times c) \times d$$
telle que $cd$ et $ab$ soit tous deux des théorèmes, ce qui vous permet d'avoir une récurrence facile (jusqu'à 10^6, le crible d’Ératosthène permet d'avoir un tableau réalisant $p$ facilement)
Un grand merci à qui publiera cette liste, j'ai hâte de savoir à quoi elle ressemble, et surtout si elle ressemble à un ensemble déjà connu autrement.
Remarque: cet ensemble est NP-complet, mais quand on le lit directement écrit. Présentement, comme on ignore la complexité réelle de la factorisation des entiers, ça compense et peut-être cet ensemble est-il "très simple".
** $p(1)=2; p(2)=3; p(3)= 5; p(4) = 7; p(5) = 11; etc$
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
S
Mais c'est 10mn de programmation (en Python, j'imagine, je donne le temps CAML), peut-être quelqu'un ayant envie de s'entrainer à Python (qui semble confortable) le fera-t-il?
S
Marco pourquoi pas le million ?
S
[Edit : conjecture réalisée sans filet et sans ordinateur, je n'ai rien testé en fait ]
S
Forcément la proportion doit vite se raréfier puisque dans tout théorème X a autant d'occurrences négatives que d'occurrences positives!! Je suis étonné que ça ne se voit pas avant 50000 mais ça doit être dû à la façon dont les nombres premiers se répartissent. J'ai aussi vérifié sur quelques exemples si les nombres de marco sont bien des théorèmes et la réponse est oui.
Le codage d'un énoncé est le suivant:
X est codé par 1
A=>B est codé par p(a) fois b, où a code A et b code B
(
Par exemple 3 code (X=>X) =>X, 2 code X=>X, 4 code X=>(X=>X), 6 code ((X=>X)=>(X=>X))
Bien sûr, du fait de la commutativité, 6 code aussi X=>((X=>X)=>X). C'est même la raison d'être de ce codage, rendre blanche la commutativité (enfin le fait que [a=>(b=>c)] = )
Si je trouvais mieux, je serais content, mais des structures naturelles qui représentent cette commutativité tout en restant "assez libres"...
a) pour tout $x$, $p(x)x$ est un théorème, et si $p(a)b$ et $ac$ sont des théorèmes alors $bc$ est un théorème,
b) pour tout $x$, $p(x)x$ est un théorème, et si $ab$ et $cd$ sont des théorèmes, alors $ap(p(b)c)d$ est un théorème.
En effet, selon la première définition, $5$ est un théorème ($p(3)3=15$ est un théorème, donc $p(2)5=15$ est un théorème, et $p(1)1$ est un théorème et donc $2\times 1$ est un théorème: on déduit en choisissant $a=2,b=5,c=1$ que $bc=5$ est un théorème),
et pas selon la seconde.
Et $10$ est un théorème selon la seconde définition, mais ne semble pas en être un selon la première.
Voici une liste de théorèmes selon la première définition:
2 5 6 15 18 22 23 26 28 31 41 45 54 55 65 66 69 70 78 84 93 94 103 116 119 122 123 135 137 148 152 158 162 165 166 167 175 195 198 202 207 210 211 234 235 236
S
Si ab théorème et p(c)d théorème alors a fois p(p(b) fois c) fois d théorème. J'ai oublié un "p" dans les hypothèses, j'ai écrit cd au lieu de p(c)d. Vraiment désolé !