

A005427


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.
(Formerly M3759)


7



5, 7, 9, 12, 16, 22, 29, 39, 52, 69, 92, 123, 164, 218, 291, 388, 517, 690, 920, 1226, 1635, 2180, 2907, 3876, 5168, 6890, 9187, 12249, 16332, 21776, 29035, 38713, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Is this the same as A072493 with its first 8 terms removed? See also the similar conjecture concerning A005428 and A073941.
We describe the countingoff 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 m1 probably because he relates this problem to the representation of m in the fractional base k/(k1) = 4/3. He actually modifies the (4/3)representation of m to include negative coefficients. See the coefficients f(n;k) below.)
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.
When m = 5, 9, 12, 16, 218, 517, ... the last survivor is the first person.
When m = 7, 29, 69, 92, 291, 388, ... the last survivor is the second person.
When m = 22, 39, 52, 123, 164, 690, ... the last survivor is the third person.
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:
(a) If 0 = a(n) mod 3, then a(n+1) = (4/3)*a(n), and i(n+1) = i(n).
(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) If 1 = a(n) mod 3 and i(n) = 2, then a(n+1) = floor((4/3)*a(n)) and i(n+1) = 1.
(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.
(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.
(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.
(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)
In general, for k >= 2, it seems that when m people are placed on a circle, labeled 1 through m, and every kth person is removed (starting the counting at person 1), we may determine those m for which the last survivor is in {1, 2, ..., k1} in the following way.
Define the sequence (T(n;k): n >= 1) by T(n;k) = ceiling(Sum_{s=1..n1} T(s;k)/(k1)) 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, ..., k1} consists of all the numbers T(n;k) >= k (thus, we exclude the cases m = 1, ..., k1 that may be repeated more than once in the sequence (T(n;k): n >= 1)).
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. 373375 and 377379, where he provides two methods of solution) may provide clues for proving the conjecture.
We also have T(n+1;k) = floor((k/(k1))*T(n;k)) or ceiling((k/(k1)*T(n;k)).
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).
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+k1; k) for n >= 1. (It is easy to prove that S(1;k) = T(k;k) = 1.)
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 (k1)) + 1  j(n;k) and j(n+1;k) = j(n;k) + f(n+1;k) for n >= 2.
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 kth 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,...,k1}.
We actually have S(n+1; k) = (k*S(n;k) + f(n+1;k))/(k1) for n >= 1.
Notice that the BurdeThériault algorithm is a generalization of Schuh's method. (End)


REFERENCES

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 countingoff games described in the book are related to a similar countingoff game in Burde (1987).]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA



EXAMPLE

We explain why 5 and 7 are in the sequence but 6 is not.
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.
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.
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.
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)


MATHEMATICA



PROG

(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). */
lista(nn) = {my(w = matrix(nn, 2)); w[1, 1] = 5; w[1, 2] = 1; for(n=1, nn1,
if(0 == w[n, 1] % 3, w[n+1, 1] = w[n, 1]*4/3; w[n+1, 2] = w[n, 2]);
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);
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);
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);
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);
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);
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);
/* Second PARI program for the general case of Josephus problem. We use the BurdeThériault algorithm, not the formula T(n; k) = ceiling(Sum_{s=1..n1} T(s; k)/(k1)). 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. */
lista(nn, k) = {my(j=vector(nn)); my(f=vector(nn)); my(N=vector(nn));
j[1]=1; f[1]=0; N[1] = 1;
for(n=1, nn1, f[n+1] = ((j[n]N[n]1) % (k1)) + 1  j[n];
j[n+1] = j[n] + f[n+1]; N[n+1] = (k*N[n] + f[n+1])/(k1); );


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS

More terms (from the Burde paper, p. 208) from R. J. Mathar, Sep 26 2006


STATUS

approved



