|
%I M3759 #113 Aug 07 2023 03:54:57
%S 5,7,9,12,16,22,29,39,52,69,92,123,164,218,291,388,517,690,920,1226,
%T 1635,2180,2907,3876,5168,6890,9187,12249,16332,21776,29035,38713,
%U 51618,68824,91765,122353,163138,217517,290023,386697,515596,687461,916615,1222153,1629538,2172717,2896956,3862608,5150144,6866859,9155812,12207749,16276999,21702665,28936887,38582516,51443354
%N Josephus problem: numbers m such that, when m people are arranged on a circle and numbered 1 through m, the final survivor when we remove every 4th person is one of the first three people.
%C Is this the same as A072493 with its first 8 terms removed? See also the similar conjecture concerning A005428 and A073941.
%C From _Petros Hadjicostas_, Jul 20 2020: (Start)
%C We describe the counting-off game of Burde (1987) using language from Schuh (1968). Suppose m people are labeled with the numbers 1 through m (say clockwise). (Burde uses the numbers 0 through m-1 probably because he relates this problem to the representation of m in the fractional base k/(k-1) = 4/3. He actually modifies the (4/3)-representation of m to include negative coefficients. See the coefficients f(n;k) below.)
%C Suppose we start the counting at the person labeled 1, and we remove every 4th person. This sequence gives those numbers m for which the last survivor is one of the first three people.
%C When m = 5, 9, 12, 16, 218, 517, ... the last survivor is the first person.
%C When m = 7, 29, 69, 92, 291, 388, ... the last survivor is the second person.
%C When m = 22, 39, 52, 123, 164, 690, ... the last survivor is the third person.
%C If we know m = a(n) and the number, say i(n), of the last survivor (when there are a(n) people on the circle), we may find a(n+1) and the number i(n+1) of the new last survivor (when there are a(n+1) people on the circle) in the following way:
%C (a) If 0 = a(n) mod 3, then a(n+1) = (4/3)*a(n), and i(n+1) = i(n).
%C (b) If 1 = a(n) mod 3 and i(n) = 1, then a(n+1) = ceiling((4/3)*a(n)) and i(n+1) = 3.
%C (c) If 1 = a(n) mod 3 and i(n) = 2, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 1.
%C (d) If 1 = a(n) mod 3 and i(n) = 3, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 2.
%C (e) If 2 = a(n) mod 3 and i(n) = 1, then a(n+1) = ceiling((4/3)*a(n)) and i(n+1) = 2.
%C (f) If 2 = a(n) mod 3 and i(n) = 2, then a(n+1) = ceiling((4/3)*a(n)) and i(n+1) = 3.
%C (g) If 2 = a(n) mod 3 and i(n) = 3, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 1. (End)
%C From _Petros Hadjicostas_, Jul 22 2020: (Start)
%C In general, for k >= 2, it seems that when m people are placed on a circle, labeled 1 through m, and every k-th person is removed (starting the counting at person 1), we may determine those m for which the last survivor is in {1, 2, ..., k-1} in the following way.
%C Define the sequence (T(n;k): n >= 1) by T(n;k) = ceiling(Sum_{s=1..n-1} T(s;k)/(k-1)) for n >= 2 starting with T(1; k) = 1. Then the list of those m's for which the last survivor is in {1, 2, ..., k-1} consists of all the numbers T(n;k) >= k (thus, we exclude the cases m = 1, ..., k-1 that may be repeated more than once in the sequence (T(n;k): n >= 1)).
%C I do not have a general proof of this conjecture though I strongly believe that Schuh's (1968) way of solving the case k = 3 (see pp. 373-375 and 377-379, where he provides two methods of solution) may provide clues for proving the conjecture.
%C We have T(n; k=2) = A011782(n+1), T(n; k=3) = A073941(n), T(n; k=4) = A072493(n), T(n; k=5) = A120160(n), T(n; k=6) = A120170(n), T(n; k=7) = A120178(n), T(n; k=8) = A120186(n), T(n; k=9) = A120194(n), and T(n; k=10) = A120202(n).
%C We also have T(n+1;k) = floor((k/(k-1))*T(n;k)) or ceiling((k/(k-1)*T(n;k)).
%C To identify the last survivor that results when we place T(n; k) people on the circle (with T(n;k) >= k) in the above Josephus problem, we use a modification of Burde's algorithm due to Thériault (2000).
%C We use the following recursions but we start at T(k;k) (rather than at the smallest n for which T(n;k) >= k). Define the sequence (S(n;k): n >= 1) by S(n;k) = T(n+k-1; k) for n >= 1. (It is easy to prove that S(1;k) = T(k;k) = 1.)
%C Define also the sequences (j(n;k): n >= 1) and (f(n;k): n >= 1) by j(1;k) = 1, f(1;k) = 0, f(n+1;k) = ((j(n;k) - S(n;k) - 1) mod (k-1)) + 1 - j(n;k) and j(n+1;k) = j(n;k) + f(n+1;k) for n >= 2.
%C Then for all n s.t. S(n;k) >= k, j(n;k) is the number of the last survivor of the Josephus problem where every k-th person is removed (provided we start the counting at number 1). It will always be the case that j(n;k) is in {1,2,...,k-1}.
%C We actually have S(n+1; k) = (k*S(n;k) + f(n+1;k))/(k-1) for n >= 1.
%C Notice that the Burde-Thériault algorithm is a generalization of Schuh's method. (End)
%D Fred Schuh, The Master Book of Mathematical Recreations, Dover, New York, 1968. [This book is cited in Burde (1987). Table 18, p. 374, is related to a very similar sequence (A073941). Thus, definitely, the counting-off games described in the book are related to a similar counting-off game in Burde (1987).]
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A005427/b005427.txt">Table of n, a(n) for n = 1..1000</a>
%H K. Burde, <a href="http://dx.doi.org/10.1016/0022-314X(87)90078-3">Das Problem der Abzählreime und Zahlentwicklungen mit gebrochenen Basen [The problem of counting rhymes and number expansions with fractional bases]</a>, J. Number Theory 26(2) (1987), 192-209.
%H Nicolas Thériault, <a href="https://pdfs.semanticscholar.org/341d/f5787ba71d62a9e4fb4f7b506351521cbf06.pdf">Generalizations of the Josephus problem</a>, Utilitas Mathematica, 58 (2000), 161-173 (MR1801309).
%H Nicolas Thériault, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.164.2015&rep=rep1&type=pdf">Generalizations of the Josephus problem</a>, Utilitas Mathematica, 58 (2000), 161-173 (MR1801309).
%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%F a(n) = 5 + ceiling(Sum_{k=1..n-1} a(k)/3). - _Petros Hadjicostas_, Jul 21 2020
%e From _Petros Hadjicostas_, Jul 22 2020: (Start)
%e We explain why 5 and 7 are in the sequence but 6 is not.
%e If we put m = 5 people on the circle, label them 1 through 5, start the counting at person 1, and remove every 4th person, then the list of people who are removed is 4 -> 3 -> 5 -> 2. Thus, the last survivor is 1, so m = 5 is included in this sequence.
%e If we put m = 6 people on a circle, label them 1 through 6, start the counting at person 1, and remove every 4th person, then the list of people who are removed is 4 -> 2 -> 1 -> 3 -> 6. Thus, the last survivor is 5 (not 1, 2, or 3), so m = 6 is not included in this sequence.
%e If we put m = 7 people on a circle, label them 1 through 7, start the counting at person 1, and remove every 4th person, then the list of people who are removed is 4 -> 1 -> 6 -> 5 -> 7 -> 3. Thus, the last survivor is 2, so m = 7 is included in this sequence.
%e Strictly speaking, m = 2 and m = 3 should have been included as well (since clearly the last survivor would be 1 or 2 or 3). In addition, m = 4 should have been included as well because the list of people removed is 4 -> 1 -> 3. The case of number 1 does create a problem since there is no survivor. Note that the numbers 1, 2, 3, 4 are all included in A072493. (End)
%t f[s_] := Append[s, Ceiling[5 + Plus@@(s/3)]]; Nest[f, {5}, 100] (* _Vladimir Joseph Stephan Orlovsky_, Jan 08 2011 *)
%o (PARI) /* Gives an n X 2 matrix w s.t. w[,1] are the terms of this sequence and w[,2] are the corresponding numbers of the last survivors (1, 2 or 3). */
%o lista(nn) = {my(w = matrix(nn,2)); w[1,1] = 5; w[1,2] = 1; for(n=1, nn-1,
%o if(0 == w[n,1] % 3, w[n+1,1] = w[n,1]*4/3; w[n+1,2] = w[n,2]);
%o if(1 == w[n,1] % 3 && w[n,2] == 1, w[n+1,1] = ceil(w[n,1]*4/3); w[n+1,2] = w[n,2] + 2);
%o if(1 == w[n,1] % 3 && w[n,2] == 2, w[n+1,1] = floor(w[n,1]*4/3); w[n+1,2] = w[n,2] - 1);
%o if(1 == w[n,1] % 3 && w[n,2] == 3, w[n+1,1] = floor(w[n,1]*4/3); w[n+1,2] = w[n,2] - 1);
%o if(2 == w[n,1] % 3 && w[n,2] == 1, w[n+1,1] = ceil(w[n,1]*4/3); w[n+1,2] = w[n,2] + 1);
%o if(2 == w[n,1] % 3 && w[n,2] == 2, w[n+1,1] = ceil(w[n,1]*4/3); w[n+1,2] = w[n,2] + 1);
%o if(2 == w[n,1] % 3 && w[n,2] == 3, w[n+1,1] = floor(w[n,1]*4/3); w[n+1,2] = w[n,2] - 2);
%o ); Vec(w[,1]);} // _Petros Hadjicostas_, Jul 21 2020
%o /* Second PARI program for the general case of Josephus problem. We use the Burde-Thériault algorithm, not the formula T(n;k) = ceiling(Sum_{s=1..n-1} T(s;k)/(k-1)). We start with T(k;k) = 1 (and omit all previous 1's). Burde starts with the smallest T(n;k) >= k whose corresponding last survivor is 1. This, however, can be very large. To get the corresponding last survivors, modify the program to get the vector j. */
%o lista(nn,k) = {my(j=vector(nn)); my(f=vector(nn)); my(N=vector(nn));
%o j[1]=1; f[1]=0; N[1] = 1;
%o for(n=1, nn-1, f[n+1] = ((j[n]-N[n]-1) % (k-1)) + 1 - j[n];
%o j[n+1] = j[n] + f[n+1]; N[n+1] = (k*N[n] + f[n+1])/(k-1););
%o for(n=1, nn, if(N[n] > k-1, print1(N[n],",")));} \\ _Petros Hadjicostas_, Jul 23 2020
%Y Cf. A005428, A072493.
%Y Similar sequences: A011782 (k = 2), A073941 (k = 3), A072493 (k = 4), A120160 (k = 5), A120170 (k = 6), A120178 (k = 7), A120186 (k = 8), A120194 (k = 9), A120202 (k = 10).
%K nonn
%O 1,1
%A _N. J. A. Sloane_, _Simon Plouffe_
%E More terms (from the Burde paper, p. 208) from _R. J. Mathar_, Sep 26 2006
%E Name edited by _Petros Hadjicostas_, Jul 20 2020
|
