Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 30/10/2021

M'écrire

Brèves de Maths

 

INDEX

 

Cribles

Premiers et ordre

Nombres (Classification)

Types de nombres

NOMBRES CHANCEUX

Chanceux

Josèphe

Ulam

Euler

 

 

Problème de Josèphe

ou de Josephus

 

Vieux problème qu’aurait rapporté l’historien Flavius Josèphe (Ier siècle de notre ère) où il s’agissait, dans un cercle de soldats prisonniers, d’en éliminer un sur trois.

Le problème de Josephus, un procédé de tri sélectif,  est un classique en matière d'exercice de programmation. Objet également de nombreuses variantes au cours de l'histoire.

On commence par les nombres chanceux de Josèphe résultant de l'application d'un crible très simple.

   

 

Sommaire de cette page

>>> Nombres chanceux de Josèphe

>>> Texte original

>>> La légende de Josephus

>>> Le problème de Joseph

>>> Théorie – Passage en binaire

>>> Programmation

>>> Exemple avec k = 3

 

Débutants

Nombres premiers

 

Glossaire

Nombres premiers

 

 

Nombres chanceux de Josèphe

haut

 

Nombres qui résistent au crible de tri sélectif simple suivant:

On commence par lister les nombres entiers et on en élimine un sur deux; restent les nombres impairs sur la deuxième ligne.

Parmi ceux-ci, on en élimine un sur trois.

Parmi ceux qui subsistent, on en élimine un sur quatre, etc.

 

Les nombres chanceux d'Ulam sont engendrés par un procédé voisin.

 

 

 

 

Sur ce tableau en colonne de gauche, le numéro de la ligne k qui indique qu'un nombre sur k est éliminé.

Le premier tri élimine les nombres pairs. Ils ne sont pas représentés sur ce tableau.

En jaune, les nombres éliminés.

 

 

 

Suite des nombres chanceux de Josèphe jusqu'à 5 000

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289, 307, 349, 387, 399, 459, 481, 529, 567, 613, 649, 709, 763, 807, 843, 927, 949, 1009, 1093, 1111, 1189, 1261, 1321, 1359, 1471, 1483, 1579, 1693, 1719, 1807, 1899, 1933, 2023, 2161, 2187, 2269, 2367, 2479, 2533, 2703, 2739, 2799, 2967, 3019, 3147, 3199, 3327, 3421, 3529, 3619, 3807, 3841, 3913, 4083, 4203, 4249, 4407, 4603, 4623, 4783, 4891, 5067 

 

 

Texte original de Verna Gardiner, R. Lazarus, N. Metropolis et S.Ulam.

Consider the sequence of all positive integers, 1, 2, 3, … We shall now strike out from this sequence every second term by counting from 1. The odd integers will be left. We shall now strike out every third integer in the remaining sequence, again starting to count from 1, but considering only the remaining integers. We shall obtain a second sequence of integers. The next step is to strike out every fourth integer counting only the remaining ones and we obtain another subsequence. We can continue this process Indefinitely. It is obvious that infinitely many integers will remain after we have completed the process.

 

Considérons la séquence de tous les nombres entiers positifs, 1, 2, 3, ... Nous allons maintenant rayer de cette séquence chaque deuxième terme en comptant à partir de 1. Il restera les nombres entiers impairs. Nous allons maintenant rayer tous les troisièmes entiers de la séquence restante, en commençant à nouveau à compter à partir de 1, mais en ne considérant que les entiers restants. Nous obtenons ainsi une deuxième séquence d'entiers. L'étape suivante consiste à rayer chaque quatrième entier en ne comptant que les entiers restants et nous obtenons une autre sous-séquence. Nous pouvons continuer ce processus indéfiniment. Il est évident qu'il restera une infinité d'entiers après que nous ayons terminé le processus.

 

 

Lègende de Josephus

Josephus Flavius,  historien juif du premier siècle (v.34-v100).

