login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 11
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; text; 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

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..10000

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] (* Robert G. Wilson v, Jul 31 2010 *)

Table[Nest[Rest@RotateLeft[#, 2] &, Range[n], n - 1], {n, 72}] // Flatten (* Arkadiusz Wesolowski, Jan 14 2013 *)

CROSSREFS

Cf. A032434, A005427, A005428, A006257, A007495, A000960, A056530.

A181281 with s=5. - Paul Weisenhorn, Oct 10 2010

Sequence in context: A129721 A268193 A238606 * A018219 A174714 A116633

Adjacent sequences:  A054992 A054993 A054994 * A054996 A054997 A054998

KEYWORD

nonn

AUTHOR

John W. Layman, May 30 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 27 21:39 EDT 2017. Contains 288804 sequences.