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

%I #73 Aug 06 2024 08:45:47

%S 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 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 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 Triangle read by rows: last survivors of Josephus elimination process.

%C 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 From _Gerhard Kirchner_, Jan 08 2017: (Start)

%C 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 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 W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987, see pp. 32-36.

%D M. Kraitchik, "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.

%H T. D. Noe, <a href="/A032434/b032434.txt">Rows n = 1..50, flattened</a>

%H Philippe Dumas, <a href="https://hal.inria.fr/inria-00074743">Algebraic aspects of B-regular series</a>, inria-00074743, 1993.

%H 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 L. Halbeisen and N. Hungerbühler, <a href="https://citeseerx.ist.psu.edu/pdf/2d9d1f1689fcf6457883400a67d2e139e8d37312">The Josephus Problem</a>, preprint, 1997.

%H 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 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 Gerhard Kirchner, <a href="/A032434/a032434.txt">Fast recurrence</a>.

%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/JosephusProblem.html">Josephus Problem</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Josephus_problem">Josephus problem</a>.

%H <a href="/index/J#nome">Index entries for sequences related to the Josephus problem</a>

%F Recurrence: T(1, k) = 1, T(n, k) = (T(n-1, k) + k) mod n if this is nonzero and n if not.

%F From _Gerhard Kirchner_, Jan 08 2017: (Start)

%F The same recurrence without these conditions:

%F T(1, k) = 1, T(n, k) = 1 + (T(n-1, k) + k - 1) mod n.

%F This "basic" recurrence is used in the following:

%F Fast recurrence (n >= k):

%F z(1) = 1, r(1) = 1,

%F if z(m) < k-1 then

%F z(m+1) = z(m) + 1,

%F r(m+1) = 1 + (r(m)+k-1) mod z(m+1) (basic recurrence),

%F else

%F e(m) = -z(m) mod (k-1),

%F if r(m) + e(m) <= 0 then e(m) -> e(m) + k - 1,

%F z(m+1) = z(m) + (z(m) + e(m))/(k-1),

%F r(m+1) = r(m) + e(m).

%F Result for m = M with z(M) <= n < z(M+1):

%F T(n,k) = r(M) + k(n - z(M)). (End)

%F From _Gerhard Kirchner_, Jan 12 2017: (Start)

%F Another fast (and shorter) recurrence is given in "Functional iteration and the Josephus problem", p. 1, (see link):

%F D(m,k) = ceiling(k/(k-1)*D(m-1,k)), m >= 1; D(0,k)=1.

%F Result for m with D(m-1,k) <= (k-1)*n < D(m,k):

%F T(n,k) = k*n + 1 - D(m,k). (End)

%e Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins

%e 1;

%e 2, 1;

%e 3, 3, 2;

%e 4, 1, 1, 2;

%e 5, 3, 4, 1, 2;

%e 6, 5, 1, 5, 1, 4;

%e 7, 7, 4, 2, 6, 3, 5;

%e ...

%e Fast recurrence for n = 7 and k = 3:

%e m = 1 2 3 4 5 6,

%e z(m) = 1 2 3 4 6 9,

%e r(m) = 1 2 2 1 1,

%e z(6) > n => M = 5.

%e Result: T(7,3) = r(5) + 3*(n - z(5)) = 4.

%t 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 (PARI) T(n,k)=local(t): if(n<2,n>0,t=(T(n-1,k)+k)%n: if(t,t,n))

%Y Cf. A032435, A032436, A321781.

%Y Second column is A006257, third column is A054995. Diagonal T(n, n) is A007495.

%K nonn,tabl,nice

%O 1,2

%A _N. J. A. Sloane_

%E Edited by _Ralf Stephan_, May 18 2004