The Josephus problem. (English) Zbl 0905.05002

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.


05A15 Exact enumeration problems, generating functions
11B37 Recurrences
05A05 Permutations, words, matrices
Full Text: DOI Numdam EuDML EMIS


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