Il est prisonnier des Romains dans une cave de Yodfat  (nord d'Israël actuel) avec quarante soldats.

Ceux-ci préfèrent se suicider plutôt que de se rendre.

Décision est prise que chacun tuera le troisième à sa gauche et le dernier le fera lui-même.

Josephus, ne voulant pas mourir, trouva la place à occuper pour être le dernier.

Note personnelle: j'ai eu l'occasion de visiter le site  impressionnant de Massada, une ville fortifiée perchée en haut d'un piton rocheux. Lieu assiégé par les Romains en 72 et 73. Les occupants se sont suicidés plutôt que de se livrer aux Romains.

De nombreux experts en récréations mathématiques ont adapté le problème de Josephus. Ainsi, Dudeney propose un jeu de chat et de souris. Treize souris sont en cercle, toutes noires sauf une blanche. Le chat doit manger une souris sur treize et ne manger la blanche qu'en dernier. Par laquelle doit-il commencer. Charitable, Dudeney explique que, le chat prenant son temps pour réfléchir s'est endormi, et les souris se sont échappées.

Le puzzle et sa solution (anglais)

Note: pour une traduction ouvrir le site "traduction Google" ou le site "DeepL"

et copier coller le texte dans la fenêtre

 

 

Problème de Josèphe ou de Josephus

haut

 

 

Le défi

Ce sont cinq soldats rangés en cercle (S1, S2, S3, S4  et S5).

Ils doivent être exécutés les uns après les autres en épargnant un soldat sur deux jusqu'à ce qu'il n'en reste qu'un seul.

L'un d'eux (le chef, un soldat méritant, ou autre) est désigné pour être épargné. Mais, à lui de choisir la bonne place.

 

Solution

En périphérie du cercle, les nombres indiquent l'ordre d'exécution: S2, S4, S1, S5 et S3.

Le soldat en position 3 sera sauvé.

 

On note f(5) = 3.

Quelles sont les positions pour n soldats ?

Voir Brève 772

 

 

 

Cas de neuf soldats
et représentation en lignes.

 

Le soldat sauvé est également celui en troisième position: f(9) = 3.

 

 

 

Valeur de f(n)

 

Valeur de f(n) en fonction de n (colonne colorées lorsque n  = 2m)

 

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

f(n)

1

1

3

1

3

5

7

1

3

5

7

9

11

13

15

1

 

Liste de 200 valeurs

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145 …

 

Propriétés

 

La fonction f(n) est la suite des nombres impairs.

Elle repasse par 1 à chaque puissance de 2.

 

 

Formules

 

Récurrence: f(2n) = 2 f(n) – 1   & f(2n + 1) = 2f(n) + 1

 

Récurrence dans le cas général où on passe k soldats:

                     f(n, k) = (f(n – k ) + k) mod (n) + 1

                     f(n, 2) = (f(n – 1 ) + 1) mod (n) + 1

                     f(1, k) = 0

 

Absolu: si n = 2m + L et 0 ≤ L ≤ 2m , alors f(n) = 2L + 1

 

 

 

Bit  à bit

 

La solution est immédiate en binaire avec un simple échange de bits.

Exemple avec f(10) = 5

*      Prenons 10 en binaire: 1010

*      Passons le premier bit en queue: 0101

*      Sa valeur décimale est: 5

 

 

Amusement

 

Une représentation amusante pour les valeurs de f(n).

 

Lire la quantité de carreaux dans la forme en face du nombre.

 

Ex: f(7) = 7  et il y a 7 petits carreaux dans la forme bleue en L.

 

Représentation due à Omar E. Pol

 

 

 

Théorie

 

Tableau du haut avec 4, 8 et 16

Si n est une puissance de 2, on vérifie que f(n) = 1.

 

Tableau du bas avec 5, 6 et 7

Lorsqu'on ajoute un élément, f(n) progresse de 2

 

Formalisation

Si un nombre est égal à une puissance de 2, alors f(n) = 1.

Si on ajoute L à cette puissance de 2, alors on ajoute 2L à f(n)

Bilan: si n = 2m + L, alors f(n) = 1 + 2L

 

Correspondance

(exemple avec valeurs binaires à droite)

 

n = 20

= 16 + 4

10100

f(n) =

1+ 2x 4 = 9

01001

 

 

Puissances de 2

 

Adjonction d'éléments

 

 

Effet binaire

La puissance 2m  est la plus grande puissance de 2 incluse dans le nombre n; elle correspond au chiffre initial de poids fort. Celui-ci contribue pour +1 dans f(n).

 

Le nombre qui reste (n amputé du premier bit) est égal à L, lequel est doublé pour former f(n). Or, un doublement (multiplication par 10 en binaire) a pour effet de décaler les bits d'un cran vers la gauche.

 

Bilan

Le nombre binaire initial

*      est tronqué à gauche,

*      ses bits sont décalés d'un cran vers la gauche et,

*      à ce nouveau nombre on ajoute 1.

 

 

 

Programmation

haut

 

Programme Maple avec k = 2

 

 

But

Former la liste des valeurs de f(n) jusqu'à une valeur spécifiée (mx).

 

Principe

Calculer les valeurs par récurrence à partir de f(0) et éditer la suite (seq).

 

Commentaires

Initialisation générale; de la valeur de départ f(0) et de la borne de calcul (mx).

Boucle de calcul avec la formule de récurrence. Les valeurs calculées sont conservées en mémoire avec l'étiquette f(n).

En fin de programme, édition de ces valeurs sous la forme d'une suite de valeurs .

 

 

Programme Python avec k = 3

 

Commentaires

La même formule de récurrence est utilisée.

Le calcul récursif est implémenté par une fonction (def).

Le programme principal est un exemple: Ici, le cas historique de Josephus avec n = 41 soldats et un tué tous les trois (k = 3). C'est le n°31 qui est sauvé.

Voir illustration ci-dessous >>>

Voir ProgrammationIndex

 

Exemples avec k = 3

haut

 

Examen détaillé du cas n = 5 et  k = 3

Le cercle extérieur représente la situation au départ.

À chaque tour, les soldats épargnés avancent d'un pas vers le centre. Les sacrifiés sont signalés par un petit carré.

Au premier tour (cercle 2), les n°1 et n°2 sont épargnés et le n°3 est sacrifié (s1).

Après avoir épargné les n°4 et n°5, c'est au tour du n°1 d'être sacrifié (s2).

Etc.

 

 

  

 

Cas n = 5,  k = 3 => Sauvé en 4

Même cas: présentation développée en cercles indépendants

 

Cas n = 41, k = 3 => Sauvé 31

 

 

 

 

 

 

Retour

*      Nombres chanceux par plage

Voir

*      Nombres chanceux d'Ulam 

*      Les gardes du fortin

*      Jeu du solitaire

*      Réussite en sautant une carte

*      Différences k-ièmes

Aussi

*      Euler

*      Représentation des nombres

*      Théorie des nombres

Sites

*      Le problème de Josèphe – Wikipédia

*      Simulation des solutions avec GeoGebra – Carlos Fleitas, Chip Rollinson

*      Le problème de Josephus*   PolytechniqueProgrammation de la version générale

*      The Josephus ProblemNumberphile – Daniel Erman – Vidéo

*      Josephus problem – Geeksfor Geeks

*      On Josephus problem – Laurent Signac – 2019 Poitiers – Analyse historique complète – pdf 26 pages

*      OEIS A000960 – Flavius Josephus's sieve.

*      OEIS A006257 - Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.

Cette page

http://villemin.gerard.free.fr/aMaths/Cribles/Josephe.htm