Affordable Access

The Josephus problem

Authors
Publication Date
Disciplines
  • Mathematics

Abstract

The Josephus problem JOURNAL DE THÉORIE DES NOMBRES DE BORDEAUX LORENZHALBEISEN NORBERTHUNGERBÜHLER The Josephus problem Journal de Théorie des Nombres de Bordeaux, tome 9, no 2 (1997), p. 303- 318. <http://www.numdam.org/item?id=JTNB_1997__9_2_303_0> © Université Bordeaux 1, 1997, tous droits réservés. L’accès aux archives de la revue « Journal de Théorie des Nombres de Bordeaux » (http://jtnb.cedram.org/) implique l’accord avec les condi- tions générales d’utilisation (http://www.numdam.org/legal.php). Toute uti- lisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit conte- nir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ 303 The Josephus Problem par LORENZ HALBEISEN ET NORBERT HUNGERBÜHLER RÉSUMÉ. Nous donnons des formules explicites permettant de calculer les nombres de Josephus j (n, 2, i) and j (n, 3, i) et four- nissant une majoration et une minoration explicites de j(n, k, i) qui ne diffèrent que d’au plus 2k - 2 (dans le cas k = 4, ces bornes sont même meilleures). Nous proposons aussi un nouvel algorithme pour le calcul de ces nombres basé précisément sur ces estimations. ABSTRACT. We give explicit non-recursive formulas to compute the Josephus-numbers j(n, 2, i) and j(n, 3, i) and explicit upper and lower bounds for j(n, k, i) (where k ~ 4) which differ by 2k - 2 (for k = 4 the bounds are even better). Furthermore we present a new fast algorithm to calculate j(n, k, i) which is based upon the mentioned bounds. 1. Introduction The Josephus problem in its original form goes back to the Roman historian Flavius Josephus (see [3]). In the Romano-Jewish conflict of 67 A. D., the Romans took the town Jotapata which Josephus was commanding. He and 40 companions escaped and were trapped in a cave. Fearing capture they decided to kill themselves. Josephus and a friend did not ag

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

AnO(nlogm) algorithm for the Josephus Problem

on Journal of Algorithms Jan 01, 1983
More articles like this..