La question (graphique) d'un dimanche après-midi pluvieux

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

La question (graphique) d'un dimanche après-midi pluvieux

Message par C.Ret »

Bonjour à toutes et à tous.

Je me suis abrité juste à tant de la pluie chaude et brumeuse de cet après-midi d'août pour découvrir une suite qui sort de l'ordinaire.
Dans une période où tout semble se dégrader, diverger , partir en vrille ou s'enfoncer dans le chaos, j'ai découvert une chose bien étrange et en quelque sorte antagoniste à ce qui semble être la tendance actuelle.


Si vous le voulez bien, considérons la suite suivante définie de la façon suivante :
Banshee's Suite.gif
Banshee's Suite.gif (2.72 Kio) Vu 8599 fois
Il s'agit d'une définition par récurrence où GCD(a,b) n'est rien d'autre que le Plus Grand Diviseur Commun (PGDC). J'ai laissé la définition avec le formalisme anglais puisque je l'ai trouvé dans un document dans cette langue.

Le terme suivant est calculé différemment selon que le terme précèdent possède ou non un diviseur commun avec le rang n.
Si u(n-1) et n sont premiers entre-eux, le terme suivant est u(n)=u(n-1)+n+1.
Sinon, le terme suivant est obtenu par division; on simplifie en quelque sorte par le plus grand diviseur commun et u(n)=u(n-1)/gcd(u(n-1),n).

Programmons notre assistant numérique préféré, ou celui qui nous semblera le plus adapté, afin d'en tracer la courbe. Certains préfèrerons peut-être tracer cette courbe à la main sur du papier calque ou une feuille de papier millimétrée. Ce ne doit pas être impossible, mais juste un peu plus long. Quoi que je n'en soit pas absolument sûr, programmer convenablement une suite définie par récurrence pose parfois de ennuis sur certains systèmes…

Pour tracer ce graphe, il suffit de calculer les éléments de cette suite, dont je donne ci-dessous les treize premières valeurs:

Code : Tout sélectionner

 n  │   0 │   1 │   2 │   3 │   4 │   5 │   6 │   7 │   8 │   9 │  10 │ 11 │  12 │ 13
────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────┼─────┼─────
u(n)│   1 │   1 │   4 │   8 │   2 │   8 │   4 │  12 │   3 │   1 │  12 │ 24 │   2 │ 16
u(0)=1 et u(1)=1 par définition.
u(2)=1+2+1=4 car u(1)=1 et n=2 sont premiers entre-eux (pas de diviseurs commun).
u(3)=4+3+1=8 car u(2)=4 et n=3 n'ont pas de diviseurs commun.
U(4)=8/4=2 car 4 est diviseur de u(3)=8 et n=4
etc.

En procédant ainsi, j'ai pu tracer la courbe suivante qui représente les valeurs u(n) pour n allant de 0 à 500 :
C128D - Color HiRes Graph u_n (1 - 500).gif
C128D - Color HiRes Graph u_n (1 - 500).gif (11.12 Kio) Vu 8602 fois
Cette suite semble aléatoire et les points forment un beau chaos, les valeurs se dispersant de plus en plus au fur et à mesure du tracé…
Mais…
(Car il y a un MAIS, qui d'ailleurs nous amène à la question graphique de ce dimanche)

Que ce passe-t-il si l'on cherche à tracer cette courbe pour n allant jusqu'à 1000, 2000, 4000 ou même plus ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
pir2
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4642
Enregistré le : 31 oct. 2006 15:08
Localisation : 67310 Westhoffen
Contact :

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par pir2 »

Impressionnant :)

Réponse en MP
Image
Image
Avatar du membre
jvernet
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7958
Enregistré le : 24 mai 2002 09:57
Localisation : France 69
Contact :

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par jvernet »

C'est étrange,ou est ce un artefact informatique ??

Meme sous Libreoffice.
"l'ordinateur et l'homme sont les deux opposés les plus intégraux qui existent. L'homme est lent, peu rigoureux et très intuitif. L'ordinateur est super rapide, très rigoureux et complètement con."
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par Ben »

J'ai essayé sur le C-128. Avoir le tableau de valeur n'est pas vraiment un problème. Mais pour la représentation graphique, c'est autre chose. Du coup, je suis passé sur Calc. Il semblerait que des lignes droites partant de l'origine se dessinent. :-)
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par C.Ret »

Attention, si sur CALC tu as obtenu le graphique suivant, c'est qu'il y a une erreur sur les indices de la suite !
C128 - Bad suite indice x=0-1000  y=0-2600.gif
C128 - Bad suite indice x=0-1000 y=0-2600.gif (6.4 Kio) Vu 8494 fois
Ben a écrit : 12 août 2019 16:20 J'ai essayé sur le C-128. Avoir le tableau de valeur n'est pas vraiment un problème. Mais pour la représentation graphique, c'est autre chose.
En fait, il n'y a pas besoin de calculer le tableau des valeurs. Et contrairement aux C64, faire le graphique sur C128 est très facile :

