FUNCTIONAL ITERATION AND THE JOSEPHUS PROBLEM

by ANDREW M. ODLYZKO and HERBERT S. WILFf

(Received 27 February, 1990)

1. Introduction. 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 q\h 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 qih one of the places clockwise around from/ 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 [l]-[10]). In this paper we deal with the 7,(n)'s.
Here we observe that in one of the known algorithms for solving the problem, the
sequence of numbers that is generated is remarkably well approximated by a single term
of its asymptotic series. This result, which essentially is a property of the iterated 'ceiling'
function, is both of independent interest and also permits us to find an explicit-looking
formula for J3(n) ((5) below).
For a fixed a > 1 we study the sequence f0 = 1, /„+, = \afn] (n s 0) (we use '("•]' and
'[•J' for the ceiling and the floor functions, respectively). We show that although these
iterates grow exponentially fast, they are approximate to within O(l) by a single term of
their asymptotic expansions.

2. Results. In [3, Section 3.3], an interesting approach to the Josephus problem is

described, and the authors give the following procedure for finding Jq(n).
(a) Define a sequence {Dkq'i}kZ:0 by

] l). (1)
(b) Determine the least integer k such that D[q) > (q - \)n.
(c) Then the answer is Jq{n) = qn + l - Dkq).
We study the behavior of the Dkq\ The striking feature that we find is that they are
extremely well approximated by the first term of their asymptotic formulas, for large k
and fixed q.
THEOREM 1. For each integer q~>2 there is a real number K(q) such that

+ 6k,q, (2)

in which ek2 = 0 for all k and if q^3 then

-(q-2)<ek,q<0 (fcad). " (3)
t Research supported by the U.S. Office of Naval Research.

Glasgow Math. J. 33 (1991) 235-240.

[Link] Published online by Cambridge University Press

 236 ANDREW M. ODLYZKO AND HERBERT S. WILF
As a trivial consequence, note that since K(2) = 1, the well known formula
J2(n) = 1 + 2(n - 2llog2"J) (n - 0 , 1 , . . .)
holds.
COROLLARY 1. We have the 'exact formula'
Dj?>=L*(3)(i)*| (k = 0 , 1 , . . . ) , (4)
and so we have also the 'exact formula'
J3(n) = 3/i + 1 - L^(3)(l)no8M((2-+1)/iC(3))1J (n = 0 , 1 , . . .), (5)
where K(3) = 1-62227 05028 84767 31595 69509 82899 32411....

3. Proofs. We will prove a little more than is necessary for Theorem 1 above. Fix
a>\, and let/(*) = \ax). We study the iterates/„ =/„(<*) of/, defined by
/„+. =/(/,) = M (n a 0; /„ = 1). (6)
PROPOSITION 1. There exists a constant c = c(a) such that
/„(«)-c(ar)«" (/!->«).. (7)
Proof. Define
un =fja". (8)
We claim that {«„} is increasing and bounded from above. It increases because

and is bounded from above because

a"+lun+l = \a"+1un] < 1 + a"+lun
implies that
u n+1 <M n + a--n-1 (n^0),
which in turn implies that un < a I {a - 1) for all n s 0. •
We now study the error term in the asymptotic formula (7). The next proposition
shows that the error is very small in many cases.
PROPOSITION 2. If a=^2 or if a = 2-l/m for integer m > 2 , then

Proof. We define numbers {en} by

fn = <xfn_x + en =\afn-1] («>1), (9)
so 0 ^ en < 1. With the «„ of (8) above, we have
/„ = una" = au^a"'1 + en = un^a" + en,
from which un = un_l + en/a" and

[Link] Published online by Cambridge University Press

 THE JOSEPHUS PROBLEM 237
It follows that
/„ = c(a)a" - 2 ^ r > (10)
and that

Thus 0 < c(a)a" -fn < l/(ar - 1) for all n, and the result follows.
Finally, if a is rational we can bound the en's away from 1 and extend the result
slightly. Indeed, suppose a = 2-l/m for integer m > 2 . Then (9) shows that all
\en\ < (m - 1)1 m, and (10) yields

However it cannot happen that all en = (m — 1)1 m for n > n0, for otherwise we would
have /„ =c(a)(2- 1/m)" - 1, but the right side cannot be an integer for all n>n0,
completing the proof. •
To finish the proof of Theorem 1 we return to the parameter values that occur in the
Josephus problem. Let a = ql(q - 1) and write K{q) for c(a) in (5), to find that

Now from (9),

and so {q - l)ek is an integer in the range [ - {q - 2), 0]. The estimate (3) of Theorem 1
now follows, and the proof is complete. •

4. The function c(ar). In this section we study the 'constant' c(a), as a function of
a. A brief table of c(a), showing some of its irregular behavior, is in Table 1.
A graph of c(a), for 1 1 < a < 2-5 is shown in Figure 1.

TABLE 1. SOME VALUES OF c(a)

