\magnification 1200 \def\vrl{\vrule width 5pt height 5pt} \centerline{\bf Functional iteration and the Josephus problem} \vskip 10pt \centerline{Andrew M. Odlyzko} \centerline{AT\&T Bell Laboratories} \centerline{Murray Hill, NJ 07974} \vskip 7pt \centerline{and} \vskip 7pt \centerline{Herbert S. Wilf\footnote{*}{Research supported by the U. S. Office of Naval Research}} \centerline{University of Pennsylvania} \centerline{Philadelphia, PA 19104-6395} \vskip .5 true in \centerline{\bf 1. Introduction} \vskip 4pt 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,\ldots ,n$. Each of $n$ people takes one of the places, then (please excuse this, but we didn't invent the problem!) every $k$th one is executed, until just one remains. More precisely, the occupant of place $k$ is `removed' first, and in general, if some place $j$ has just been vacated, then the $k$th 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 $J_q(n)$. For example, if $n=5$ and $q=2$, the order of execution is 2, 4, 1, 5, 3, and $J_2(5)=3$. There are other questions that have been raised about the problem, and it has an extensive literature (see [1]-[10]). In this paper we deal with the $J_q(n)$'s. What we have to contribute is the observation that in one of the algorithms that has been proposed 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, as we will see below, is both of independent interest and also permits one to write down an explicit-looking formula for $J_3(n)$ ((5) below). More precisely, we write `$\lceil\cdot\rceil$' and `$\lfloor\cdot\rfloor$' for the ceiling and the floor functions respectively. For a fixed real $\alpha >1$ we study the sequence $f_0=1$, $f_{n+1}=\lceil{\alpha f_n}\rceil\quad (n\ge 0)$. We show that although these iterates grow exponentially fast, they are approximable to within $O(1)$ by a single term of their asymptotic expansion. \vskip 10pt \centerline{\bf 2. Results} \vskip 4pt In [3], section 3.3, an interesting approach to the Josephus problem is described, and the authors give the following procedure for finding $J_q(n)$: {\parindent 40pt \item{(a)} Define a sequence $D_n^{(q)}$ by $$D_n^{(q)}=\bigl\lceil{{q\over {q-1}}D_{n-1}^{(q)}}\bigr\rceil\qquad (n\ge 1;\, D_0^{(q)}=1).\eqno(1)$$ \item{(b)} Determine the least integer $k$ such that $D_k^{(q)}>(q-1)n$. \item{(c)} Then the answer is $J_q(n)=qn+1-D_k^{(q)}$. } We study the behavior of the $D_n^{(q)}$. The striking feature that we find is that they are extremely well approximated by the first term of their asymptotic formulas, for large $n$ and fixed $q$. \proclaim Theorem 1. For each integer $q\ge 2$ there is a real number $K(q)$ such that $$D_n(q)= K(q)\bigl({q\over {q-1}}\bigr)^n +\epsilon_{n,q},\eqno(2)$$ in which all $\epsilon_{n,2}=0$ and if $q\ge 3$ then $$-(q-2)<\epsilon_{n,q}\le 0\qquad (n\ge 0).\eqno(3)$$ \vskip 6pt As a trivial corollary, we note that clearly $K(2)=1$, so the well known formula $$J_2(n)=1+2(n-2^{\lfloor \log_2{n}\rfloor})\qquad (n=0,1,\ldots )$$ holds. \proclaim Corollary 1. We have the `exact formula' $$D_n^{(3)}=\bigl\lfloor K(3)({3\over 2})^n \bigr\rfloor\qquad (n=0,1,\ldots ),\eqno(4)$$ and so $$J_3(n)=3n+1-\bigl\lfloor K(3)\bigl({3\over 2}\bigr)^{\lceil{\, \log_{3\over 2}{({{2n+1}\over {K(3)}})}}\rceil}\bigr\rfloor\qquad (n=0,1,\ldots ).\eqno(5)$$ Here the constant is $K(3)=1.62227\, 05028\, 84767\, 31595\, 69509\, 82899\, 32411\ldots $. \vskip 10pt \centerline{\bf 3. Proofs} \vskip 4pt We begin by proving a little more than is necessary for theorem 1 above. Fix $\alpha >1$, and let $f(x)=\lceil{\alpha x}\rceil$. We study the iterates $f_n=f_n(\alpha )$ of $f$, defined by $$f_{n+1}=f(f_n)=\lceil{\alpha f_n}\rceil\qquad (n\ge 0;\, f_0=1).\eqno(6)$$ \proclaim Proposition 1. There exists a constant $c=c(\alpha )$ such that $$f_n(\alpha )\sim c(\alpha )\alpha^n\qquad (n\to\infty).\eqno(7)$$ \noindent {\bf Proof.} Define $$u_n=f_n/\alpha^n.\eqno(8)$$ We claim that $\{u_n\}$ is increasing and bounded from above. It increases because $$\alpha^{n+1}u_{n+1}=\lceil{\alpha^{n+1}u_n}\rceil\ge \alpha^{n+1}u_n,$$ and is bounded from above because $$\alpha^{n+1}u_{n+1}=\lceil{\alpha^{n+1}u_n}\rceil\le 1+\alpha^{n+1}u_n$$ implies that $$u_{n+1}\le u_n+\alpha^{-n-1}\qquad (n\ge 0),$$ which in turn implies that $u_n\le \alpha /(\alpha -1)$ for all $n\ge 0$. \vrl We now study the error term in the asymptotic formula (7). The next proposition shows that the error is very small in many cases. \proclaim Proposition 2. If $\alpha \ge 2$ or if $\alpha =2-1/m$ for integer $m\ge 2$, then $$\forall n\ge 0: f_n=\lfloor{c(\alpha )\alpha^n}\rfloor .$$ \noindent {\bf Proof.} We define numbers $\{e_n\}$ by $$f_n=\alpha f_{n-1}+e_n=\lceil{\alpha f_{n-1}}\rceil\qquad (n\ge 1),\eqno(9)$$ so $0\le e_n<1$. With the $u_n$ of (8) above, we have $$f_n=u_n\alpha^n=\alpha u_{n-1}\alpha^{n-1}+e_n=u_{n-1}\alpha^n+e_n,$$ from which $u_n=u_{n-1}+e_n/\alpha^n$ and $$u_n=1+\sum_{k=1}^n{{e_k}\over {\alpha^k}}\longrightarrow c(\alpha )=1+\sum_{k=1}^{\infty}{{e_k}\over {\alpha^k}}.$$ It follows that $$f_n=c(\alpha )\alpha^n-\sum_{j\ge 1}{{e_{n+j}}\over {\alpha^j}},\eqno(10)$$ and that $$|f_n-c(\alpha )\alpha^n|\le \sum_{j\ge 1}{1\over {\alpha^j}}={1\over {\alpha -1}}.$$ Thus $0\le c(\alpha )\alpha^n-f_n\le 1/(\alpha -1)$ for all $n$, and if $\alpha >2$ the result follows. If $\alpha =2$ the result is trivial. Finally, if $\alpha $ is rational we can bound the $e_n$'s away from 1 and extend the result slightly. Indeed, suppose $\alpha =2-1/m$ for integer $m\ge 2$. Then (9) shows that all $|e_n|\le (m-1)/m$, and (10) yields $$|f_n-c(\alpha )\alpha^n|\le {{m-1}\over m}{1\over {\alpha -1}}=1.$$ However it cannot happen that all $e_n=(m-1)/m$ for $n>n_0$, for otherwise we would have $f_n=c(\alpha )(2-1/m)^n-1$, but the right side cannot be an integer for all $n>n_0$, completing the proof. \vrl To finish the proof of theorem 1 we return to the parameter values that occur in the Josephus problem. Let $\alpha =q/(q-1)$ and write $K(q)$ for $c(\alpha )$ in (5), to find that $$D_n^{(q)}=K(q)\bigl({q\over {q-1}}\bigr)^n-\sum_{j\ge 1}e_{n+j}\bigl({{q-1}\over q}\bigr)^n.$$ Now from (9), $$e_n=\bigl\lceil\bigl({q\over {q-1}}\bigr)D_{n-1}^{(q)}\bigr\rceil -\bigl({q\over {q-1}}\bigr)D_{n-1}^{(q)}$$ and so $(q-1)e_n$ is an integer in the range $[-(q-2),0]$. The estimate (3) of theorem 1 now follows, and the proof is complete. \vrl \vskip 10pt \centerline{\bf 4. The function $c(\alpha )$.} In this section we study the `constant' $c(\alpha )$, as a function of $\alpha$. A brief table of $c(\alpha )$, showing some of its irregular behavior, is below. $$\matrix{\alpha&c(\alpha )\cr \hfil &\hfil\cr 1.050000\hfil &\hfil \, 11.83541649...\cr 1.100000\hfil &\hfil 6.1922534...\cr 1.103831\hfil &\hfil 6.3948499...\cr 1.108731\hfil &\hfil 6.0491335...\cr 1.110087\hfil &\hfil 5.7834036...\cr 1.110631\hfil &\hfil 5.7299817...\cr 1.111891\hfil &\hfil 6.1263971...\cr 1.250000\hfil &\hfil 2.0763957...\cr 1.500000\hfil &\hfil 1.6222705...\cr 1.900000\hfil &\hfil 1.2701620...\cr 2.000000\hfil &\hfil 1.0000000...\cr 2.001000\hfil &\hfil 1.9908393...\cr 2.500000\hfil &\hfil 1.3653870...\cr 5.500000\hfil &\hfil 1.1311946...\cr}$$ \vskip 6pt A graph of $c(\alpha )$, for $1.1 <\alpha <2.5$ is shown in Fig. 1. \vskip 6pt \centerline {Figure 1 goes here} \vskip 6pt \centerline{\bf Fig. 1: $c(\alpha )$ vs. $\alpha $.} \vskip 6pt It is easy to see that at the integers the function $c(\alpha )$ has jump discontinuities of the following kind: $$c(m+0)=c(m)+{1\over {m-1}}=1+{1\over {m-1}}\qquad (m=2,3,\ldots ).$$ We are also able to make a quantitative statement about the jumps at the Josephus points, as the following proposition shows. \proclaim Proposition 3. At the Josephus points $\alpha_q=q/(q-1)$, the function $c(\alpha )$ has jump discontinuities also, and they are of the form $$c(\alpha +0)=\alpha c(\alpha )\qquad (\alpha =2,\, 3/2,\, 4/3,\, 5/4,\, \ldots ).\eqno(11)$$ \noindent{\bf Proof.} We claim that at such a value of $\alpha $ the sequences $\{f_n(\alpha )\}$ and $\{f_n(\alpha +0)\}$ are related by $$f_n(\alpha )=f_{n-1}(\alpha +0)+1\qquad (n\ge 1),\eqno(12)$$ which would establish the truth of the proposition. To prove (12), it suffices to show that $$\bigl\lceil{(\alpha +\epsilon )(f_n(\alpha )-1)}\bigr\rceil =f_{n+1}(\alpha )-1,$$ for each $n\ge 1$ and all small enough $\epsilon $. But the left side is $$\eqalign{\bigl\lceil{\alpha f_n(\alpha )-\alpha +\epsilon f_n(\alpha)-\epsilon }\bigr\rceil &=\bigl\lceil{\alpha f_n(\alpha )-1+(1-\alpha -\epsilon )+\epsilon f_n(\alpha )}\bigr\rceil\cr &=\bigl\lceil{\alpha f_n(\alpha )+\epsilon f_n(\alpha )-(\epsilon + {1\over {q-1}})}\bigr\rceil -1\cr &=\biggl\lceil{{q\over {q-1}}f_n(\alpha )+\epsilon f_n(\alpha )-(\epsilon +{1\over {q-1}})}\biggr\rceil -1.\cr}$$ Suppose $(q-1)\backslash f_n(\alpha )$. Then the last member above is $(q/(q-1))f_n(\alpha )-1$, i.e., it is $f_{n+1}(\alpha )-1$, as required. Next suppose that $f_n(\alpha )\equiv 1\pmod{(q-1)}$. Then $${q\over {q-1}}f_n(\alpha )=m+{1\over {q-1}},$$ say, and the last member above is $$\biggl\lceil{m+{1\over {q-1}}+\epsilon (f_n(\alpha )-1)-{1\over {q-1}}}\biggr\rceil -1=m=\lceil{q/(q-1)f_n(\alpha )}\rceil -1=f_{n+1}(\alpha )-1.$$ A similar easy calculation handles all of the other residue classes simultaneously. \vrl \vskip 10pt \centerline{\bf 5. Remarks, and a conjecture} \vskip 4pt We must remark that as it stands, our `explicit' formula for $J_3(n)$ is not an improvement over the algorithm in (1), because the computation of the universal constant $K(3)$ requires the $D_n$'s of (1). This situation could change if some independent method were found to calculate $K(3)$ with high precision. We would like to know more about the function $c(\alpha )$. 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)? Finally, we have a conjecture about the error in the general asymptotic formulas above. In the Josephus case, where $\alpha =q/(q-1)$, we conjecture that the numbers $(q-1)e_n$, which assume only the values $0,1,\ldots ,q-2$, in fact are asymptotically uniformly distributed on those $q-1$ values. This would imply that if $q\ge 2$, $$\eqalign{&\lim_{n\to\infty}Prob\biggl\{D_n^{(q)}-\biggl\{ K(q)\bigl({q\over {q-1}}\bigr)^n-{{(q-2)}\over {2}}\biggr\}\le t\sqrt{{{q(q-2)}\over {12(2q-1)}}}\,\, \biggr\}\cr &\qquad\qquad ={1\over {\sqrt{2\pi }}}\int_{-\infty}^te^{-y^2/2}dy.\cr}$$ The conjecture seems similar to asking for a proof that a given real number is normal in a given base, and so it is likely to be very difficult to prove. \vskip 12pt \centerline{\bf References} \vskip 10pt {\parindent 10pt \parskip 0pt \frenchspacing \item{1.} Ahrens, Wilhelm E. M. G., Mathematische Unterhaltungen und Spiele, Teubner: Leipzig, 1918, 118-169. \item{2.} Aulicino, D. J., and Goldfield, Morris, A new relation between primitive roots and permutations, {\it Amer. Math. Monthly} {\bf 76} (1969), 664-666. \item{3.} R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, New York, 1989. \item{4.} I. N. Herstein and I. Kaplansky, Matters mathematical, Chelsea, New York, 1978 (pp. 121-128). \item{5.} F. Jakobczyk, On the generalized Josephus problem, {\it Glasgow Math. J.} {\bf 14} (1973), 168-173. \item{6.} Knuth, Donald E., The Art of Computer Programming, Addison-Wesley, New York; Vol. I, 2nd Ed. (1973), Ex. 1.3.2.22, and Vol. III (1975), Ex. 5.1.1.2. \item{7.} Errol L. Lloyd, An $O(n\log{m})$ algorithm for the Josephus problem, {\it J. Algorithms} {\bf 4} (1983), 262-270. \item{8.} MacFhraing, Rob Alasdair (R. A. Rankin), Aireamh muinntir Fhinn is Dhubhain, agus sgeul Iosephuis is an d\` a fhichead Iudhaich (The numbering of Fionn's and Dubhan's men, and the story of Josephus and the forty Jews), {\it Proc. Royal Irish Acad.} Sect. A {\bf 52} (1948), 87-93 (Gaelic. English summary; MR {\bf 10} (1949), 509). \item{9.} W. J. Robinson, The Josephus problem, {\it Math. Gaz.} {\bf 44} (1960), 47-52. \item{10.} D. Woodhouse, The extended Josephus problem, {\it Rev. Mat. Hisp.-Amer.} Ser. 4 {\bf 31} (1973), 207-218. } \end