Code : Tout sélectionner

100 xa=0 : xb=1000 : sx=320/(xb-xa)                        : rem  limites et échelle de l'axe des x 
110 ya=1 : yb=2800 : sy=200/(yb-ya)                        : rem  limites et échelle de l'axe des y
120 y=1  : graphic 1,1                                     : rem  Initialise la suite et le mode graphique HR
130 draw 1,0,199 : draw 1,sx,199                           : rem  Dessine les points (0,u(1)) et (1,u(1))
140 for x=2 to xb                                          : rem  Parcourt les termes de 2 à xb 
150 :  a=x:b=y:do while b : g=b:b=a-b*int(a/b):a=g : loop  : rem       Calcul du GCD(u(n-1),n)   
160 :  if g=1 then y=y+x+1 : else y=y/g                    : rem       Calcul du terme suivant
170 :  draw 1,x*sx,199-y*sy                                : rem       Dessine le point (i,u(i))
180 next x                                                 : rem  Terme suivant 
jvernet a écrit : 11 août 2019 20:17 C'est étrange,ou est ce un artefact informatique ??

Meme sous Libreoffice.
Non , non ce n'est pas un bogue, ni un bugg ou un artéfact lié au calcul électronique. C'est vraiment comme cela :)

(même avec Microsoft Ofiice Excel - c'est dire...)
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
jvernet
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7958
Enregistré le : 24 mai 2002 09:57
Localisation : France 69
Contact :

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par jvernet »

C.Ret a écrit : 14 août 2019 20:46

Non , non ce n'est pas un bogue, ni un bugg ou un artéfact lié au calcul électronique. C'est vraiment comme cela :)

