|
| |
|
|
A032434
|
|
Triangle read by rows: last survivors of Josephus elimination process.
|
|
14
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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]
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)
|
|
|
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
|
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, Journal de Théorie des Nombres de Bordeaux 9 (1997), 303-318.
|
|
|
FORMULA
|
Recurrence: T(1, k) = 1, T(n, k) = (T(n-1, k) + k) mod n if this is nonzero and n if not.
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)
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)
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
PROG
|
(PARI) T(n, k)=local(t): if(n<2, n>0, t=(T(n-1, k)+k)%n: if(t, t, n))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
