A032434 -id:A032434 - cp's OEIS frontend

A032436 Triangle of third-to-last man to survive in the Josephus problem of n men in a circle with every k-th killed, with 1 <= k <= n and n >= 3.

1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 4, 1, 1, 3, 1, 2, 5, 3, 1, 2, 1, 1, 2, 6, 1, 4, 3, 3, 1, 1, 2, 7, 3, 1, 1, 2, 4, 1, 1, 2, 8, 1, 4, 1, 3, 3, 5, 1, 1, 4, 9, 3, 2, 5, 1, 5, 1, 1, 4, 3, 2, 10, 1, 5, 1, 1, 3, 8, 2, 1, 1, 1, 2, 11, 3, 1, 5, 6, 4, 2, 4, 3, 1, 1, 1, 7, 12, 5, 2, 3, 2, 1, 9, 4, 5, 7, 1, 1, 6

Offset: 3

N. J. A. Sloane

			Triangle T(n,k) (with rows n >= 3 and columns k = 1..n) begins
   1, 1, 1;
   2, 1, 1, 1;
   3, 1, 2, 1, 2;
   4, 1, 1, 3, 1, 2;
   5, 3, 1, 2, 1, 1, 2;
   6, 1, 4, 3, 3, 1, 1, 2;
   7, 3, 1, 1, 2, 4, 1, 1, 2;
   8, 1, 4, 1, 3, 3, 5, 1, 1, 4;
   9, 3, 2, 5, 1, 5, 1, 1, 4, 3, 2;
  10, 1, 5, 1, 1, 3, 8, 2, 1, 1, 1, 2;
  11, 3, 1, 5, 6, 4, 2, 4, 3, 1, 1, 1, 7;
  ...

W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed., New York: Dover, pp. 32-36, 1987.
M. Kraitchik, "Josephus' Problem," Sec. 3.13 in Mathematical Recreations, New York: W. W. Norton, pp. 93-94, 1942.
Eric W. Weisstein, The CRC Concise Encyclopedia in Mathematics, 2nd ed., Chapman and Hall/CRC, 2002. [The first 7 rows of the triangle appear on p. 1596 of this book under the topic "Josephus Problem".]

W. W. R. Ball, Mathematical Recreations and Essays, 4th ed., New York: The MacMillan Company, 1905 (see "Decimation" on pp. 19-20).
Sean A. Irvine, A032435 and A032436 Josephus problem data mismatch, message in seqfan, June 2020.
F. Jakóbczyk, On the generalized Josephus problem, Glasow Math. J. 14(2) (1973), 168-173. [It contains algorithms that allow the identification of the original position of the third-to-last person to survive in Josephus problem.]
M. Kraitchik, "Josephus' Problem", Sec. 3.13 in Mathematical Recreations, New York: W. W. Norton, pp. 93-94, 1942. [Available only in the USA through the Hathi Trust Digital Library.]
Eric Weisstein's World of Mathematics, Josephus Problem. [It contains a new, apparently corrected, triangle.]
Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus Problem

Cf. A032434, A032435.

A198790 Irregular table T(n,k) read by rows: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, lcm(1, 2, 3, ..., n) >= k >= 1.

Original entry on oeis.org

1, 2, 1, 3, 3, 2, 2, 1, 1, 4, 1, 1, 2, 2, 3, 2, 3, 3, 4, 4, 1, 5, 3, 4, 1, 2, 4, 4, 1, 2, 4, 5, 3, 2, 5, 1, 3, 4, 1, 1, 3, 4, 1, 2, 5, 4, 2, 3, 5, 1, 3, 3, 5, 1, 3, 4, 2, 1, 4, 5, 2, 3, 5, 5, 2, 3, 5, 1, 4, 3, 1, 2, 4, 5, 2, 2, 4, 5, 2, 3, 1, 6, 5, 1, 5, 1, 4

Offset: 1

William Rex Marshall, Nov 21 2011

Arrange 1, 2, 3, ... n clockwise in a circle. Starting the count at 1, delete every k-th integer clockwise until only one remains, which is T(n,k).

