The Josephus problem

Halbeisen, Lorenz; Hungerbühler, Norbert

Halbeisen, Lorenz ; Hungerbühler, Norbert

Journal de théorie des nombres de Bordeaux, Tome 9 (1997) no. 2, pp. 303-318.

Résumé
Abstract

Nous donnons des formules explicites permettant de calculer les nombres de Josephus $j (n, 2, i)$ and $j (n, 3, i)$ et fournissant une majoration et une minoration explicites de $j (n, k, i)$ qui ne diffèrent que d’au plus $2 k - 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.

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 \geq 4$ ) which differ by $2 k - 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.

MR Zbl

@article{JTNB_1997__9_2_303_0,
     author = {Halbeisen, Lorenz and Hungerb\"uhler, Norbert},
     title = {The {Josephus} problem},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {303--318},
     publisher = {Universit\'e Bordeaux I},
     volume = {9},
     number = {2},
     year = {1997},
     mrnumber = {1617400},
     zbl = {0905.05002},
     language = {en},
     url = {https://www.numdam.org/item/JTNB_1997__9_2_303_0/}
}

TY  - JOUR
AU  - Halbeisen, Lorenz
AU  - Hungerbühler, Norbert
TI  - The Josephus problem
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1997
SP  - 303
EP  - 318
VL  - 9
IS  - 2
PB  - Université Bordeaux I
UR  - https://www.numdam.org/item/JTNB_1997__9_2_303_0/
LA  - en
ID  - JTNB_1997__9_2_303_0
ER  -

%0 Journal Article
%A Halbeisen, Lorenz
%A Hungerbühler, Norbert
%T The Josephus problem
%J Journal de théorie des nombres de Bordeaux
%D 1997
%P 303-318
%V 9
%N 2
%I Université Bordeaux I
%U https://www.numdam.org/item/JTNB_1997__9_2_303_0/
%G en
%F JTNB_1997__9_2_303_0

Halbeisen, Lorenz; Hungerbühler, Norbert. The Josephus problem. Journal de théorie des nombres de Bordeaux, Tome 9 (1997) no. 2, pp. 303-318. https://www.numdam.org/item/JTNB_1997__9_2_303_0/

Bibliographie
Cité par

[1] Burde, K.: "Das Problem der Abzählreime und Zahlenentwicklungen mit gebrochenen Basen". J. of Number Theory 26 (1987), 192-209 | MR | Zbl

[2] Jakóbczyk, F.: "On the generalized Josephus problem". Glasgow Math. J. 14 (1973),168-173 | MR | Zbl

[3] Josephus, F.: "The jewish war, Book III". Translated by H. S. Thackeray, Heinemann (1927), 341-366, 387-391

[4] Nörlund, N.E.: "Vorlesungen über Differenzenrechnung", Grundlehren d. math. Wissensch. 13, Springer, Berlin 1924 | JFM

[5] Robinson, W.J.: "The Josephus problem". Math. Gazette 44 (1960), 47-52 | MR

[6] Rouse Ball, W.W.: "Mathematical recreations and essays". Reprint New York (1962), 32-36 | JFM

[7] Woodhouse, D.: "The extended Josephus problem". Rev. Mat. Hisp.-Amer. (4) 33 (1973), 207-218 | MR | Zbl