Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-29T13:51:23.186Z Has data issue: false hasContentIssue false
  • English
  • Français

Functional iteration and the Josephus problem

Published online by Cambridge University Press:  18 May 2009

Andrew M. Odlyzko  and
Herbert S. Wilf
Andrew M. Odlyzko
Affiliation:
AT & T Bell Laboratories, Murray Hill, NJ 07974, USA
Herbert S. Wilf
Affiliation:
University of Pennsylvania, Philadelphia, PA 19104-6395, USA
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Information
Glasgow Mathematical Journal , Volume 33 , Issue 2 , May 1991 , pp. 235 - 240
Copyright
Copyright © Glasgow Mathematical Journal Trust 1991

References

REFERENCES

1.Ahrens, W. E. M. G., Mathematische Unterhaltungen und Spiele, (Teubner, 1918) 118–169.Google Scholar
2.Aulicino, D. J., and Goldfield, M., A new relation between primitive roots and permutations, Amer. Math. Monthly 76 (1969), 664–666.CrossRefGoogle Scholar
3.Graham, R. L., Knuth, D. E. and Patashnik, O., Concrete Mathematics, (Addison-Wesley, 1989).Google Scholar
4.Herstein, I. N. and Kaplansky, I., Matters mathematical (Chelsea, New York, 1978) 121–128.Google Scholar
5.Jakobczyk, F., On the generalized Josephus problem, Glasgow Math. J. 14 (1973), 168–173.CrossRefGoogle Scholar
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.Lloyd, E. L., An O(n log m) algorithm for the Josephus problem J. Algorithms 4 (1983), 262–270.CrossRefGoogle Scholar
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.Robinson, W. J., The Josephus problem, Math. Gaz. 44 (1960), 47–52.CrossRefGoogle Scholar
10.Woodhouse, D., The extended Josephus problem, Rev. Mat. Hisp.-Amer. (Ser. 4) 31 (1973), 207–218.Google Scholar