|
%I #49 Jan 19 2023 09:35:09
%S 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,
%T 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,
%U 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
%N 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.
%C 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.
%H Arkadiusz Wesolowski, <a href="/A054995/b054995.txt">Table of n, a(n) for n = 1..10000</a>
%H R. Baumann, <a href="https://www.yumpu.com/de/document/read/460296/nr-165">Das Josephus-Problem</a>, LOG IN, Heft Nr. 165, pp. 70-71, 2010 (in German).
%H Ph. Dumas, <a href="http://algo.inria.fr/dumas/Dumas93a/Gif/">Algebraic aspects of B-regular series</a>. [Broken link]
%H Philippe Dumas, <a href="https://hal.inria.fr/inria-00074743">Algebraic aspects of B-regular series</a>, Research Report, RR-1931, INRIA, 1993.
%H Ph. Dumas, <a href="https://doi.org/10.1007/3-540-56939-1_94">Algebraic aspects of B-regular series</a>, 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.
%H L. Halbeisen and N. Hungerbühler, <a href="http://www.numdam.org/item/JTNB_1997__9_2_303_0">The Josephus Problem</a>, J. Théor. Nombres Bordeaux 9 (1997), no. 2, 303-318.
%H Alasdair MacFhraing, <a href="https://www.jstor.org/stable/20488493">Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich</a>, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
%H A. M. Odlyzko and H. S. Wilf, <a href="https://doi.org/10.1017/S0017089500008272">Functional iteration and the Josephus problem</a>, Glasgow Math. J. 33, 235-240, 1991.
%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F 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.
%F a(1) = 1 and, for n > 1, a(n) = (a(n-1) + 3) mod n, if this value is nonzero, n otherwise.
%F a(n) = (a(n-1) + 2) mod n + 1. - _Paul Weisenhorn_, Oct 10 2010
%e 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.
%e a(13) = 13 => a(14) = (a(13) + 2) mod 14 + 1 = 2. - _Paul Weisenhorn_, Oct 10 2010
%t (* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, 3]; Array[f, 70] (* _Robert G. Wilson v_, Jul 31 2010 *)
%t Table[Nest[Rest@RotateLeft[#, 2] &, Range[n], n - 1], {n, 72}] // Flatten (* _Arkadiusz Wesolowski_, Jan 14 2013 *)
%Y Cf. A032434, A005427, A005428, A006257, A007495, A000960, A056530.
%Y Cf. A181281 (with s=5). - _Paul Weisenhorn_, Oct 10 2010
%K nonn
%O 1,2
%A _John W. Layman_, May 30 2000
|
