nombres premiers

[invite0496604c]

Si vous etes interressé par les nombres premiers , il y a un livre très bien fait :
Auteur : Delahaye Jean-Paul Titre : Merveilleux nombres premiers.

-----

[invite58f1e2bf]

Pourtant, un algorithme de calcul des nombres premiers est une sorte de représentation comprimée de l'ensemble des nombres premiers, non ?

[inviteb9b852ac]

Hum, je dirais que l'ensemble des nombres premiers est imcompressible. N'oublions qu'un algorithme s'effectue en un nombre fini d'opérations. C'est comme dire que N² peut-être "comprimé" dans N (c'est une mauvaise interprétation sur des espaces infinis, i.e il existe une bijection de N dans N²)

[invite88ef51f0]

Oui, mais il faudrait un temps infini... Tu peux même faire un algorithme qui fait les entiers naturels en quelques lignes

EDIT : Je répondais à Gilllloux

[invite58f1e2bf]

Prenons, l'ensemble des nombres pairs. Cet ensemble est compressible (enfin je crois), pourtant il faut un temps infini pour générer cet ensemble.

[invite88ef51f0]

Euh... Excusez-moi de vous demander pardon, mais mathématiquement ça veut dire quoi "compressible" ?

[invite58f1e2bf]

Alors ca, moi, j'en sais rien ! Mais au 'feeling' je dirais que en tout cas, l'ensemble des nombres pairs est compressible...

[invite58f1e2bf]

Oui, bon, peut-etre pas en fait, mais bon. En tout cas, je pense qu'il ne suffit pas qu'un ensemble soit infini pour etre incompressible.

[inviteb9b852ac]

Non, bien sûr que non. Mon exemple sur N² était pour exprimer autre chose. Donc je me suis mal exprimé.
Précisons. On parle plus de complexité d'une suite (de nombres, de chiffres comme pour pi ou oméga). Si une suite n'est pas due au hasard (aléatoire), on peut la réduire à un algorithme, c'est-à-dire qu'il existe une formule pour la suite plus courte que la suite elle-même (comme pour N²). A vérifier, mais je crois que la suite des nombres premiers est aléatoire (si on connaissait une régularité, on se prendrait pas la tête), donc la complexité de cette suite est irréductible. Si tu veux programmer cette suite, le programme sera aussi long, complexe, que la suite elle-même.
Voila, voila, c'est lié tout cela à Gödel & Co.

[invite7553e94d]

quel que soit n:
n!+2 est divisible par 2 (2 et n! le sont)
n!+3 est divisible par 3
n!+x est divisible par x (2<=x<=n)

on a donc n-1 nombres consécutifs non premiers.

n! + n est lui aussi non premier (multiple de n)

[invitef6a8dd1c]

Oui, et il est inclus dans les nombres que donnait gargulp

n!+x est divisible par x (2<=x<=n)

On n'en a que n-1 parce qu'on commence à 2

Geoffrey

[invite7553e94d]

je n'avais pas vu le superieur ou egal, pardon.