(même avec Microsoft Ofiice Excel - c'est dire...)
J'ai mis mon fils qui sort de MP dessus. Il me parle de sous suites, après un indice n particulier, mais a pas encore trouvé le truc ;)
"l'ordinateur et l'homme sont les deux opposés les plus intégraux qui existent. L'homme est lent, peu rigoureux et très intuitif. L'ordinateur est super rapide, très rigoureux et complètement con."
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par C.Ret »

Comme aujourd'hui c'est un peu comme un dimanche, je donne un indice.

Il ne s'agit pas de sous-suite, mais bel est bien d'un problème de parité. La question du jour férié après-midi est donc :

Que ce passe-t-il si la suite prend la valeur u(n) = 1 avec un indice n pair ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
pir2
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4642
Enregistré le : 31 oct. 2006 15:08
Localisation : 67310 Westhoffen
Contact :

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par pir2 »

On arrive "juste" un peu plus tôt au comportement d'après 638 (premier indice pair pour lequel u(n)=1)
Image
Image
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par Ben »

C.Ret a écrit : 14 août 2019 20:46 Attention, si sur CALC tu as obtenu le graphique suivant, c'est qu'il y a une erreur sur les indices de la suite !
J'avais un petit mélange des deux graphes, une erreur de copier/coller.

En fait, le premier u(n)=1 avec n pair "déclenche" cette parité
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: La question (graphique) d'un dimanche après-midi pluvieux

Message par C.Ret »

C'est bien cela.

Le premier élément u(n) de la suite qui vaut 1 avec n pair change complètement le comportement du graphe.

Telle qu'elles sont définies, les valeurs sont assez difficile à prédire. Le début du graphe es valeurs successives se dispersent donnant une impression de distribution aléatoire au graphe. Arrivé à un point précis, le graphe est d'un seul coup bien structuré.


Voyons ce qui se passe au point d'indice pair 2m où la valeur de la suite est 1 :
m est donc un entier, qui d'après le graphe des premières valeurs est au moins plus grand que 200.

Code : Tout sélectionner

 n  │  2m │ 2m+1 │ 2m+2 │ 2m+3 │ 2m+4 │ 2m+5 │ 2m+6 │ 2m+7 │ 2m+8 │ 2m+9 │ 2m+10│ 2m+11│ 2m+12│ 2m+13 ...
────┼─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼────── ─ ─
u(n)│   1 │      │      │      │      │      │      │      │      │      │      │      │      │      
Comme PGDC( 1 , 2m+1) = 1, la valeur de la suite au point 2m+1 sera u(2m+1) = u(2m) + (2m+1) + 1 = 1 + 2m+1 + 1 = 2m+3 :

Code : Tout sélectionner

 n  │  2m │ 2m+1 │ 2m+2 │ 2m+3 │ 2m+4 │ 2m+5 │ 2m+6 │ 2m+7 │ 2m+8 │ 2m+9 │ 2m+10│ 2m+11│ 2m+12│ 2m+13 ...
────┼─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼────── ─ ─
u(n)│   1 │ 2m+3 │      │      │      │      │      │      │      │      │      │      │      │      
Il n'y a pas de diviseur communs entre (2m+3) et (2m+2), ce qui fait que PGDC(2m+3,2m+2)=1 et la valeur suivante sera donc u(2m+2)= u(2m+1) + (2m+2) +1 = 2m+3 + 2m+2 +1 = 4m+6

Code : Tout sélectionner

 n  │  2m │ 2m+1 │ 2m+2 │ 2m+3 │ 2m+4 │ 2m+5 │ 2m+6 │ 2m+7 │ 2m+8 │ 2m+9 │ 2m+10│ 2m+11│ 2m+12│ 2m+13 ...
────┼─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼────── ─ ─
u(n)│   1 │ 2m+3 │ 4m+6 │      │      │      │      │      │      │      │      │      │      │      
Par contre, on a 4m+6 = 2*(2m+3), de ce fait, le PGDC( 2m+3 , 4m+6) = 2m+3.
La valeur suivante de la suite sera donc u(2m+3) = u(2m+2) / (2m+3) = (4m+6)/(2m+3) = 2

Code : Tout sélectionner

 n  │  2m │ 2m+1 │ 2m+2 │ 2m+3 │ 2m+4 │ 2m+5 │ 2m+6 │ 2m+7 │ 2m+8 │ 2m+9 │ 2m+10│ 2m+11│ 2m+12│ 2m+13 ...
────┼─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼────── ─ ─
u(n)│   1 │ 2m+3 │ 4m+6 │    2 │      │      │      │      │      │      │      │      │      │      
Le terme suivant est celui d'indice 2m+4, il nous faut donc calculer le PGDC( u(2m+3) , 2m+4 ) = PGDC( 2 , 2m+4 ) = 2 car 2m+4 est pair.
Le terme d'indice 2m+4 est donc calculé à partir du quotient : u(2m+4) = u(2m+3) / 2 = 2 / 2 = 1.

Code : Tout sélectionner

 n  │  2m │ 2m+1 │ 2m+2 │ 2m+3 │ 2m+4 │ 2m+5 │ 2m+6 │ 2m+7 │ 2m+8 │ 2m+9 │ 2m+10│ 2m+11│ 2m+12│ 2m+13 ...
────┼─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼────── ─ ─
u(n)│   1 │ 2m+3 │ 4m+6 │    2 │    1 │      │      │      │      │      │      │      │      │      
L'on se retrouve alors à nouveau avec une valeur de la suite égale à 1 au niveau d'un indice pair. Les choses se répètent donc à nouveau et à l'infini :
la suite devient comme périodique de période 4.

Code : Tout sélectionner

 n  │  2m │ 2m+1 │ 2m+2 │ 2m+3 │ 2m+4 │ 2m+5 │ 2m+6 │ 2m+7 │ 2m+8 │ 2m+9 │ 2m+10│ 2m+11│ 2m+12│ 2m+13 ...
────┼─────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼────── ─ ─
u(n)│   1 │ 2m+3 │ 4m+6 │    2 │    1 │ 2m+7 │ 4m+14│    2 │    1 │ 2m+11│ 4m+22│    2 │    1 │ 2m+15 ...

Ce qui explique l'aspect du graphe si l'on poursuit son tracé au-delà de 638.
C128D - Color HiRes Graph u_n (1 - 1k2).gif
C128D - Color HiRes Graph u_n (1 - 1k2).gif (14.83 Kio) Vu 8313 fois


On voit trois droites, en réalité il s'agit de la répétition toutes les 4 valeurs :
  • - des valeurs 1 ,
  • - des valeurs 2m+3 , 2m+7, 2m+11, ... formant l'alignement des points selon la droite de pente 1 (on augmente de 4 unité tous les 4 points),
  • - des valeurs 4m+6 , 4m+14, 4m+22, ... aligné selon la droite de pente 2 (on augmente de 8 tous les 4 points),
  • - des valeurs 2 (qui sur le graphe , à cause de l'échelle semble former une droite horizontale avec les points de valeur 1.
Voilà la pourquoi et le comment, mais ne me demandé pas pourquoi cela ne se produit pas avant n = 638, c'est comme cela, un point c'est tout :)
Il n'y a pas de valeur 1 à un indice pair avant. Na !




Cette suite est présente dans l'ON-LINE ENCYCLOPEDIA of INTEGER SEQUENCES : OEIS A133058

Plus d'informations et d'explications par l'inventeur de cette suite Neils J. A. Sloane en personne (et donc en anglais) sur YouTube :Amazing Graphs (Part.1) - Numberphile
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Répondre

Retourner vers « Tous les Pockets »