|
Search: id:A032434
|
|
|
| A032434 |
|
Triangle read by rows: last survivors of Josephus elimination process. |
|
+0
8
|
|
| 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; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.
|
|
REFERENCES
|
Ball, W. W. R. and Coxeter, H. S. M., Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 32-36, 1987.
Kraitchik, M. "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W.W. Norton, pp. 93-94, 1942.
Odlyzko, A. M. and Wilf, H. S. "Functional Iteration and the Josephus Problem." Glasgow Math. J. 33, 235-240, 1991.
|
|
LINKS
|
T. D. Noe, Rows n=1..50, flattened
Ph. Dumas, Algebraic aspects of B-regular 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, Link to a section of The World of Mathematics.
|
|
FORMULA
|
Recurrence: T(1, k) = 1, T(n, k) = [T(n-1, 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
|
|
PROGRAM
|
(PARI) T(n, k)=local(t): if(n<2, n>0, t=(T(n-1, 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 this_sequence A002347 A006642 A094435
Adjacent sequences: A032431 A032432 A032433 this_sequence A032435 A032436 A032437
|
|
KEYWORD
|
nonn,tabl,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
Edited by Ralf Stephan (ralf(AT)ark.in-berlin.de), May 18 2004
|
|
|
Search completed in 0.002 seconds
|
