NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 08/05/2019

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique     Brèves de Maths

     

Topologie

 

Débutants

Géométrie

Graphe

 

Glossaire

Topologie

 

 

INDEX

 

Topologie

 

Logique

Eulérien

Planaire

 Multiple et diviseurs

Nœuds

Lexique

Coloration

Graphe de Delaunay

 Fourmis

 

Sommaire de cette page

>>> Chemin de multiples-diviseurs

>>> Longueur maximale du chemin

>>> Recherche par ordinateur

>>> Exemple de trois chemins avec n = 15

>>> Suite de tous les nombre jusqu' N

>>> Jeu Multiples–Diviseurs

 

 

 

 

MULTIPLES & DIVISEURS

Chemins eulériens

Graphe divisoriel ou chaine de divisibilité*

 

Vous connaissez le jeu qui consiste à suivre un dessin sans lever le crayon. Le tracé suit alors un chemin eulérien.

L'idée ici consiste à exécuter un tracé reliant les nombres entiers avec pour règle que le nombre suivant est un multiple ou un diviseur du précédent.

 

Un bon jeu pour enfants et adultes; propice exercices de programmation; et, un terrain pour les adeptes de la théorie des nombres.

Pour ces derniers, les questions qu'ils se posent:

*      quel est le chemin le plus long pour n donné ?

*      combien de chemins au minimum pour couvrir les nombres de 1 à n ?  

*      comment obtenir les nombres de 1 à N dans liste avec des nombres pas trop grands ?

*      etc.

 

* Divisibility chain: chaine de divisibilité.

Au sens strict: un élément de rang n est divisible par un de rang m si n est divisible par m

 

Chemin de multiples-diviseurs

 

Défi

Nombre de 1 à n organisés tels que chacun est le multiple (M) ou le diviseur (D) du suivant.

 

Sur la première ligne: 3 est un multiple de 1.

Le nombre 1 est un diviseur de 2.

 

Sur la dernière ligne (n = 4):

   4 est multiple de 2;

   2 est un diviseur de 1;

   1 est un diviseur de 3

 

Jusqu'à présent rien de plus simple, voire banal !

 

n = 3 – Deux possibilités: 312 et 213

 

3M1

1D2

2

2M1

1D3

3

 

 

n = 4 – Quatre possibilités

 

3M1

1D2

2D4

4

3M1

1D4

4M2

2

2D4

4M1

1D3

3

4M2

2D1

1D3

3

 

 

Remarque sur les nombres premiers

Un nombre premier ne peut être précédé ou suivi que du 1, et pas les deux à  la fois !

Ce qui impose que le nombre premier (en jaune) est en début ou fin de liste.

Sauf, s'il y a parmi les nombres de 1 à n, un multiple de P. Ce sera le cas pour n = 6, avec P = 3.

 

P est un nombre premier

 

1

P

P

1

 

Il existe un multiple de P

 

1

P

kP

kP

P

1

Avec le 5, présence de deux nombres premiers

Ces deux nombres premiers sans multiples sont obligatoirement placés en tête et queue de liste, laissant l'un d'eux orphelin.

 

n = 5 – Pas de solution en un seul chemin

 

3M1

1D2

2D4

4?

5

 

Il existe deux chemins: 3124 et 5.

 

 

 

Présence du 6 comme multiple de 3

Les deux nombres premiers

*    soit, entourent le 1,

*    soit, sont en tête et queue de liste

 

Nécessairement le 6 est voisin du 3.

Seul 2 divise 6, reste 4, multiple de 2.

Finalement, quatre solutions sont possibles symétriques deux à deux.

 

 

Défi équivalent: dessiner un chemin eulérien

Comment relier les nombres par un trait continu (sans lever le crayon) tout en respectant la règle.

 

n = 6 – Quatre chemins symétriques deux à deux

 

5

1

3

6

2

4

5

1

4

2

6

3

4

2

6

3

1

5

3

6

2

4

1

5

 

Les deux chemins eulériens

 

 

Avec un nombre premier supplémentaire

Impossible de réaliser le défi.

Il se résoudre à accepter deux suites.

En arrivant à 11, il faut trois suites.

Avec 13, une en plus, etc.  

 

n = 7 impose deux boucles

 

5

1

3

6

2

4

7

7

4

2

6

3

1

5

 

Longueur maximale du chemin

 

Recherche du chemin le plus long

Il est entendu qu'à partir de 7, il existe plusieurs chemins eulériens (Ch), et c'est inévitable.

 

Le prochain défi consiste, malgré tout, à trouver le chemin le plus long parmi les 7! = 5 040 permutations des nombres de 1 à 7.

 

 

