Loading [MathJax]/jax/output/CommonHTML/jax.js
Back
Close

Recueil d'exercices pour apprendre Python au lycée

M_C
158K views

La suite de Van Eck

Cette page est inspirée de cette vidéo.
Nous allons nous intéresser à la suite de Van Eck qui est une suite créée très recemment (en 2010) et étudiée (pour le plaisir) depuis. Ce qui est intéressant avec cette suite c'est que, comme elle est très récente, on la connait assez mal et très peu de choses ont été découvertes dessus. On a, au mieux, quelques conjectures en observant les termes de la suite (Wikipedia).

Le but de cette page est de calculer les termes de la suite puis de les afficher pour faire quelques observations et conjectures. Libre à vous ensuite d'approfondir et pourquoi pas découvrir des choses que les chercheurs n'auraient pas encore vues...

Définition de la suite

La suite (Vn) commence par V0=0. (On pourrait commencer par un autre nombre mais c'est classiquement le choix qui est fait).

Ensuite, supposons connus les premiers termes jusqu'à Vn. Deux possibilités :

  • Si c'est la première fois qu'apparait le nombre Vn jusqu'à présent, alors Vn+1=0.
  • Sinon, on compte de combien il faut reculer pour retomber sur la valeur Vn dans les termes précédents de la suite.

Regardons la construction des premiers termes :

  1. On commence par V0=0. Comme 0 apparait pour la première fois, le nombre suivant V1=0
  2. V1=0 et ce n'est pas la première fois qu'il apparait donc on compte de combien il faut reculer pour retomber sur 0.
    Ici comme V0=0, on recule de 1 donc V2=1
  3. V2=1 et 1 apparait pour la première fois donc V3=0.
  4. V3=0 et 0 est déjà dans les premiers termes et qu'il faut reculer de 2 pour retomber dessus, V4=2
  5. V5=0 et ainsi de suite

On obtient ainsi comme premiers termes :
0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3, 1, 42, 0, 5, 15, 20, 0, 4, 32, 0, 3, 11, 18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3, 6, 3, 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0, 5, 37, 0, 3, 8, 8, 1...

Essayez de calculer seul les termes V6 jusqu'à V10 puis vérifiez avec la liste précédente pour être sûr d'avoir bien compris comment se construit cette suite.


Calcul des termes de la suite (version naive)

Difficulté : Moyenne
Prérequis : Les listes

En utilisant la définition précédente, créer une fonction VanEck(n) qui donne la liste des valeurs de la suite de Van Eck (Vn) de V0 jusqu'à Vn.

Exemple : VanEck(4) doit renvoyer [0, 0, 1, 0, 2].

Calcul des termes de la suite de Van Eck
def VanEck(n):
# Ne pas toucher ce qui précède
# Les valeurs pour les variables en entrée seront automatiquement données
# Ecrire ci-dessous en n'oubliant pas d'indenter et d'utiliser return pour renvoyer un résultat
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Calcul des termes de la suite (version optimisée)

Difficulté : Difficile
Prérequis : Les listes

La façon dont on calcule les termes de la suite en utilisant simplement la définition prend beaucoup de temps dès qu'on augmente un peu la valeur de n (plusieurs minutes pour seulement n=100000). Nous allons voir comment optimiser beaucoup nos calculs.

Pour cela nous allons utiliser deux listes : une première dans laquelle on va mettre nos termes au fur et à mesure (comme pour la version précédente) et une autre dans laquelle, à chaque nouvelle valeur de Vn qu'on calcule, on va mettre l'indice correspondant. Ainsi il suffira de lire dans cette liste la dernière fois qu'on a croisé une valeur au lieu de chercher à chaque fois dans la liste des termes où était cette dernière valeur.

Exemple : Supposons qu'on veuille calculer pour n=5.
On commence par créer nos deux listes :

  • la liste des termes initialisée avec 0 : liste_termes=[0]
  • la liste des indices qu'on crée déjà en entier (comme on calcule pour n=5, on va créer une liste de longueur 6). Pour l'initialiser, il faut mettre une valeur qu'on n'utilisera pas (par exemple -1 ou None) pour signifier qu'on n'a pas encore trouver cette valeur. Ainsi, au début on a donc une variable liste_indices = [-1,-1,-1,-1,-1,-1] (qu'on peut créer facilement en faisant [-1]*6). Pour bien préciser les choses : si on a liste_indices[3]=5, cela signifie que la dernière fois qu'on a obtenu un 3 comme valeur de notre suite, c'est lorsque l'indice était 5.
    Voyons maintenant comment doit fonctionner notre algorithme pour calculer les 6 premiers termes :
  • A l'étape 0 : On regarde le dernier terme de notre liste_termes : C'est 0. On regarde dans notre liste_indices la dernière fois qu'on a croisé 0 : on trouve -1 ce qui signifie jamais. Dans ce cas, d'après la façon dont on doit créer la suite, la valeur suivante de la suite (Vn) est V1=0. On rajoute donc 0 à notre liste_termes et comme du coup la dernière fois qu'on a croisé 0 est à l'indice 0 (on ne considère pas encore le nouveau 0 qu'on a rajouté) on le note dans notre liste_indices. Donc à cette étape on a liste_termes = [0,0] et liste_indices=[0,-1,-1,-1,-1,-1].
  • A l'étape 1 : On recommence : la dernier terme est 0. Dans liste_indices, la dernière fois qu'on a croisé 0 est en 0. Comme on est à l'étape 1 (on considère V1) la distance entre les deux est 1 - 0 = 1. Donc la valeur suivante de la suite est V2=1 qu'on ajoute à liste_termes. On met à jour le fait que le dernier 0 croisé est à l'indice 1 ce qui donne comme état des variables : liste_termes = [0,0,1] et liste_indices=[1,-1,-1,-1,-1,-1].
    Remarque importante : On ne met pas encore le fait qu'on a obtenu un 1 à l'indice 2 dans la liste_indices car cette liste nous permet de garder en mémoire ce qui se passe avant d'avoir obtenu ce 1.
  • A l'étape 2 : On rerecommence : le dernier terme est 1. On a jamais croisé de 1 donc on met un 0...
    On obtient comme variables à la fin de cette étape : liste_termes = [0,0,1,0] et liste_indices=[1,2,-1,-1,-1,-1].
  • On a ensuite : liste_termes = [0,0,1,0,2] et liste_indices=[3,2,-1,-1,-1,-1].
  • Et enfin : liste_termes = [0,0,1,0,2,0] et liste_indices=[3,2,4,-1,-1,-1].

Vérifiez bien que vous avec compris le raisonnement avant de vous lancer dans l'algorithme.

A présent, créez votre nouvelle fonction VanEck(n) en utilisant l'algorithme qui vient d'être décrit.

Calcul des termes de la suite de Van Eck
def VanEck(n):
# Ne pas toucher ce qui précède
# Les valeurs pour les variables en entrée seront automatiquement données
# Ecrire ci-dessous en n'oubliant pas d'indenter et d'utiliser return pour renvoyer un résultat
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Affichage graphique des termes de la suite

Compléter le script ci-dessous pour qu'il affiche les termes de la suite. On utilise la fonction plt.plot(X,Y), où X est la liste des abscisses des points que l'on souhaite tracer et Y la liste des ordonnées. On pourra se repporter à la partie du cours sur matplotlib.

Vous pouvez ensuite modifier comme vous le souhaiter ce script pour essayer de trouver des propriétés intéressantes. On peut par exemple observer que les "pics" ont l'air alignés selon un droite (Cela fait partie des conjectures sur cette suite).

affichage des termes de la suite de Van Eck
import matplotlib.pyplot as plt
# Indice jusqu'auquel on calcule les termes de la suite
N = 100000
# Copier coller ci dessous votre fonction VanEck(n)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Pour aller plus loin

Une des conjectures consiste à considérer le suite (un) des maximums entre 0 et n des valeurs de Vkk. La conjecture affirme que (un) aurait pour limite 1. Vous pouvez essayer de tester cette conjecture à l'aide d'un programme...

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants