|
| |
|
|
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.
|
|
8
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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.
a(n) = (a(n-1)+2) mod n +1. - Paul Weisenhorn, Oct 10 2010
|
|
|
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.
a(13) = 13 => a(14) = (a(13)+2) mod 14 +1 = 2. - Paul Weisenhorn, Oct 10 2010
|
|
|
MATHEMATICA
| (* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, 3]; Array[f, 70] [From Robert G. Wilson v, Jul 31 2010]
|
|
|
CROSSREFS
| Cf. A032434, A005427, A005428, A006257, A007495, A000960, A056530.
A181281 with s=5. - Paul Weisenhorn, Oct 10 2010
Sequence in context: A061298 A002126 A129721 * A018219 A174714 A116633
Adjacent sequences: A054992 A054993 A054994 * A054996 A054997 A054998
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| John W. Layman (layman(AT)math.vt.edu), May 30 2000
|
| |
|
|
