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
242 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
 
 
 
 
 

ensemble contenant tous les premiers entiers

Envoyé par Aline Delves 
ensemble contenant tous les premiers entiers
il y a dix jours
Bonjour,
Quel est le moyen le plus simple (ou peut-être existe-t-il un moyen...) de savoir qu'un ensemble de $n$ nombres contient exactement les $n$ premiers entiers ($1,2,\ldots,n$) ?
En calculant leur somme, on obtient $n(n+1)/2$ mais il y a d'autres ensembles de $n$ nombres qui ont même caractéristique (on imagine augmenter l'un des nombres de la suite des $n$ premiers entiers de $k$ et diminuer un autre de $k$, ou autre moyen).
Merci à ceux qui auraient une réponse ou à ceux qui pourraient me fournir des références bibliographiques à ce sujet.
Aline

[Ajouté la liste des $n$ premiers entiers pour ne pas confondre avec $n$ entiers premiers. smiling smiley AD]



Edité 1 fois. La dernière correction date de il y a dix jours et a été effectuée par AD.
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Ce n'est pas très clair. Dans le même ordre d'idée, le produit des $n$ premiers entiers donne $n!$...
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Bonjour,
J'essaye de m'expliquer mieux : j'ai un ensemble de $n$ nombres $\{x_1,x_2,\ldots,x_n\}$. Quel moyen me permet de savoir que mon ensemble de nombres contient tous les nombres de 1 à $n$. Si je calcule la somme des nombres de mon ensemble, si je trouve par exemple une somme de 10 pour 4 nombres, peut-être que l'ensemble est $\{1,2,1,6\}$. Peut-être est-ce parce que j'ai utilisé le mot ensemble alors qu'il peut y avoir plusieurs occurrences d'un même nombre que ce que j'ai écrit n'était pas clair...
Cordialement,
Aline
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Ce sont des entiers strictement positifs ?
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Oui, désolée du délai de réponse.
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Alors tu peux tester successivement s'ils sont tous distincts, non ?
Le deuxième distinct du premier, le troisième non dans l'ensemble des deux premiers, et ainsi de suite...



Edité 1 fois. La dernière correction date de il y a dix jours et a été effectuée par Chaurien.
Re: ensemble contenant tous les premiers entiers
il y a dix jours
A priori, s'il s'agit d'un programme informatique, il suffit de les trier (*), puis de tester qu'ils ont bien successivement 1, 2, 3, ..., n.
Si on a des connaissances sur l'origine des n nombres, on peut faire mieux. Et aussi si n est petit (rechercher directement 1, puis, dans ceux qui restent, 2, etc.).

Cordialement.

(*) algorithme quicksort, très efficace si n est grand.
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Commencer par trier les $x_i$, c'est une complexité en $n\log(n)$, ce qui peut être considéré comme efficace, comme dit Gérard. Mais on doit pouvoir obtenir une complexité linéaire avec un « histogramme » y.
Donnée : tableau x = [x[1],...,x[n]]
Sortie : vrai si x contient 1,...,n, faux sinon.
Corps :
    initialiser deux variables :
        tableau y = (0,...,0) de longueur n
        entier m = 0
    pour k de 1 à n faire :
        y[x[k]] = y[x[k]] + 1
        si y[x[k]] == 2 :
            renvoyer faux
        si x[k] > m:
            m = x[k]
    si m == n:
        renvoyer vrai
    sinon:
        renvoyer faux
Justification : si on sort de la boucle, tous les y[ i] valent au plus 1 donc les x[k] sont distincts ; par le principe des tiroirs, le maximum vaut au moins n.

PS : Je n'ai rien inventé, c'est une réminiscence de lectures (Cormen et al. ?). Les histogrammes permettent de trier une liste d'entiers en temps linéaire si on sait a priori qu'ils sont tous dans un intervalle fixé.