Avec n = 7, il y toujours 2 chemins (Ch = 2). Il y a seize chemins de longueur maximale (Q = 16), en l'occurrence L = 6, soit, tous les nombres sauf un.
Les nombres exclus sont les nombres premiers 5 et 7 (en rouge)

 

n = 7, L = 6,

Ch = 2 et Q = 16

 

3, 6, 2, 4, 1, 5, 7

3, 6, 2, 4, 1, 7, 5

4, 2, 6, 3, 1, 5, 7

4, 2, 6, 3, 1, 7, 5

5, 1, 3, 6, 2, 4, 7

5, 1, 4, 2, 6, 3, 7

5, 3, 6, 2, 4, 1, 7

5, 4, 2, 6, 3, 1, 7

5, 7, 1, 3, 6, 2, 4

5, 7, 1, 4, 2, 6, 3

7, 1, 3, 6, 2, 4, 5

7, 1, 4, 2, 6, 3, 5

7, 3, 6, 2, 4, 1, 5

7, 4, 2, 6, 3, 1, 5

7, 5, 1, 3, 6, 2, 4

7, 5, 1, 4, 2, 6, 3

 

Exemples en jaune =>

 

 

n = 8, L = 7, Ch = 2 et Q = 32

Un des exemples =>

 

n = 9, L = 8, Ch = 2 et Q  = 32

Comme: 4, 8, 2, 6, 3, 9, 1, 5, 7

 

n = 10, L = 9, Ch = 2 et Q  = 80

Comme: 4, 8, 1, 5, 10, 2, 6, 3, 9, 7

 

N = 11 à 13

Ch = 3

 

Éric Saias, enseignant-chercheur à Sorbonne Université, a montré que le nombre minimal de chemins pour couvrir les entiers de 1 à n était supérieur à n/6 pour tout entier n.

 

 

Recherche par ordinateur

Jusqu'à n = 10, il existe 3 628 800 (= 10!) permutations des 10 nombres.

Une recherche "force brute" des permutations qui satisfont la règle de construction des suites de nombres est assez facile à implémenter.

Au-delà, pour éviter la saturation de la mémoire et limiter le temps de calcul, d'autres pistes doivent être mise en œuvre.

Un algorithme s'appuyant sur une table des diviseurs permet de limiter les chemins d'exploration et de calculer nombres après nombres. Il faut alors maitriser la gymnastique du cheminement dans les arbres (retour vers la bifurcation précédente, par exemple). Programmation avancée !

 

Exemple de disposition pour aide avec tableur

Création des colonnes des diviseurs de 1 à 15 par exemple.

Deux exemples d'essais sur les deux lignes en bas.

 

En commençant par 13, suivi du 1, on a choisit 15 pour suivre, amenant le 5, puis le 10, …

La dernière ligne est représentée sur le graphe qui suit..

 

 

Exemple de trois chemins avec n = 15

En bleu, toutes les possibilités de routes

 

 

Suite de tous les nombres jusqu' N

 

Défi n°2

Trouver une suite de nombres telle qu'elle contienne tous les nombres de 1 à N, une seule fois, quelle que soit les nombres utilisés.

Les nombres utilisés peuvent, bien entendu, dépasser N.

 

L'algorithme de construction semble simple. Mais les nombres intermédiaires croissent rapidement.

Est-il possible de trouver d'autres solutions avec des nombres moins grands ?

 

Les mathématiciens Éric Saias et Pierre Mazet ont montré qu'il est possible de construire une chaîne de divisibilité en s'assurant que le énième terme demeure toujours plus petit que:

 

Note: cette suite de nombres est répertoriée en OEIS- A064736.

 

Exemple

1, 2, pour obtenir le 3, on passe par le 6 = 2 x 3.

1, 2, 6, 3, pour le 4, on fait 3x4 = 12

1, 2, 6, 3, 12, 4, 20, 5 le 6 est déjà présent, passons au 7: 5 x 7 = 35

…5, 35, 7, 56, 8, 72, 9, 90, 10, etc.

 

Jusqu'à 100

