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

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, 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, 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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• tabl
• nice

Comments

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]

From Gerhard Kirchner, Jan 08 2017: (Start)

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.

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)

Examples

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins
  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;
  ...
Fast recurrence for n = 7 and k = 3:
m =    1 2 3 4 5 6,
z(m) = 1 2 3 4 6 9,
r(m) = 1 2 2 1 1,
z(6) > n => M = 5.
Result: T(7,3) = r(5) + 3*(n - z(5)) = 4.
		

References

• W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987, see pp. 32-36.
• M. Kraitchik, "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.

Links

• T. D. Noe, Rows n = 1..50, flattened
• Philippe Dumas, Algebraic aspects of B-regular series, inria-00074743, 1993.
• Philippe Dumas, Algebraic aspects of B-regular series, 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.
• L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
• L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
• L. Halbeisen and N. Hungerbühler, The Josephus Problem, Journal de Théorie des Nombres de Bordeaux 9 (1997), 303-318.
• Gerhard Kirchner, Fast recurrence.
• A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, preprint, 1991. [Cached copy, with permission]
• A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
• Eric Weisstein's World of Mathematics, Josephus Problem.
• Wikipedia, Josephus problem.
• Index entries for sequences related to the Josephus problem

Crossrefs

Cf. A032435, A032436, A321781.

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

Programs

Mathematica

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 *)

PARI

T(n,k)=local(t): if(n<2,n>0,t=(T(n-1,k)+k)%n: if(t,t,n))

Formula

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

From Gerhard Kirchner, Jan 08 2017: (Start)

The same recurrence without these conditions:

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

This "basic" recurrence is used in the following:

Fast recurrence (n >= k):

z(1) = 1, r(1) = 1,

if z(m) < k-1 then

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

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

else

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

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

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

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

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

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

From Gerhard Kirchner, Jan 12 2017: (Start)

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

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

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

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

Extensions

Edited by Ralf Stephan, May 18 2004