ensemble contenant tous les premiers entiers
dans Arithmétique
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. :-) AD]
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. :-) AD]
Réponses
-
Ce n'est pas très clair. Dans le même ordre d'idée, le produit des $n$ premiers entiers donne $n!$...
-
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 -
Ce sont des entiers strictement positifs ?
-
Oui, désolée du délai de réponse.
-
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... -
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. -
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 fauxJustification : 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é. -
Bien vu !
-
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 -
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. -
@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. -
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}$... -
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. -
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$. -
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é. -
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$ -
Rosab:
Le problème n'est pas celui-là. Le problème est que je suppose implicitement que les $x_i$ sont distincts. -
Une piste ?
Somme des termes successifs de la suite de Fibonacci
http://jm.davalan.org/divers/fibonacci/f03.html
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 https://goo.gl/SHAXyT
(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 https://goo.gl/Uhkh4S
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 https://goo.gl/2irAx2
n’a pas cette propriété
Reste à démontrer que cette propriété est toujours valable -
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. -
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."
https://blogdemaths.wordpress.com/2012/06/03/devenez-le-maitre-dune-variante-du-jeu-de-nim/
paragraphe 6 -
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}$.. -
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. -
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. -
Un rappel : http://www.les-mathematiques.net/phorum/read.php?5,1574872,1574992#msg-1574992
Même pas besoin de tri -
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 -
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 -
@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}]
https://goo.gl/pKrrnz
Product[n, {n, 1, 60}] +(-5+10)+(-40+80)+(-60+15) = Product[n, {n, 1, 60}]
https://goo.gl/v1UmAA
Merci beaucoup -
Dans la même veine : Sums of Consecutive Integers
https://arxiv.org/pdf/math/0701149.pdf -
Intéressant !
merci. -
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 -
-
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 ? -
Champ-Pot-Lion a écrit: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 ! -
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} https://goo.gl/YHs8ZQ 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 } https://goo.gl/96sf4w 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) -
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). -
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.. -
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$. -
Ah, ok je vois ta rigueur.
Merci. -
Bonsoir,rosab a écrit: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? -
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 3
+2 Invités