cp's OEIS Frontend

A032434 Triangle read by rows: last survivors of Josephus elimination process.

%I A032434 #74 Feb 16 2025 08:32:36
%S A032434 1,2,1,3,3,2,4,1,1,2,5,3,4,1,2,6,5,1,5,1,4,7,7,4,2,6,3,5,8,1,7,6,3,1,
%T A032434 4,4,9,3,1,1,8,7,2,3,8,10,5,4,5,3,3,9,1,7,8,11,7,7,9,8,9,5,9,5,7,7,12,
%U A032434 9,10,1,1,3,12,5,2,5,6,11,13,11,13,5,6,9,6,13,11,2,4,10,8,14,13,2,9
%N A032434 Triangle read by rows: last survivors of Josephus elimination process.
%C A032434 T(n,k) is the surviving integer under the following elimination process. Arrange 1, 2, 3, ..., n in a circle, increasing clockwise. Starting with i = 1, delete the integer k - 1 places clockwise from i. Repeat, counting k - 1 places from the next undeleted integer, until only one integer remains. [After _John W. Layman_]
%C A032434 From _Gerhard Kirchner_, Jan 08 2017: (Start)
%C A032434 The fast recurrence is useful for large n, if single values of T(n,k) are to be determined (not the whole sequence). The number of steps is about log(n)/log(n/(k/(k-1))) instead of n, i.e., many basic steps are bypassed by a shortcut.
%C A032434 Example: For computing T(10^80, 7), about 1200 steps are needed, done in a second, whereas even the age of the universe would not be sufficient for the basic recurrence. Deduction of the fast recurrence and the reason for its efficiency: See the link "Fast recurrence". (End)
%D A032434 W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987, see pp. 32-36.
%D A032434 M. Kraitchik, "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.
%H A032434 T. D. Noe, <a href="/A032434/b032434.txt">Rows n = 1..50, flattened</a>
%H A032434 Philippe Dumas, <a href="https://hal.inria.fr/inria-00074743">Algebraic aspects of B-regular series</a>, inria-00074743, 1993.
%H A032434 Philippe Dumas, <a href="https://doi.org/10.1007/3-540-56939-1_94">Algebraic aspects of B-regular series</a>,  in: A. Lingas, R. Karlsson, S. Carlsson S. (eds), Automata, Languages and Programming, ICALP 1993 (Lecture Notes in Computer Science, vol 700, Springer, Berlin, Heidelberg), pp. 457-468, 1993.
%H A032434 L. Halbeisen and N. Hungerbühler, <a href="https://citeseerx.ist.psu.edu/pdf/2d9d1f1689fcf6457883400a67d2e139e8d37312">The Josephus Problem</a>, preprint, 1997.
%H A032434 L. Halbeisen and N. Hungerbühler, <a href="http://user.math.uzh.ch/halbeisen/publications/pdf/jos.pdf">The Josephus Problem</a>, preprint, 1997.
%H A032434 L. Halbeisen and N. Hungerbühler, <a href="https://jtnb.centre-mersenne.org/item/JTNB_1997__9_2_303_0">The Josephus Problem</a>, Journal de Théorie des Nombres de Bordeaux 9 (1997), 303-318.
%H A032434 Gerhard Kirchner, <a href="/A032434/a032434.txt">Fast recurrence</a>.
%H A032434 A. M. Odlyzko and H. S. Wilf, <a href="/A032434/a032434.pdf">Functional iteration and the Josephus problem</a>, preprint, 1991. [Cached copy, with permission]
%H A032434 A. M. Odlyzko and H. S. Wilf, <a href="http://dx.doi.org/10.1017/S0017089500008272">Functional iteration and the Josephus problem</a>, Glasgow Math. J. 33 (1991), 235-240.
%H A032434 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>.
%H A032434 Wikipedia, <a href="https://en.wikipedia.org/wiki/Josephus_problem">Josephus problem</a>.
%H A032434 <a href="/index/J#nome">Index entries for sequences related to the Josephus problem</a>
%F A032434 Recurrence: T(1, k) = 1, T(n, k) = (T(n-1, k) + k) mod n if this is nonzero and n if not.
%F A032434 From _Gerhard Kirchner_, Jan 08 2017: (Start)
%F A032434 The same recurrence without these conditions:
%F A032434 T(1, k) = 1,  T(n, k) = 1 + (T(n-1, k) + k - 1) mod n.
%F A032434 This "basic" recurrence is used in the following:
%F A032434 Fast recurrence (n >= k):
%F A032434 z(1) = 1, r(1) = 1,
%F A032434 if z(m) < k-1 then
%F A032434   z(m+1) = z(m) + 1,
%F A032434   r(m+1) = 1 + (r(m)+k-1) mod z(m+1) (basic recurrence),
%F A032434 else
%F A032434   e(m) = -z(m) mod (k-1),
%F A032434   if r(m) + e(m) <= 0 then e(m) -> e(m) + k - 1,
%F A032434   z(m+1) = z(m) + (z(m) + e(m))/(k-1),
%F A032434   r(m+1) = r(m) + e(m).
%F A032434 Result for m = M with z(M) <= n < z(M+1):
%F A032434 T(n,k) = r(M) + k(n - z(M)). (End)
%F A032434 From _Gerhard Kirchner_, Jan 12 2017: (Start)
%F A032434 Another fast (and shorter) recurrence is given in "Functional iteration and the Josephus problem", p. 1, (see link):
%F A032434 D(m,k) = ceiling(k/(k-1)*D(m-1,k)), m >= 1; D(0,k)=1.
%F A032434 Result for m with D(m-1,k) <= (k-1)*n < D(m,k):
%F A032434 T(n,k) = k*n + 1 - D(m,k). (End)
%e A032434 Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins
%e A032434   1;
%e A032434   2, 1;
%e A032434   3, 3, 2;
%e A032434   4, 1, 1, 2;
%e A032434   5, 3, 4, 1, 2;
%e A032434   6, 5, 1, 5, 1, 4;
%e A032434   7, 7, 4, 2, 6, 3, 5;
%e A032434   ...
%e A032434 Fast recurrence for n = 7 and k = 3:
%e A032434 m =    1 2 3 4 5 6,
%e A032434 z(m) = 1 2 3 4 6 9,
%e A032434 r(m) = 1 2 2 1 1,
%e A032434 z(6) > n => M = 5.
%e A032434 Result: T(7,3) = r(5) + 3*(n - z(5)) = 4.
%t A032434 t[1, k_] = 1; t[n_, k_] := t[n, k] = If[m = Mod[t[n-1, k] + k, n]; m != 0, m, n]; Flatten[ Table[ t[n, k], {n, 1, 14}, {k, 1, n}]] (* _Jean-François Alcover_, Sep 25 2012 *)
%o A032434 (PARI) T(n,k)=local(t): if(n<2,n>0,t=(T(n-1,k)+k)%n: if(t,t,n))
%Y A032434 Cf. A032435, A032436, A321781.
%Y A032434 Second column is A006257, third column is A054995. Diagonal T(n, n) is A007495.
%K A032434 nonn,tabl,nice
%O A032434 1,2
%A A032434 _N. J. A. Sloane_
%E A032434 Edited by _Ralf Stephan_, May 18 2004