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]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
Le deuxième distinct du premier, le troisième non dans l'ensemble des deux premiers, et ainsi de suite...
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.
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é.
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
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.
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.
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}$...
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.
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$.
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é.
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$
Non tu as perdu la notion de permutation.
Le problème n'est pas celui-là. Le problème est que je suppose implicitement que les $x_i$ sont distincts.
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
et de vérifier si on reçoit bien primorial(a_n) ... calculateur connaissant les premiers oblige.
"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
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}$..
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.
Une solution pourrait être de ranger les entiers dans l'ordre croissant (sens large)
puis d'examiner ces sommes.
Même pas besoin de tri
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
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
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
https://arxiv.org/pdf/math/0701149.pdf
merci.
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
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
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 ?
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 !
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)
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).
@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..
Ç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$.
Merci.
@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?
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.