

A032434


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


11



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 k1 places clockwise from i. Repeat, counting k1 places from the next undeleted integer, until only one integer remains.  After John W. Layman.


REFERENCES

Ball, W. W. R. and Coxeter, H. S. M., Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 3236, 1987.
Kraitchik, M. "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W.W. Norton, pp. 9394, 1942.
Odlyzko, A. M. and Wilf, H. S. "Functional Iteration and the Josephus Problem." Glasgow Math. J. 33, 235240, 1991.


LINKS

T. D. Noe, Rows n=1..50, flattened
Ph. Dumas, Algebraic aspects of Bregular series
L. Halbeisen, The Josephus Problem
L. Halbeisen and N. Hungerbuehler, The Josephus Problem
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem
Eric Weisstein's World of Mathematics, Josephus Problem.


FORMULA

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


EXAMPLE

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


MATHEMATICA

t[1, k_] = 1; t[n_, k_] := t[n, k] = If[m = Mod[t[n1, k] + k, n]; m != 0, m, n]; Flatten[ Table[ t[n, k], {n, 1, 14}, {k, 1, n}]] (* JeanFrançois Alcover, Sep 25 2012 *)


PROG

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


CROSSREFS

Cf. A032435, A032436. Second column is A006257, third column is A054995. Diagonal T(n, n) is A007495.
Sequence in context: A102746 A123143 A128133 * A002347 A006642 A210595
Adjacent sequences: A032431 A032432 A032433 * A032435 A032436 A032437


KEYWORD

nonn,tabl,nice


AUTHOR

N. J. A. Sloane.


EXTENSIONS

Edited by Ralf Stephan, May 18 2004


STATUS

approved



