Génération d'une suite d'entiers

[Merlin95]

**
Bonjour.

J'aimerais générer les élèments de la suite , des nombres entiers qui peuvent s'écrire par récurrence de manière unique (*) comme somme de deux nombres parmi les plus petits , mais que s'ils n'ont pas déjà été utilisés un nombre maximum (forcément ) fixé de fois.

(*) de manière unique : ce qui veut dire qu'on ignore *définitivement* un nombre pouvant s'écrire comme sommes de deux entiers de plusieurs manières possibles, mais je passe outre ce cas en « admettant jusqu'à preuve du contraire », avec un possible contre-exemple détecté lors de l'utilisation du programme.

C'est pourquoi aussi, cet aspect qui rendrait inutilement plus lourde, la présentation mathématique qui suit, est ignoré pour l'instant - en attendant un contre-exemple, et tout en s'assurant que le programme détecte bien ces « cas limites » éventuels.
----
Soit donc un entier fixé, et une suite de suites d'entiers à valeurs dans .

représente le nombre d'occurrences () de dans les compositions des nombres compris entre et .

On définit aussi et ainsi :
si ,
sinon.

si ,
sinon.

et alors ainsi par récurrence les suites et () :


on peut donc toujours commencer à utiliser le nombre , « fois », par exemple, si , on génère : puis , puis puis

Par exemple, si , on génère : puis , puis puis

mais si , on génère , puis , puis puis

Et donc

Et :
- si ,


- si ,


----
Si vous avez réussi à décrypter (pas évident de voir comment j'ai construit pour arriver à ce que j'ai dit au début), comme je n'ai pas d'ordinateur pour programmer, j'aimerais avoir « en ligne sur le net », par exemple pour une fonction (au sens informatique) qui me retourne les premiers termes de cette suite.

Dans le but entre autres, par exemple, de tracer l'évolution de .

[Ben314]

Salut,
C'est pas franchement clair ton truc :

J'aimerais générer les élèments de la suite , des nombres entiers qui peuvent s'écrire par récurrence comme somme de deux nombres parmi les plus petits . . .

Je vois pas comment ta phrase "parmi les plus petits" peut définir (sans ambiguïté) qui va être l'élément suivant de la suite.
Sur ton exemple avec m=3, si j'ai bien compris, au départ on a un 1 qu'on a le droit d'utiliser 3 fois.
- On forme donc 2=1+1 qu'on a le droit d'utiliser 3 fois et il reste une utilisation possible pour le 1.
- On forme donc 3=2+1 qu'on a le droit d'utiliser 3 fois : il reste deux utilisation du 2 et aucune du 1.
Et là, tu dit qu'ensuite on forme 5=2+3 : O.K. concernant le fait qu'on a le droit de le faire, mais pourquoi ne forme t-on pas 4=2+2 qui est <5 et qu'on a aussi le droit de faire vu qu'il reste deux utilisation du 2 ?

Est-ce que ça signifie que ton "parmi les plus petits" veut en fait dire qu'on prend systématiquement les deux entiers les plus petits possibles pour lesquels il reste des utilisations (et deux fois le même si le plus petit avec des utilisations disponibles en a au moins 2) ?
Si oui, ce qui me semble pas clair, c'est ce qu'on va faire si le nombre généré avec cette méthode a déjà été généré précédemment : on le recopie une deuxième fois et on ajoute des "disponibilités" ? On forme une autre somme ? Si oui, laquelle ?

Et bien sûr, tant que la façon dont tu forme ta suite n'est pas définie de façon parfaitement rigoureuse, ben on risque pas de programmer quoi que ce soit . . .

[Merlin95]

Non bien +1, c'est ça tu as vu juste, donc ça veut dire que j'ai été clair, car c'est bien une bêtise d'inattention de ma part dans le calcul qui construit la suite, c'est bien évidemment , le suivant, car on prend le plus petit justement (puisque l'autre donnait ).

D'ailleurs dans le min de la formule de mon premier message, on voit bien qu'on autorise bien d'additionner un nombre avec lui-même.
Je corrige dans mon message.

[Merlin95]

ce qui me semble pas clair, c'est ce qu'on va faire si le nombre généré avec cette méthode a déjà été généré précédemment

Non çà, ça n'est pas possible, la somme de deux nombres ne peut être générée qu'une seule fois par construction puisqu'on épuise les nombres par le bas (mais peut-être l'algorithme peut s'arrêter aussi ? je ne pense pas, mais je ne suis pas sûr justement, entre autres choses).
Et s'il existe plusieurs possibilités donnant un minimum, on ne retient pas la somme, car la décomposition d'un nombre , doit être unique (comme déjà precisé dans mon premier message).

[Ben314]

Avec le coup de l'erreur sur l'exemple m=3, ça devenait clair.

Et s'il existe plusieurs possibilités donnant un minimum, on ne retient pas la somme, car la décomposition d'un nombre , doit être unique (comme déjà precisé dans mon premier message).

Sauf qu'avec ça, c'est de nouveau pas bien clair vu qu'il me semble possible qu'à un moment donné, on n'ait pas le droit de générer la somme S du fait qu'il y a plusieurs façon de la faire mais que, plus tard, à force d'épuiser les utilisations des nombres, il risque de n'y avoir plus qu'une seule façon d'obtenir cette somme S.
Dans ce cas on fait quoi : On prend cette somme S (qui est plus petite que la précédente qu'on a pris) ou on laisse tomber ?

[Merlin95]

Oui je vois ton cas, la suite ne serait en plus potentiellement pas monotone, ce que je n'avais effectivement pas vu, en plus de pouvoir potentiellement engendrer l'arrêt du programme.
Mais ce dernier cas peut se produire dans d'autres situations aussi.

C'est pourquoi dés le premier message, j'ai bien précisé, que l'on suppose que ce cas « n'arrive pas » jusqu'à preuve du contraire, facile à vérifier rapidement dans un programme avec la routine pour détecter et nous avertir, si ce cas « arrive », lors de la construction de la suite pendant de l'exécution du programme.

Et si cela se produit, je propose la même chose, c'est-à-dire, ne rien faire de plus, donc juste ne pas retenir le nombre, quitte à voir les conséquences, et réfléchir ensuite.

De même, avec la routine qui détecte et nous avertit, lorsqu'une suite est « finie » (c'est-à-dire, tout simplement, quand le programme n'a pas pu genérer un nouveau nombre en fait).

[Ben314]

Visiblement, pour m=3, la nouvelle somme est systématiquement la somme des deux plus petits qui ont encore des disponibilités (éventuellement deux fois le même) et on risque même de pouvoir calculer le n-ième terme de façon générale : ça a l'air d'être lié à la base 2 vu que le passage d'un terme au suivant semble se faire systématiquement en ajoutant une puissance de 2.

Par contre, pour m=4 (ou plus), il y a très vite des problèmes de duplication vu qu'une fois formé 2=1+1 et 3=2+1 il y a deux façons d'écrire le 4 : 2+2 ou 3+1.

[Merlin95]

Donc comme dit avant, on vire définitivement 4, à priori.

[Merlin95]

Ou alors les conserver, la suite ne sera plus strictement croissante, et le problème en effet, est de devoir choisir si on ajoute un terme ou autant de termes que de décompositions trouvées. C'est pour ça, à priori, le plus simple est de virer définitivement le nombre.

Mais ça fait partie du problème, ce sont ces choses là que j'aimerais justement savoir et tester, autant que possible, avec le programme.

[Merlin95]

Tu avais raison, il y a bien un schmilblick.