a c(«)
1-050000 11-8354164...
1-125000 51954489...
11250 + 5-8448800. . .
1-166666 4-0371021. . .
11666 + 4-7099524. . .
1-200000 3-2438724...
1-2000 + 3-8926469...
1-250000 2-0763957...
1-500000 1-6222705...
1-900000 1-2701620...
2-000000 1-0000000...
2-0000 + 20000000...
2-500000 1-3653870...
5-500000 1-1311946...

[Link] Published online by Cambridge University Press

 238 ANDREW M. ODLYZKO AND HERBERT S. WILF

Figure 1. c(a) vs. a.

It is easy to see that at the integers the function c(a) has jump discontinuities of the
following kind:

(+) () + = 1 + ( 2 3 )
m —1 m— 1
We are also able to make a quantitative statement about the jumps at the Josephus
points, as the following proposition shows.
PROPOSITION 3. At the Josephus points aq = q/(q — 1), the function c(a) has jump
discontinuities of the form
c(a+) = ac(a) (a-= 2,3/2,4/3,5/4,. . . ) . (11)
Proof. We claim that at such a value of a the sequences {fn(a)} and {fn(a+)} are
related by

which would establish the truth of the proposition. To prove (12), it suffices to show that
{/„(*) - 1} satisfies the same recurrence that {fn_1(a+)} does, namely the recurrence
\(a + e ) ( / » - 1)1 = / n + 1 ( * ) - l ,
for each « s 1 and all small enough e.

[Link] Published online by Cambridge University Press

 THE JOSEPHUS PROBLEM 239
But the left side is
\afn(a) - a + efn{a) - e] = \afn(a) - 1 + (1 - a - e) + efn(a)]

If (q-l)\fn(a) then the last member above is (q/(q - l))fn(a) - 1, i.e., it is

/ „ + , ( * ) - 1 , as required.
Next suppose that /„(<*) = (q — \)m + r (1« r =£ q — 2). Then the last member above
is

e(fn(a) - 1)| - 1 = qm + r =/ n + 1 (a) - 1.

5. Remarks, and a conjecture, (i) As it stands, our 'explicit' formula for J3(n) is
not a dramatic improvement over the algorithm in (1), because the computation of the
universal constant K(3) requires the Dk's of (1). This situation could change if some
independent method were found to calculate /C(3) with high precision.
(ii) We would like to know more about the function c(a). In particular, does it
satisfy some functional equation? Can one evaluate it at the Josephus points in some way
that is quite independent of the algorithm (2)? What more can be proved about the sizes
of its discontinuities?
(iii) If q >2 then in view of the uncertainty (3) in the formula (2), what we know is
that D^ is one of the q - 2 numbers

This means that the correct value of Jn(q) is known to be one of q — 2 consecutive places
around the circle (the chance of survival has increased from 1: n to 1: (q — 2)).
(iv) We have a conjecture about the error in the general asymptotic formulas above.
In the Josephus case, where a = q/(q — 1), we conjecture that the integers (q — l)en,
which assume only the values 0,1,... ,q -2, in fact are asymptotically uniformly
distributed on those q - 1 values, and furthermore that small sets of successive values are
asymptotically independent. This would imply that if q =: 2,

This conjecture is likely to be quite difficult to settle.

[Link] Published online by Cambridge University Press

 240 ANDREW M. ODLYZKO AND HERBERT S. WILF
REFERENCES
1. W. E. M. G. Ahrens, Mathematische Unterhaltungen undSpiele, (Teubner, 1918) 118-169.
2. D. J. Aulicino, and M. Goldfield, A new relation between primitive roots and
permutations, Amer. Math. Monthly 76 (1969), 664-666.
3. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, (Addison-Wesley,
1989).
4. I. N. Herstein and I. Kaplansky, Matters mathematical (Chelsea, New York, 1978)
121-128.
5. F. Jakobczyk, On the generalized Josephus problem, Glasgow Math. J. 14 (1973),
168-173.
6. D. E. Knuth, The Art of Computer Programming, Vol. 1 (Addison-Wesley, 1973), Ex.
[Link], and Vol. Ill (1975), Ex. [Link].
7. E. L. Lloyd, An O(« logm) algorithm for the Josephus problem, J. Algorithms 4 (1983),
262-270.
8. R. A. MacFhraing, (R. A. Rankin), Aireamh muinntir Fhinn is Dhubhain, agus sgeul
Iosephuis is an da 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).
9. W. J. Robinson, The Josephus problem, Math. Gaz. 44 (1960), 47-52.
10. D. Woodhouse, The extended Josephus problem, Rev. Mat. Hisp.-Amer. (Ser. 4) 31 (1973),
207-218.

AT & T BELL LABORATORIES UNIVERSITY OF PENNSYLVANIA

MURRAY HILL PHILADELPHIA, PA 19104-6395
NJ 07974 USA
USA

[Link] Published online by Cambridge University Press