1, 2, 6, 3, 12, 4, 20, 5, 35, 7, 56, 8, 72, 9, 90, 10, 110, 11, 143, 13, 182, 14, 210, 15, 240, 16, 272, 17, 306, 18, 342, 19, 399, 21, 462, 22, 506, 23, 552, 24, 600, 25, 650, 26, 702, 27, 756, 28, 812, 29, 870, 30, 930, 31, 992, 32, 1056, 33, 1122, 34, 1224, 36, 1332, 37, 1406, 38, 1482, 39, 1560, 40, 1640, 41, 1722, 42, 1806, 43, 1892, 44, 1980, 45, 2070, 46, 2162, 47, 2256, 48, 2352, 49, 2450, 50, 2550, 51, 2652, 52, 2756, 53, 2862, 54, 2970, 55, 3135, 57, 3306, 58, 3422, 59, 3540, 60, 3660, 61, 3782, 62, 3906, 63, 4032, 64, 4160, 65, 4290, 66, 4422, 67, 4556, 68, 4692, 69, 4830, 70, 4970, 71, 5183, 73, 5402, 74, 5550, 75, 5700, 76, 5852, 77, 6006, 78, 6162, 79, 6320, 80, 6480, 81, 6642, 82, 6806, 83, 6972, 84, 7140, 85, 7310, 86, 7482, 87, 7656, 88, 7832, 89, 8099, 91, 8372, 92, 8556, 93, 8742, 94, 8930, 95, 9120, 96, 9312, 97, 9506, 98, 9702, 99, 9900, 100

 

Plus loin

… 495, 245520, 496, 246512, 497, 247506, 498, 248502, 499, 249500, 500 …

…4995, 24955020, 4996, 24965012, 4997, 24975006, 4998, 24985002, 4999, 24995000, 5000 …

 

Programme Maple

Excellent petit exercice de programmation.

On déclare une liste R avec 1 et 2 pré-positionnés.

La boucle de calcul commence à 3 jusqu'au nombre N désiré (Ici N = 20).

Si le nombre n n'est pas déjà dans la liste R (has), on calcule le produit du dernier nombre de r par n. R[nops(R)] veut dire que dans R on veut l'élément de rang nops(R) avec nops donnant la quantité d'éléments dans R.

La liste R est complétée des deux nouveaux, m (le multiple) et n (le nombre suivant.

 

En bleu, le résultat du calcul. Notez que le nombre 20 demandé n'apparait pas en fin de liste. Il est apparu en septième position.

 

 

 

[1, 2, 6, 3, 12, 4, 20, 5, 35, 7, 56, 8, 72, 9, 90, 10]

 

 

Programme Python

Définition d'une fonction multiples-diviseurs.

Exactement mêmes instructions qu'en Maple.

À noter: boucle jusqu'à n + 1 pour avoir un résultat jusqu'à n inclus.

La non-appartenance s'exprime simplement par not in (pas dedans).

Accès au dernier élément de la liste (comme possible aussi avec Maple) par l'indice -1.

Ajouter un élément  se fait aves append (apposer), mais un seul élément à la fois.

 

Voir ProgrammationIndex  / PythonIndex  

 

 

Jeu Multiples–Diviseurs

 

Le jeu consiste à réaliser une suite de nombres tels que le suivant soit toujours un nombre nouveau multiple ou diviseur du précédent.

Une grille des nombres de 1 à 100 sert de support au jeu (illustration). Le premier joueur fait un choix, le second enchaine. Les nombres choisis sont barrés au fur et à mesure.

On montre que le second joueur peut toujours gagner la partie. Un exercice de programmation consiste à faire jouer l'ordinateur en second et l'amener à gagner à tout coup.

Exemple de partie: 14, 2, 62, 31, 93, 3, 57, 19, 95, 5, 55, 11, 77, 7, 91, 13, 65.

Voir le lien pour son implémentation Scratch

Allez dans le projet (voir à l'intérieur) pour rendre visible la liste des nombres joués.

 

Page imaginée d'après l'article de Roger Mansuy

 

 

 

 

Suite

*         Chemin le plus court

*         Marche de l'ivrogne

*         Voyageur de commerce

*         Vocabulaire des graphes

*         Coloration des graphes (nombre chromatique)

*         Petit monde

*         Sept amis autour d'une table

Voir

*         Code Gray

*         Croissance logistique

*         Énigmes et paradoxes

*         Graphe de Delaunay

*         Intelligence artificielle

*         JeuxIndex

*         Logique formelle

*         Percolation

*         Relier les points d'un seul coup de crayon

*         TopologieGlossaire

*         Tour de Brahmâ

*         Trois maisons (énigme des -)

Sites

*            Enchaînons multiples set diviseurs – Roger Mansuy – La Recherche – Mars 2019 – N°545

*            Factors ans multiple chain – Jeu interactif de construction de suite multiples-diviseurs.

*            A game of multiples and divisors – Redfrontdoor – Réflexions sur le jeu multiples-diviseurs et sa programmation

*            Ce jeu en Scratch – mit-edu – 2015

*            OEIS A064736 – a(1)=1, a(2)=2; for n>0, a(2*n+2) = smallest number missing from {a(1), ... ,a(2*n)}, and a(2*n+1) = a(2*n)*a(2*n+2)

*            Étude du graphe divisoriel 4** – Pierre Mazet et Éric Saias

Cette page

http://villemin.gerard.free.fr/aMaths/Topologi/aaaGraph/MulDiv.htm