Un énigme ? Trigons (somme des entiers de 1 à n) et cycles

[invite1da1ea6d]

@Amanuensis: Là j'avoue que tu m'as un peu perdu avec les histoires de résidus quadratiques, cela dépasse très largement mes maigres connaissances mathématiques

Une autre question : pourquoi T'(n) est-il parfois négatif ?
Par exemple pour n=125456 :
T(n) = 7869666696
T'(n) = MOD(T(n),999) = -884

?
-----

[Médiat]

Moi je trouve MOD(T(n),999) = 240.

Ceci étant dit les calculs modulo 999 (ou tout autre) repose sur des "classes d'équivalences", et on peut choisir n'importe quel élément d'une classe comme représentant. Il est d'usage de choisir les nombres entre 0 et 998, si vous préférez les nombres entre 1 et 999, c'est un choix licite (puisque 0 et 999 sont dans la même classe), de la même façon, je vous disais avoir trouvé 240, j'aurais pu aussi dire avoir trouvé -759, qui est dans la même classe que 240.

[invite179e6258]

Les points fixes de l'application sont 0,1,297 et 703. Si on l'itère suffisamment, on constate que 297 est atteint pour 4 valeurs de départ (297,405,593,701) mais 703 est atteint pour 315 valeurs de départ. Comme quoi la symétrie par rapport à 500 n'est pas parfaite.

[Médiat]

Je parlais de symétrie par rapport à 499 (d'ailleurs : 297 + 701 = 405 + 593 = 998 = 2*499), tous les points de départ donnant 703 (ou quoi que ce soit d'autre) sont toujours appariables 2 par 2 symétriquement par rapport à 499.

[invite1da1ea6d]

Je trouve aussi 240 manuellement, mais je viens de comprendre d'où vient le problème, il s'agit d'une limitation de la fonction utilisée dans mon script en PHP pour le modulo (%), qui réagit mal aux grands nombres, pour lesquels il vaut mieux utiliser fmod(a,n).

Par contre, pour mon éclairage personnel, pourriez-vous juste me préciser cette notion de classe d'équivalence : pourquoi -759 appartient-il à la même classe que 240 ?
Ainsi que cette intéressante notion de symétrie par rapport à 499 ?

[invite179e6258]

Je parlais de symétrie par rapport à 499 (d'ailleurs : 297 + 701 = 405 + 593 = 998 = 2*499), tous les points de départ donnant 703 (ou quoi que ce soit d'autre) sont toujours appariables 2 par 2 symétriquement par rapport à 499.

ah tiens c'est marrant moi je vois ça comme une symétrie par rapport à 500 : 500 -203 = 297 et 500 + 203 = 703 mais bon c'est une question de convention. C'est clair que la fonction est symétrique au sens usuel par rapport à 499 : f(499-x)=f(499+x).

[Médiat]

Par contre, pour mon éclairage personnel, pourriez-vous juste me préciser cette notion de classe d'équivalence : pourquoi -759 appartient-il à la même classe que 240 ?

