|
| |
|
|
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 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.)
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 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.
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)).
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.
We also have T(n+1;k) = floor((k/(k-1))*T(n;k)) or ceiling((k/(k-1)*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+k-1; 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 (k-1)) + 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 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}.
We actually have S(n+1; k) = (k*S(n;k) + f(n+1;k))/(k-1) for n >= 1.
Notice that the Burde-Thé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 counting-off games described in the book are related to a similar counting-off 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, nn-1,
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 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. */
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, nn-1, f[n+1] = ((j[n]-N[n]-1) % (k-1)) + 1 - j[n];
j[n+1] = j[n] + f[n+1]; N[n+1] = (k*N[n] + f[n+1])/(k-1); );
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms (from the Burde paper, p. 208) from R. J. Mathar, Sep 26 2006
|
|
|
STATUS
|
approved
|
| |
|
|
