The Josephus problem

Lorenz Halbeisen; Norbert Hungerbühler

Journal de théorie des nombres de Bordeaux (1997)

  • Volume: 9, Issue: 2, page 303-318
  • ISSN: 1246-7405

Abstract

top
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 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.

How to cite

top

Halbeisen, Lorenz, and Hungerbühler, Norbert. "The Josephus problem." Journal de théorie des nombres de Bordeaux 9.2 (1997): 303-318. <http://eudml.org/doc/248008>.

@article{Halbeisen1997,
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 \ge 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.},
author = {Halbeisen, Lorenz, Hungerbühler, Norbert},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {non-recursive formulas; Josephus numbers; algorithm},
language = {eng},
number = {2},
pages = {303-318},
publisher = {Université Bordeaux I},
title = {The Josephus problem},
url = {http://eudml.org/doc/248008},
volume = {9},
year = {1997},
}

TY - JOUR
AU - Halbeisen, Lorenz
AU - Hungerbühler, Norbert
TI - The Josephus problem
JO - Journal de théorie des nombres de Bordeaux
PY - 1997
PB - Université Bordeaux I
VL - 9
IS - 2
SP - 303
EP - 318
AB - 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 \ge 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.
LA - eng
KW - non-recursive formulas; Josephus numbers; algorithm
UR - http://eudml.org/doc/248008
ER -

References

top
  1. [1] Burde, K.: "Das Problem der Abzählreime und Zahlenentwicklungen mit gebrochenen Basen". J. of Number Theory26 (1987), 192-209 Zbl0622.10005MR889384
  2. [2] Jakóbczyk, F.: "On the generalized Josephus problem". Glasgow Math. J.14 (1973),168-173 Zbl0278.05007MR327527
  3. [3] Josephus, F.: "The jewish war, Book III". Translated by H. S. Thackeray, Heinemann (1927), 341-366, 387-391 
  4. [4] Nörlund, N.E.: "Vorlesungen über Differenzenrechnung", Grundlehren d. math. Wissensch. 13, Springer, Berlin1924 Zbl50.0315.02JFM50.0315.02
  5. [5] Robinson, W.J.: "The Josephus problem". Math. Gazette44 (1960), 47-52 MR117163
  6. [6] Rouse Ball, W.W.: "Mathematical recreations and essays". Reprint New York (1962), 32-36 JFM52.0072.01
  7. [7] Woodhouse, D.: "The extended Josephus problem". Rev. Mat. Hisp.-Amer. (4) 33 (1973), 207-218 Zbl0299.05007MR330037

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.