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.
LINKS
Arkadiusz Wesolowski, Table of n, a(n) for n = 1..10000
R. Baumann, Das Josephus-Problem, LOG IN, Heft Nr. 165, pp. 70-71, 2010 (in German).
Ph. Dumas, Algebraic aspects of B-regular series. [Broken link]
Philippe Dumas, Algebraic aspects of B-regular series, Research Report, RR-1931, INRIA, 1993.
Ph. Dumas, Algebraic aspects of B-regular series, in: International Colloquium on Automata, Languages and Programming, ICALP 1993 (A. Lingas, R. Karlsson, S. Carlsson, eds.), pp. 457-468, Lecture Notes in Computer Science, vol. 700, Springer, Berlin, 1993.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, J. Théor. Nombres Bordeaux 9 (1997), no. 2, 303-318.
Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991.
FORMULA
a(n) = 3*n + 1 - floor(K(3)*(3/2)^(ceiling(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
KEYWORD
nonn
AUTHOR
John W. Layman, May 30 2000
STATUS
approved