Parce que -759 + 999 = 240 (deux nombres sont équivalents modulo 999 si leur différence est un multiple de 999 ; on peut remplacer 999 par n'importe quel entier).

Ainsi que cette intéressante notion de symétrie par rapport à 499 ?

Il suffit de savoir que lorsque l'on fait des calculs modulo 999, on peut ajouter ou soustraire 999 sans rien changer (puisque 999 et 0 sont dans la même classe).

[Médiat]

ah tiens c'est marrant moi je vois ça comme une symétrie par rapport à 500 : 500 -203 = 297 et 500 + 203 = 703

T(297) = 297
T(703) = 703
Ce n'est pas franchement symétrique.
Maintenant il serait peut-être intéressant de faire correspondre à chaque nombre (entre 0 et 998 par exemple), un couple défini par :

= longueur de la chaine avant de rentrer dans un cycle
= longueur du cycle.

Par exemple et

mais et , donc pas de symétrie non plus, mais il y a peut-être quelque chose à chercher ...

[invite1da1ea6d]

Maintenant il serait peut-être intéressant de faire correspondre à chaque nombre (entre 0 et 998 par exemple), un couple défini par :

= longueur de la chaine avant de rentrer dans un cycle
= longueur du cycle.

Par exemple et

mais et , donc pas de symétrie non plus, mais il y a peut-être quelque chose à chercher ...

Je songeais à cela justement, en observant les différences à ce niveau-là.

Par exemple, , ce qui est une sorte de maximum constaté jusque là (empiriquement).

[Médiat]

Pour moi, , mais qui est bien un maximum.

[invite1da1ea6d]

Pour moi, , mais qui est bien un maximum.

En effet, au temps pour moi, j'avais lu un de trop pour l'alpha de 596.
Mais comment savoir théoriquement que le maximum est bien atteint par 12 ?

[Médiat]

Il n'y en a que 500 à regarder .

Notez cependant que pour un nombre > 1000, il faut ajouter 1 à
Le maximum théorique est donc (11, 6) mais je ne sais pas s'il est atteint

[invite1da1ea6d]

Notez cependant que pour un nombre > 1000, il faut ajouter 1 à

Pourquoi ?
Jusqu'à présent on pouvait calculer un T(n) avec n > 1000 sans calculer T'(n) avant, non ?

[Médiat]

Parce qu'il faut appliquer une première fois T' avant d'avoir un résultat entre 1 et 999.

[invite1da1ea6d]

Parce qu'il faut appliquer une première fois T' avant d'avoir un résultat entre 1 et 999.

Ok, mais ce n'est pas ce que fait le calculateur sur la page, et ce n'est pas ce qu'on a fait jusqu'à présent me semble-t-il.

Par ex., plus haut :

pour n=125456 :
T(n) = 7869666696
T'(n) = MOD(T(n),999)

Vous trouviez T'(n) = 240 parce que T(n) =7869666696 => 7+869+666+696 = 2238 => 2+238 = 240.

Et pas T'(n) = 125 + 456 = 581.

Ou alors ai-je fumé ?

[azizovsky]

Salut , j'ai une vision un peu différente du problème (possible je vais dire n'importe quoi ) , soit on'a k registres ( http://fr.wikipedia.org/wiki/Registr..._d%C3%A9calage) dicémale non binaire de 3 'Bascule' ,chaque bascule affiche un chiffre de 1 à 9 ,le résultat de l'opération T(n) , et la somme de k rgistres de 3 bascule .

ps :Le bit 'décimale' qui était mémorisé aprés la troisième,6 ème ,9...., bascule est réinséré sous forme d'addition d'où à la louche .

[Amanuensis]

Pour la symétrie...

Les racines de 1 sont 1, 998, 593 et 406. Il n'y en a que quatre, car 999=27.37, et modulo 37, 2 racines de 1, et modulo 27 aussi

593 = 2.297 -1, et T(297)=297

Plus généralement, si (2n-1)²=1, on a 4n²-4n=0, et donc n²=n (4 est inversible), et (n²+n)/2=n

Les quatre racines de 1 donnent les quatre points fixes. 2.1-1 = 1, 2.0-1= -1, 2.297-1=593 et 2.703-1 = 406

Si (2a-1)²=1, alors 2T(-(2a-1)n - a) = (2a-1)²n²+2a(2a-1)n+a²-(2a-1)n-a = n²+n

On a donc les symétries suivantes

pour a=0, T(n)=n

pour a =1, T(-n-1)=T(n) [T(998-n)=T(n), déjà indiqué]

pour a=294, T(406n-297)=T(n)

et pour a=703, T(593n-703)=T(n)

[Amanuensis]

pour a=0, T(n)=n

Faute: lire T(n)=T(n)

[Médiat]

Ok, mais ce n'est pas ce que fait le calculateur sur la page, et ce n'est pas ce qu'on a fait jusqu'à présent me semble-t-il.

Par ex., plus haut :


Vous trouviez T'(n) = 240 parce que T(n) =7869666696 => 7+869+666+696 = 2238 => 2+238 = 240.

Et pas T'(n) = 125 + 456 = 581.

Ou alors ai-je fumé ?