Edité 1 fois. La dernière correction date de il y a dix jours et a été effectuée par Math Coss.
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Bien vu !
Re: ensemble contenant tous les premiers entiers
il y a dix jours
Bonjour et merci,
Non, ce n'était pas un programme que je souhaitais, c'était une fonction : en calculant la somme des différences 2 à 2 pour les nombres de 1 à 5, j'avais trouvé 20 mais c'était un hasard (que ça vaille $n(n-1)$), je pensais qu'il existait peut-être une formule, qui minimisait quelque chose, une sorte de distance, pour dire qu'ils étaient bien espacés de 1 en 1, que l'espacement était régulier.
Je vous remercie bien d'avoir réfléchi en tous cas.
Cordialement,
Aline



Edité 1 fois. La dernière correction date de il y a dix jours et a été effectuée par Aline Delves.
Re: ensemble contenant tous les premiers entiers
il y a six jours
avatar
Bonjour.

L'addition étant commutatif, je pense que le problème d'ordre est à évacuer dans votre question. C'est vrai qu'il suffit qu'ils (les $n$ nombres) soient tous distincts. Pour cela, je pense qu'en plus de leur somme, ils suffira de vérifier que la somme de leurs carrés est égale à

$\dfrac{n(n + 1)(2n + 1)}{6}$, pour $n$ nombres.

Merci.



Edité 1 fois. La dernière correction date de il y a six jours et a été effectuée par AD.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
@babsgueye

Bonjour,
la somme des carrés ne suffit pas :
$$7+4+3+3+2+2 = 6+5+4+3+2+1 = 21$$
$$7^2+4^2+3^2+3^2+2^2+2^2 = 6^2+5^2+4^2+3^2+2^2+1^2 = 91$$

Intuitivement, on doit pouvoir utiliser une fonction symétrique des $x_i$ de degré de plus en plus élevé avec $n$.
C'est un problème diophantien intéressant.
BCO
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
Si l'ensemble est infini alors la densité de Schnirelmann devrait faire le job et être égale à 1 si et seulement si l'ensemble contient tous les entiers (cf. wiki)

Pour le cas où l'ensemble est fini, ne peut-on pas jouer avec les nombres transcendants ?
Par exemple en calculant la somme des exponentielles de chaque élément : cette somme devrait être logiquement égale à $\frac{e^{n+1}-e}{e-1}$...



