Halbeisen, Lorenz; Hungerbühler, Norbert The Josephus problem. (English) Zbl 0905.05002 J. Théor. Nombres Bordx. 9, No. 2, 303-318 (1997). Summary: 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 \(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. Cited in 6 Documents MSC: 05A15 Exact enumeration problems, generating functions 11B37 Recurrences 05A05 Permutations, words, matrices Keywords:non-recursive formulas; Josephus numbers; algorithm PDF BibTeX XML Cite \textit{L. Halbeisen} and \textit{N. Hungerbühler}, J. Théor. Nombres Bordx. 9, No. 2, 303--318 (1997; Zbl 0905.05002) Full Text: DOI Numdam EuDML EMIS OpenURL Online Encyclopedia of Integer Sequences: A version of Josephus problem: a(n) is the surviving integer under the following elimination process. Arrange 1,2,3,...,n in a circle, increasing clockwise. Starting with i=1, delete the integer two places clockwise from i. Repeat, counting two places from the next undeleted integer, until only one integer remains. References: [1] Burde, K.: “Das Problem der Abzählreime und Zahlenentwicklungen mit gebrochenen Basen”. J. of Number Theory26 (1987), 192-209 · Zbl 0622.10005 [2] Jakóbczyk, F.: “On the generalized Josephus problem”. Glasgow Math. J.14 (1973),168-173 · 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, Berlin1924 · JFM 50.0315.02 [5] Robinson, W.J.: “The Josephus problem”. Math. Gazette44 (1960), 47-52 [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 · Zbl 0299.05007 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.