Halbeisen, Lorenz; Hungerbühler, Norbert
The Josephus problem
Journal de théorie des nombres de Bordeaux, Tome 9 (1997) no. 2 , p. 303-318
Zbl 0905.05002 | MR 1617400
URL stable : http://www.numdam.org/item?id=JTNB_1997__9_2_303_0

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 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.
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 k4) 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.

Bibliographie

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

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

[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 50.0315.02

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

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

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