Edité 1 fois. La dernière correction date de il y a cinq jours et a été effectuée par BCO.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
avatar
On peut aussi considérer le polynôme $P_n(x)=(x-1)(x-2)...(x-n)$ et vérifier si les $x_i$ sont racines (tout en s'assurant que les $x_i$ sont distincts et inférieurs où égaux à $n$).
Calculer les coefficients de ce polynôme a un coût en temps mais si on a l'intention de tester plusieurs fois qu'une suite de $x_i$ convient ce coût peut être acceptable.

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.



Edité 1 fois. La dernière correction date de il y a cinq jours et a été effectuée par Fin de partie.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
Ce que demande Aline Delves est une "fonction", et non un algorithme. Il faut tout tester d'un coup.
Par exemple, si $n=7$, le polynôme $x_1^5+x_2^5+x_3^5+x_4^5+x_5^5+x_6^5+x_7^5-29008$ s'annule si et seulement si les $x_i$ (entiers strictement positifs) forment une permutation des nombres de $1$ à $7$.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
avatar
Rosab:

Il n'est pas difficile de transformer mon algorithme en fonction me semble-t-il:

Soit $P_n(x)=(x-1)(x-2)...(x-n)$

On considère la fonction $\displaystyle F(x_1,x_2,...,x_n)=\mid P_n(x_1)\mid+\mid P_n(x_2)\mid+...+\mid P_n(x_n)\mid$

PS:
Cela ne fonctionne pas. Désolé.

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.



Edité 1 fois. La dernière correction date de il y a cinq jours et a été effectuée par Fin de partie.
BCO
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
Dans le même esprit que la proposition de FDP et sauf erreur de ma part :
Soit le polynôme $P(x) = \sum_{k=1}^{n} x^{a_k}$
On note $P^{(k)}$ la dérivée $k^{ème}$ de $P$.
Alors l'ensemble $A$ contient exactement tous les $n$ premiers entiers strictement positifs si et seulement $P^{(k)}(0) = k!$ pour tout $1<=k<=n$



Edité 2 fois. La derni&egrave;re correction date de il y a cinq jours et a &eacute;t&eacute; effectu&eacute;e par BCO.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
@Fdp
Non tu as perdu la notion de permutation.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
avatar
Rosab:
Le problème n'est pas celui-là. Le problème est que je suppose implicitement que les $x_i$ sont distincts.

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
Une piste ?
Somme des termes successifs de la suite de Fibonacci
[jm.davalan.org]

Soit les sommes
1+2+3+4+5+6+7+8+9 = 1+2+3+4+6+6+6+8+9

Fibonacci (n+2)-1 contient n nombres successifs
F_(n+2) se calcule avec Binet [goo.gl]

(F_1 + F_2 + F_3 + F_4 + F_5 + F_6 + F_7 + F_8 + F_9) = F_(n+2) -1 = F_(11) - 1 = 88 [goo.gl]

Si j’ai « n » nombres, je peux avec la formule de Binet vérifier par exemple que
(F_1 + F_2 + F_3 + F_4 + F_6 + F_6 + F_6 + F_8 + F_9) = 86 [goo.gl]
n’a pas cette propriété

Reste à démontrer que cette propriété est toujours valable



Edité 5 fois. La derni&egrave;re correction date de il y a cinq jours et a &eacute;t&eacute; effectu&eacute;e par abstract.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
Une autre solution "théorique" est d'associer chaque nombre a_i de l'ensemble de n nombres à un prime(a_i)
et de vérifier si on reçoit bien primorial(a_n) ... calculateur connaissant les premiers oblige.



Edité 3 fois. La derni&egrave;re correction date de il y a cinq jours et a &eacute;t&eacute; effectu&eacute;e par abstract.
Re: ensemble contenant tous les premiers entiers
il y a cinq jours
Pour la somme Fibonacci, la réponse ici peut-être :
"Nous pouvons passer à présent à la preuve de l’unicité de l’écriture d’un entier comme somme de nombres de Fibonacci consécutifs."
[blogdemaths.wordpress.com]
paragraphe 6
Re: ensemble contenant tous les premiers entiers
il y a quatre jours
avatar
Salut.

On peut, je pense utiliser la factorielle. Vérifier qu'il est nécessaire et suffisant d'avoir $x_{1}!*x_{2}!*...*x_{n}! = \prod_{i=1}^{n}i^{(n-i+1)}$

où $(x_{1}, x_{2},...,x_{n})$ est la liste des n nombres, et $x_{i}!$, la factorielle de $x_{i}$..
Re: ensemble contenant tous les premiers entiers
il y a quatre jours
avatar
La seule factorielle n'est pas suffisant. Il va falloir utiliser la somme aussi.

Mais avec la somme, est ce que le produit des factorielles n'est pas très fort ? Utiliser seulement $n!$ doit suffir. On peut essayer de le démontrer.

Ce sera des équations de la forme $ab + 1 = a + b$ qui n'a pour solution que $a = b =1$, or $ab\neq1$....

Cordialement.
Re: ensemble contenant tous les premiers entiers
il y a trois jours
Je crois me souvenir que la seule suite telle que $\quad\displaystyle \forall n,\ \sum^n x_k^3=\Big(\sum^n x_k\Big)^2\ $ est la suite $x_k=k$.

Une solution pourrait être de ranger les entiers dans l'ordre croissant (sens large)
puis d'examiner ces sommes.



Edité 1 fois. La derni&egrave;re correction date de il y a trois jours et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: ensemble contenant tous les premiers entiers
il y a trois jours
Un rappel : http://www.les-mathematiques.net/phorum/read.php?5,1574872,1574992#msg-1574992
Même pas besoin de tri



Edité 1 fois. La derni&egrave;re correction date de il y a trois jours et a &eacute;t&eacute; effectu&eacute;e par gerard0.
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: 124 398, Messages: 1 187 864, Utilisateurs: 19 578.
Notre dernier utilisateur inscrit beki.


Ce forum
Discussions: 4 387, Messages: 52 442.

 

 
©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