Geodesic
Functional iteration and the Josephus problem
Glasgow mathematical journal, Tome 33 (1991) no. 2, pp. 235-240

Voir la notice de l'article provenant de la source Cambridge University Press

The problem of Josephus is the following. We are given two positive integers n, q. There are n places arranged around a circle, and numbered clockwise 1, 2, ..., n. Each of n people takes one of the places, then (please excuse this, but we didn't invent the problem!) every qth one is executed, until just one remains. More precisely, the occupant of place q is ‘removed’ first, and in general, if some place j has just been vacated, then the qth one of the places clockwise around from j that are still occupied will be vacated next. One question is this: if you would like to be the last survivor, then into what place should you go initially? We denote the answer to this question by Jq(n). For example, if n = 5 and q = 2, the order of execution is 2, 4, 1, 5, 3, and J2(5) = 3. Other questions have been raised about the problem, and it has an extensive literature (see [1]–[10]). In this paper we deal with the Jq(n)'s. 
Odlyzko, Andrew M.; Wilf, Herbert S. Functional iteration and the Josephus problem. Glasgow mathematical journal, Tome 33 (1991) no. 2, pp. 235-240. doi: 10.1017/S0017089500008272
@article{10_1017_S0017089500008272,
     author = {Odlyzko, Andrew M. and Wilf, Herbert S.},
     title = {Functional iteration and the {Josephus} problem},
     journal = {Glasgow mathematical journal},
     pages = {235--240},
     year = {1991},
     volume = {33},
     number = {2},
     doi = {10.1017/S0017089500008272},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/S0017089500008272/}
}
TY  - JOUR
AU  - Odlyzko, Andrew M.
AU  - Wilf, Herbert S.
TI  - Functional iteration and the Josephus problem
JO  - Glasgow mathematical journal
PY  - 1991
SP  - 235
EP  - 240
VL  - 33
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1017/S0017089500008272/
DO  - 10.1017/S0017089500008272
ID  - 10_1017_S0017089500008272
ER  - 
%0 Journal Article
%A Odlyzko, Andrew M.
%A Wilf, Herbert S.
%T Functional iteration and the Josephus problem
%J Glasgow mathematical journal
%D 1991
%P 235-240
%V 33
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1017/S0017089500008272/
%R 10.1017/S0017089500008272
%F 10_1017_S0017089500008272

[1] 1.Ahrens, W. E. M. G., Mathematische Unterhaltungen und Spiele, (Teubner, 1918) 118–169. Google Scholar

[2] 2.Aulicino, D. J., and Goldfield, M., A new relation between primitive roots and permutations, Amer. Math. Monthly 76 (1969), 664–666. Google Scholar | DOI

[3] 3.Graham, R. L., Knuth, D. E. and Patashnik, O., Concrete Mathematics, (Addison-Wesley, 1989). Google Scholar

[4] 4.Herstein, I. N. and Kaplansky, I., Matters mathematical (Chelsea, New York, 1978) 121–128. Google Scholar

[5] 5.Jakobczyk, F., On the generalized Josephus problem, Glasgow Math. J. 14 (1973), 168–173. Google Scholar | DOI

[6] 6.Knuth, D. E., The Art of Computer Programming, Vol. 1 (Addison-Wesley, 1973), Ex. 1.3.2.22, and Vol. III (1975), Ex. 5.1.1.2. Google Scholar

[7] 7.Lloyd, E. L., An O(n log m) algorithm for the Josephus problem J. Algorithms 4 (1983), 262–270. Google Scholar | DOI

[8] 8.MacFhraing, R. A., (Rankin, R. A.), Aireamh muinntir Fhinn is Dhubhain, agus sgeul Iosephuis is an dà fhichead Iudhaich (The numbering of Fionn's and Dubhan's men, and the story of Josephus and the forty Jews), Proc. Royal Irish Acad. Sect. A 52 (1948), 87–93 (Gaelic. English summary; MR 10 (1949), 509). Google Scholar

[9] 9.Robinson, W. J., The Josephus problem, Math. Gaz. 44 (1960), 47–52. Google Scholar | DOI

[10] 10.Woodhouse, D., The extended Josephus problem, Rev. Mat. Hisp.-Amer. (Ser. 4) 31 (1973), 207–218. Google Scholar

Cité par Sources :