|
%I #71 Jan 25 2022 01:48:05
%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/viewdoc/summary?doi=10.1.1.34.4643">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
|