Dans un premier temps il y a une évidence : T'(n) est compris entre 1 et 999.
Deuxième temps : les nombres entre 1 et 499 couvrent toutes les suites des images itérées (puisque T'(n) = T'(998-n)
Troisième temps : le couple le plus grand est (10, 6) pour les nombres entre 1 et 499
On en déduit que le maximum théorique est (11, 6) puisqu'à partir de n > 1000, il faut appliquer une première fois T' pour avoir un nombre entre 1 et 999
En fait (démonstration simple), c'est à dire que si m > 1000, T'(m) est non seulement compris entre 1 et 1000, mais c'est déjà l'image par T' d'un entier entre 1 et 1000
Le plus grand couple réellement atteint est donc (10, 6)

[gg0]

Dans un premier temps il y a une évidence : T'(n) est compris entre 1 et 999.
Deuxième temps : les nombres entre 1 et 499 couvrent toutes les suites des images itérées (puisque T'(n) = T'(998-n)
Troisième temps : le couple le plus grand est (10, 6) pour les nombres entre 1 et 499
On en déduit que le maximum théorique est (11, 6) puisqu'à partir de n > 1000, il faut appliquer une première fois T' pour avoir un nombre entre 1 et 999
En fait (démonstration simple), c'est à dire que si m > 1000, T'(m) est non seulement compris entre 1 et 1000, mais c'est déjà l'image par T' d'un entier entre 1 et 1000
Le plus grand couple réellement atteint est donc (10, 6)

La partie
a été cachée par ce bandeau :Only futura-sciences.com may use mimetex on this server. Please read www.forkosh.com/mimetex.html and install mimetex.cgi on your own server.Thank you, John Forkosh

C'est assez déplaisant !

[Médiat]

Est-ce mieux ?

[invite1da1ea6d]

C'est bon chez moi.

Les racines de 1 sont 1, 998, 593 et 406.

J'avoue ne pas avoir compris, pardon ! Qu'est-ce-que tu appelles racines de 1 ?

[gg0]

C'est bon aussi chez moi.

Merci !

[Amanuensis]

J'avoue ne pas avoir compris, pardon ! Qu'est-ce-que tu appelles racines de 1 ?

Les nombres tels que n²=1 modulo 999

[invite1da1ea6d]

Les nombres tels que n²=1 modulo 999

Ok. Pas tout saisi à ta démonstration sur la symétrie (notamment : "Il n'y en a que quatre, car 999=27.37, et modulo 37, 2 racines de 1, et modulo 27 aussi
593 = 2.297 -1, et T(297)=297"), mais je vois l'idée générale !

Au final, le fait qu'il y ait 8 cycles seulement pour tout (T'(n) = MOD (n(n+1) / 2, 999)) itéré un certain nombre de fois fait donc partie du mode opératoire, mais est-ce démontrable ?

Merci en tout cas à tous pour vos contributions.


PS : j'ai à nouveau le message rouge mimetex.

[Médiat]

Au final, le fait qu'il y ait 8 cycles seulement pour tout itéré un certain nombre de fois fait donc partie du mode opératoire, mais est-ce démontrable ?

Oui puisque l'on peut démontrer que tous les cas se ramènent aux cas compris entre 1 et 999 (et on peut améliorer), et que ces cas se limitent à 8 cycles ; cqfd.

A partir du moment où on peut démontrer que l'on peut se ramener à un nombre fini de cas, il suffit d'étudier ces cas pour conclure (s'ils ne sont pas trop nombreux, ou si on peut programmer les calculs, cf. le théorème des 4 couleurs).

[Amanuensis]

Ok. Pas tout saisi à ta démonstration sur la symétrie (notamment : "[I]Il n'y en a que quatre, car 999=27.37, et modulo 37, 2 racines de 1, et modulo 27 aussi

Application du théorème des restes chinois. Il y a toute un "outillage" pour faire de l'arithmétique modulo un entier.

Au final, le fait qu'il y ait 8 cycles seulement pour tout (T'(n) = MOD (n(n+1) / 2, 999)) itéré un certain nombre de fois fait donc partie du mode opératoire, mais est-ce démontrable ?

Si on parle d'un seul cas, ici 999, cela se démontre par l'analyse exhaustive, le nombre de possibilités étant fini (comme indiqué dans le message précédent).

Pour parler de quelque chose "à démontrer" selon le sens commun, faudrait en faire une loi plus générale, portant par exemple sur le nombre de cycles selon la valeur du modulo.

Par exemple peut-on dire quelque chose de particulier (et le démontrer) pour le nombre de cycles modulo un nombre premier?

[Médiat]

J'avoue ne pas voir de moyen de calculer simplement le nombre de cycles en fonction du modulo avec lequel on travaille, mais je suis tombé sur un résultat qui m'a surpris : 359 (qui est premier) ne possède que les deux cycles minimaux de période 1 (0 et 1), alors que 13 en a 3.

[invite1da1ea6d]

359 (qui est premier) ne possède que les deux cycles minimaux de période 1 (0 et 1), alors que 13 en a 3.

C'est-à-dire ?

[Médiat]

Si vous remplacez 999 par 359, tous les nombres finissent par atterrir sur 0 ou sur 1.