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
93 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 huit mois
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 huit mois et a été effectuée par AD.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois
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 huit mois
Ce sont des entiers strictement positifs ?
Re: ensemble contenant tous les premiers entiers
il y a huit mois
Oui, désolée du délai de réponse.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a été effectuée par Chaurien.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois
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 huit mois et a été effectuée par Math Coss.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
Bien vu !
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a été effectuée par Aline Delves.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a été effectuée par AD.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
@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 huit mois
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 huit mois et a été effectuée par BCO.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a été effectuée par Fin de partie.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois
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 huit mois et a été effectuée par Fin de partie.
BCO
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a &eacute;t&eacute; effectu&eacute;e par BCO.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
@Fdp
Non tu as perdu la notion de permutation.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois
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 huit mois et a &eacute;t&eacute; effectu&eacute;e par abstract.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a &eacute;t&eacute; effectu&eacute;e par abstract.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois
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 huit mois
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 huit mois
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 huit mois et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: ensemble contenant tous les premiers entiers
il y a huit mois
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 huit mois et a &eacute;t&eacute; effectu&eacute;e par gerard0.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Bonjour,
Soit un ensemble de "n" nombres entiers consécutifs (1,2,…,n),
saurait-on démontrer si oui ou non, il y a unicité de l’écriture de leur somme et de leur produit ?
Rien trouvé sur le web.
Merci
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Salut.
Est ce que ta question n'est pas mal posée @abstract ?
Vous voulez parler de l'unicité de la liste comme dans le fil?
Si c'est ça, la somme et le factoriel ne suffisent pas, comme j'en ai parlé plus haut (parce les équations de la forme $ac + bc' +c'' = a + b + cc'c''$ ont des solutions pour n assez grand).
Par exemple, la liste $ {1, 2, 3, 4, 10, 6, 7, 8, 9, 10, 11, 12,....39, 80,41,...., 58, 59, 15}$ pour $n = 60$..

Mais je ne sais plus pourquoi je suis revenu sur le produit des factorielles (même sans la somme)?

Cordialement
Re: ensemble contenant tous les premiers entiers
il y a sept mois
@babsgueye
Excellent ! C'est cela que je cherchais et que votre contre exemple argumente :
Sum[n, {n, 1, 60}] +(-5+10)+(-40+80)+(-60+15) = Sum[n, {n, 1, 60}]
[goo.gl]
Product[n, {n, 1, 60}] +(-5+10)+(-40+80)+(-60+15) = Product[n, {n, 1, 60}]
[goo.gl]
Merci beaucoup



Edité 2 fois. La derni&egrave;re correction date de il y a sept mois et a &eacute;t&eacute; effectu&eacute;e par abstract.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Dans la même veine : Sums of Consecutive Integers
[arxiv.org]
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Intéressant !

merci.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Bonjour,

Pour rebondir sur le contre-exemple de babsgueye, pour tous $x,y,z$ réels, les trois nombres $x,yz^2,y(z+1)-x$ et les trois nombres $xz,y,z(y(z+1)-x)$ ont la même somme et le même produit. Il est donc vain, en général, d'espérer réaliser le voeu d'Aline à l'aide des seul.E.s (en ce cas particulier, je le confesse, je suis d'accord avec Chaurien!) somme et produit des éléments de son ensemble.
Le contre-exemple de babsgueye correspond à mon $(x,y,z)=(5,15,2)$ qui donne respectivement $\{5,60,40\}$ et $\{10,15,80\}$. Il y a plus "petit", à savoir $(x,y,z)=(1,3,2)$ qui donne respectivement $\{1,12,8\}$ et $\{2,3,16\}$.
Cordialement
Paul
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Bonjour.

Je sais pas pourquoi, on est tombé pile sur $n=60$ avec le lien de @abstract, mais on a aussi bien la liste ${2, 2, 3, 4, 10, 6, 7, 2}$ qui correspond à $n=8$ seulement...

Pour satisfaire @Aline pourquoi le produit des factorielles des éléments de la liste ne marche pas ?

Cordialement
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Bonjour,

On peut chercher une fonction croissante P qui grandit suffisamment rapidement pour que l'application qui à une famille non ordonnée d'entiers associe la somme de leurs images par P convienne, comme dans l'exemple de rosab pour $n=7$.

Par exemple, si on prend $P(n+1) > P(n)×(n+1)$, alors c'est bon. En effet, si $P(x_1) + \cdots + P(x_k) = P(1) + \cdots + P(k)$, alors avec $M := \max(x_1,\dots,x_k)$ on a :

* Si $M < k$, alors $P(k) > k × P(k-1) > k×P(M)$.
* Si $M > k$, alors $P(M) > (k+1) × P(k)$.

On peut alors éliminer $k$ et se ramener à $k-1$.

On peut donc prendre $(x_1+1)! + (x_2+1)! + \cdots + (x_k+1)!$. Pour $k$ fixé, on peut prendre les puissances $k$ièmes ?



