|
Search: id:A054995
|
|
|
| A054995 |
|
A version of Josephus problem: a(n) 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 two places clockwise from i. Repeat, counting two places from the next undeleted integer, until only one integer remains. |
|
+0
6
|
|
| 1, 2, 2, 1, 4, 1, 4, 7, 1, 4, 7, 10, 13, 2, 5, 8, 11, 14, 17, 20, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 1, 4, 7, 10, 13, 16, 19, 22, 25
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
If one counts only one place (rather than two) at each stage to determine the element to be deleted, the Josephus survivors (A006257) are obtained.
|
|
REFERENCES
|
Odlyzko, A. M. and Wilf, H. S. "Functional Iteration and the Josephus Problem." Glasgow Math. J. 33, 235-240, 1991.
|
|
LINKS
|
Ph. Dumas, Algebraic aspects of B-regular series
L. Halbeisen, The Josephus Problem
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem
|
|
FORMULA
|
a(n)=3*n+1-floor(K(3)*(3/2)^(ceil(log((2*n+1)/K(3))/log(3/2)))) where K(3)=(3/2)*K=1.622270502884767... (K is the constant described in A061419); a(n)=3n+1-A061419(k+1) where A061419(k+1) is the least integer such that A061419(k+1)>2n.
a(1)=1 and, for n>1, a(n) = (a(n-1)+3) mod n, if this value is nonzero, n otherwise.
|
|
EXAMPLE
|
a(5)=4 because the elimination process gives (1^,2,3,4,5) -> (1,2,4^,5) -> (2^,4,5) -> (2^,4) -> (4), where ^ denotes the counting reference position.
|
|
CROSSREFS
|
Cf. A032434, A005427, A005428, A006257, A007495, A000960, A056530.
Sequence in context: A061298 A002126 A129721 this_sequence A018219 A116633 A134666
Adjacent sequences: A054992 A054993 A054994 this_sequence A054996 A054997 A054998
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
John W. Layman (layman(AT)math.vt.edu), May 30 2000
|
|
|
Search completed in 0.002 seconds
|