In the full table in A198789, row n repeats with a periodicity of lcm(1, 2, 3, ..., n) = A003418(n). This sequence is a scan of each row in A198789 for exactly one period length.

			n\k  1  2  3  4  5  6  7  8  9 10 11 12
---------------------------------------
1 |  1
2 |  2  1
3 |  3  3  2  2  1  1
4 |  4  1  1  2  2  3  2  3  3  4  4  1

William Rex Marshall, Rows n = 1..10, flattened
Index entries for sequences related to the Josephus Problem

Cf. A003418, A007495, A032434, A198788, A198789.

T(1,1) = 1;

for n >= 2, lcm(1, 2, ... n) >= k >=1: T(n,k) = ((T(n-1,((k-1) mod lcm(1, 2, ... n-1)) + 1) + k - 1) mod n) + 1.

A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 3, 2, 1, 16, 4, 3, 2, 1, 32, 6, 4, 3, 2, 1, 64, 9, 5, 4, 3, 2, 1, 128, 14, 7, 5, 4, 3, 2, 1, 256, 21, 9, 6, 5, 4, 3, 2, 1, 512, 31, 12, 8, 6, 5, 4, 3, 2, 1, 1024, 47, 16, 10, 7, 6, 5, 4, 3, 2, 1, 2048, 70, 22, 12, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Gerhard Kirchner, Oct 21 2021

The table, see example, is read by ascending antidiagonals.

Trivial cases: T(m,k)=m for m

The recurrence in the formula section does not only yield T(m,k), but also the survivor's number S(m,k) so that the Josephus problem can be solved for any number N of people, especially for large N because T(m,k) grows exponentially, see link "Derivation of the recurrence", section II.

T(m,k) compared with other sequences ("->" means that the sequences can be made equal by removing repeated terms, see link "Derivation of the recurrence", section IV).

T(m,2) = A000079(m)=2^(m-1)

T(m,3) -> A073941

T(m,4) -> A072493

T(m+4,4)= A005427(m)

T(m,5) -> A120160

T(m,6) -> A120170

T(m,7) -> A120178

T(m,8) -> A120186

T(m,9) -> A120194

T(m,10)-> A120202

			k=4: 7 people, survivors number 2 <4.
k=4: 6 people, survivors number 5>=4, counterexample.
Table T(m,k) begins:
  m\k____2____3____4____5
   1:    1    1    1    1
   2:    2    2    2    2
   3:    4    3    3    3
   4:    8    4    4    4
   5:   16    6    5    5
   6:   32    9    7    6
   7:   64   14    9    8
   8:  128   21   12   10
   9:  256   31   16   12
  10:  512   47   22   15

Gerhard Kirchner, Derivation of the recurrence
Gerhard Kirchner, Table for 2<=k<=10 and 1<=m<=30
Index entries for sequences related to the Josephus Problem

Cf. A005428, A032434, A054995, A007495.

block(k:10, mmax:30, t:1, s:1, T:[1],
/*Terms T(m,k), m=1 thru mmax */
for m from 1 thru mmax-1 do(
    p:  mod(t, k-1),
    if s>p then e:-p else e:k-1-p,
    t: (k*t+e)/(k-1), s: 1+mod(s+e-1, t),
    T:append(T,[t])),
return (T));

Recurrence for T(m,k) and S(m,k), the survivor's number.
Start: T(1,k)=S(1,k)=1.
T(m+1,k)=(k*T(m,k)+e)/(k-1),
S(m+1,k)=1 + (S(m,k)+e-1) mod T(m+1,k),
with e=-p if S(m,k)>p and e=k-1-p otherwise, p = T(m,k) mod (k-1).

Previous Showing 11-13 of 13 results.

cp's OEIS Frontend

A032436 Triangle of third-to-last man to survive in the Josephus problem of n men in a circle with every k-th killed, with 1 <= k <= n and n >= 3.

Views

Author

Keywords

Examples

References

Links

Crossrefs

A198790 Irregular table T(n,k) read by rows: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, lcm(1, 2, 3, ..., n) >= k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maxima

Formula