Edité 1 fois. La derni&egrave;re correction date de il y a sept mois et a &eacute;t&eacute; effectu&eacute;e par Champ-Pot-Lion.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Citation
Champ-Pot-Lion
Pour k fixé, on peut prendre les puissances kièmes ?

Là on n'est pas dans le cadre de ta démonstration, et donc pour k assez grand on peut peut-être trouver un contre-exemple !
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Bonsoir, voilà en une seule opération le résultat requis ; il suffit de copier/coller la séquence "n".

Exemple pour n= {1,2,3,4,5,6,7,8,9}, soit 9 nombres
F_(Length[n]+2)-1 // (accumulate F_n) , for n={ 1,2,3,4,5,6,7,8,9} [goo.gl] donne
{1, 2, 4, 7, 12, 20, 33, 54, 88}(88) ; jumeaux 88,88, donc la séquence contient exactement les n premiers entiers (1,2,…,n)

Exemple pour n={1,2,3,4,6,6,6,8,9 }, soit 9 nombres
F_(Length[n]+2)-1 // (accumulate F_n) , for n={ 1,2,3,4,6,6,6,8,9 } [goo.gl] donne
{1, 2, 4, 7, 15, 23, 31, 52, 86}(88) ; dizigotes 86,88, donc la séquence ne contient pas exactement les n premiers entiers (1,2,…,n)
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Oups, c'est en prenant $P(n) = (n+1)!$ que l'on a $P(n) > n P(n-1)$. Pas en prenant $P(n) = n!$. Je rectifie.

Pour que le raisonnement s'applique jusqu'au rang $k$, avec $P$ croissante, il suffit que pour tout $k' \leq k$, on ait $\frac{P(k'+1)}{P(k')} > k'+1$. Pour chaque $k$, il y a un $p$ tel que $P(x) = x^p$ convienne (et le plus petit $p$ convenant augmente strictement dès qu'on augmente $k$ strictement).
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Salut.

@Champ-Pot-Lion, quand vous choisissez la fonction $P(x) = x!$, pourquoi avez-vous besoin de l'idée de récurrence ? Cela marche pour chaque $n$. Et puis est-ce que l'inégalité large ne suffit pas ? Je pense que si ! Et donc $P(n) = n!$ pourra marcher avec ton raisonnement (sous entendu que $P(k)$ n'est pas le seul élément de la liste des $P(i)$) )

Sinon je ne comprends pas pourquoi vous prenez à la fin, la somme des $(x_{i} + 1)!$ et pas seulement la somme des $x_{i}!$

Cordialement..



Edité 1 fois. La derni&egrave;re correction date de il y a sept mois et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Salut,

Ça fonctionne aussi avec l'inégalité large et donc $n!$, oui. Je prenais une égalité stricte parce que je n'avais pas pensé que pour $k>1$ la somme des $P(x_i)$ est strictement supérieure à $P(\max_i x_i)$.

> pourquoi avez-vous besoin de l'idée de récurrence ?

Je ne comprends pas la question. Dans ce que j'ai dit on montre que si on a la bonne somme, $k$ apparaît forcément parmi les $x_i$. Donc on peut retirer $P(k)$ de la somme, des deux côtés (le premier étant $P(x_1) + \cdots + P(x_k)$ et le deuxième $P(1)+\cdots+P(k)$). Et on se ramène alors à $k-1$.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Ah, ok je vois ta rigueur.

Merci.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
Bonsoir,

Citation
rosab
Ce que demande Aline Delves est une "fonction", et non un algorithme.

@rosab (et @ Aline Delves): je ne comprends pas pourquoi vous considérez que l'algorithme de Math-coss n'est pas une "fonction".

Cordialement
Paul

Edit: j'ai "envoyé" au lieu de "aperçu". Je poursuis:

@abstract: l'affirmation que tout entier est d'une seule façon la somme de nombres de Fibonacci non consécutifs (cf([blogdemaths.wordpress.com] paragraphe 6) est fausse: à "non consécutifs", il faut rajouter "et différents". Ca jette une suspicion sur ton idée, mais ne prouve pas qu'elle est mauvaise!

@babsgueye: ton produit des factorielles est-il juste une idée comme ça ou as-tu des arguments pour conforter ta conjecture?



Edité 1 fois. La derni&egrave;re correction date de il y a sept mois et a &eacute;t&eacute; effectu&eacute;e par depasse.
Re: ensemble contenant tous les premiers entiers
il y a sept mois
avatar
Bonjour.

Le produit des factorielles était juste une idée; qui ne marche pas d'ailleurs. Parce que si on prend un $n$ tel que $n + 1$ est une factorielle, on trouve un contre-exemple.

Merci.



Edité 1 fois. La derni&egrave;re correction date de il y a sept mois et a &eacute;t&eacute; effectu&eacute;e par AD.
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: 129 574, Messages: 1 244 795, Utilisateurs: 21 422.
Notre dernier utilisateur inscrit Elliot le coyotte.


Ce forum
Discussions: 4 661, Messages: 55 495.

 

 
©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