A321781 -id:A321781 - cp's OEIS frontend

A321793 Josephus problem: Records in the rows of A321781.

3, 5, 10, 11, 27, 11, 19, 42, 19, 40, 26, 23, 47, 62, 45, 56, 92, 55, 86, 74, 62, 67, 85, 65, 85, 169, 119, 105, 153, 90, 94, 150, 139, 144, 175, 171, 119, 131, 178, 161, 187, 234, 301, 203, 206, 226, 173, 217, 406, 178, 216, 164, 372, 208, 341, 175, 281, 234, 301, 322, 252, 339

Offset: 2

Hugo Pfoertner, Nov 19 2018

nonn

For a given initial position j among the n persons in the Josephus problem, there exists a smallest elimination parameter q, meaning every q-th person being executed, by which position j can be made to survive. a(n) gives the maximum of q taken over all initial positions 1 <= j <= n. The value of j, for which the maximum q occurs, is given by A321794.

Hugo Pfoertner, Table of n, a(n) for n = 2..400
Index entries for sequences related to the Josephus Problem

Cf. A006257, A321781, A321794.

A321794 Josephus problem: Positions of records in the rows of A321781.

Original entry on oeis.org

2, 1, 4, 5, 6, 1, 2, 4, 2, 4, 4, 7, 3, 3, 5, 14, 13, 8, 14, 18, 4, 5, 19, 10, 11, 10, 13, 25, 2, 21, 18, 19, 15, 10, 11, 15, 4, 39, 23, 33, 33, 39, 28, 4, 34, 32, 8, 32, 18, 12, 26, 53, 10, 11, 22, 33, 26, 3, 54, 42, 14, 39, 18, 59, 66, 6, 50, 61, 23, 69, 8, 59, 3, 21

Offset: 2

Hugo Pfoertner, Nov 19 2018

nonn

a(n) gives the initial position j of a person in the Josephus problem such that the largest minimal elimination parameter q, meaning every q-th person being executed, is needed among all initial positions 1 <= j <= n, to make position a(n) survive. The corresponding value of q is given by A321793.

Hugo Pfoertner, Table of n, a(n) for n = 2..400
Index entries for sequences related to the Josephus Problem

Cf. A321781, A321793.

A032434 Triangle read by rows: last survivors of Josephus elimination process.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

T(n,k) 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 k - 1 places clockwise from i. Repeat, counting k - 1 places from the next undeleted integer, until only one integer remains. [After John W. Layman]
From Gerhard Kirchner, Jan 08 2017: (Start)
The fast recurrence is useful for large n, if single values of T(n,k) are to be determined (not the whole sequence). The number of steps is about log(n)/log(n/(k/(k-1))) instead of n, i.e., many basic steps are bypassed by a shortcut.
Example: For computing T(10^80, 7), about 1200 steps are needed, done in a second, whereas even the age of the universe would not be sufficient for the basic recurrence. Deduction of the fast recurrence and the reason for its efficiency: See the link "Fast recurrence". (End)

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins
  1;
  2, 1;
  3, 3, 2;
  4, 1, 1, 2;
  5, 3, 4, 1, 2;
  6, 5, 1, 5, 1, 4;
  7, 7, 4, 2, 6, 3, 5;
  ...
Fast recurrence for n = 7 and k = 3:
m =    1 2 3 4 5 6,
z(m) = 1 2 3 4 6 9,
r(m) = 1 2 2 1 1,
z(6) > n => M = 5.
Result: T(7,3) = r(5) + 3*(n - z(5)) = 4.

W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987, see pp. 32-36.
M. Kraitchik, "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.

T. D. Noe, Rows n = 1..50, flattened
Philippe Dumas, Algebraic aspects of B-regular series, inria-00074743, 1993.
Philippe Dumas, Algebraic aspects of B-regular series, in: A. Lingas, R. Karlsson, S. Carlsson S. (eds), Automata, Languages and Programming, ICALP 1993 (Lecture Notes in Computer Science, vol 700, Springer, Berlin, Heidelberg), pp. 457-468, 1993.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, Journal de Théorie des Nombres de Bordeaux 9 (1997), 303-318.
Gerhard Kirchner, Fast recurrence.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, preprint, 1991. [Cached copy, with permission]
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
Eric Weisstein's World of Mathematics, Josephus Problem.
Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus problem

Cf. A032435, A032436, A321781.

Second column is A006257, third column is A054995. Diagonal T(n, n) is A007495.

t[1, k_] = 1; t[n_, k_] := t[n, k] = If[m = Mod[t[n-1, k] + k, n]; m != 0, m, n]; Flatten[ Table[ t[n, k], {n, 1, 14}, {k, 1, n}]] (* Jean-François Alcover, Sep 25 2012 *)

T(n,k)=local(t): if(n<2,n>0,t=(T(n-1,k)+k)%n: if(t,t,n))

Recurrence: T(1, k) = 1, T(n, k) = (T(n-1, k) + k) mod n if this is nonzero and n if not.
From Gerhard Kirchner, Jan 08 2017: (Start)
The same recurrence without these conditions:
T(1, k) = 1,  T(n, k) = 1 + (T(n-1, k) + k - 1) mod n.
This "basic" recurrence is used in the following:
Fast recurrence (n >= k):
z(1) = 1, r(1) = 1,
if z(m) < k-1 then
  z(m+1) = z(m) + 1,
  r(m+1) = 1 + (r(m)+k-1) mod z(m+1) (basic recurrence),
else
  e(m) = -z(m) mod (k-1),
  if r(m) + e(m) <= 0 then e(m) -> e(m) + k - 1,
  z(m+1) = z(m) + (z(m) + e(m))/(k-1),
  r(m+1) = r(m) + e(m).
Result for m = M with z(M) <= n < z(M+1):
T(n,k) = r(M) + k(n - z(M)). (End)
From Gerhard Kirchner, Jan 12 2017: (Start)
Another fast (and shorter) recurrence is given in "Functional iteration and the Josephus problem", p. 1, (see link):
D(m,k) = ceiling(k/(k-1)*D(m-1,k)), m >= 1; D(0,k)=1.
Result for m with D(m-1,k) <= (k-1)*n < D(m,k):
T(n,k) = k*n + 1 - D(m,k). (End)

Edited by Ralf Stephan, May 18 2004

A187788 a(n) is the least step for the Sankt-Petrus-game with n white and n black stones.

Original entry on oeis.org

2, 5, 2, 4, 3, 11, 2, 3, 8, 16, 4, 21, 6, 5, 2, 11, 20, 34, 8, 15, 10, 7, 13, 11, 13, 45, 18, 23, 8, 3, 2, 25, 75, 42, 13, 5, 23, 13, 50, 16, 18, 89, 38, 8, 39, 30, 29, 38, 7, 45, 23, 137, 46, 63, 17, 48, 5, 46, 34, 140, 33, 39, 2, 28, 29, 79, 33, 48, 3, 10, 46, 120, 6, 37, 17, 8, 44, 15, 160, 20, 35, 144, 104, 179, 153, 24, 8, 265, 19, 9, 62, 7, 139, 19, 44, 93, 182, 27, 158, 185

Offset: 1

Paul Weisenhorn, Jan 06 2013

nonn

Beginning at the position A187789(n) with step a(n), (n-1) white stones were eliminated; then from the position 1 of the last white stone, n black stones were eliminated.

			n=4; WBWWBBWB; startposition=A187789(4)=8; least step=a(4)=4; elimination: white stones: {3,7,4}; black stones: {6,5,8,2}.

W. Ahrens, Das Josephusspiel, Archiv für Kulturgeschichte, Jg 11(1913), 129-151.

R. Baumann, Das Josephus-Problem, LOG IN, Heft Nr. 165, pp. 68-71, 2010 (in German).
Index entries for sequences related to the Josephus Problem

Cf. A187789, A206602.

First column in A321781.

s:=1: M:={}:
for n from 1 to 100 do M:=M union {n}:
while (M <> {}) do
  s1:=s: s:=s+1: f[1]:=1:
  for n from 2 to 101 do  n1:=n-1:
    f[n]:=(f[n1]+s1) mod n +1:
    if (f[n]=1) and (n1 in M) then
      a[n1]:=s: M:=M minus {n1}:
    end if:
  end do:
end do:

A343780 If n good guys followed by n bad guys stand in a circle, a(n) is the least q such that executing every q-th person gets all bad guys first.

Original entry on oeis.org

2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881, 13482720, 25779600, 68468401, 610346880, 1271932200, 327280800, 11605393800, 10071626400, 270022896000, 212719197601, 673534461600, 80276676481, 7618206526561, 14227357636801

Offset: 1

Nicholas Matteo, Apr 29 2021

nonn

There are 2n people in a circle, numbered 1 through 2n; the first n are "good guys" and the last n are "bad guys." We count, starting from 1, to the q-th person, who is executed; then, starting from the next position, repeat until all bad guys are gone.
This is a variant of the Josephus problem. In exercise 1.21 of Concrete Mathematics, it is proved there is always a q such that all bad guys are executed before any good guys, namely the least common multiple of n+1, n+2, ..., 2n (which provides an upper bound for a(n)).
According to Ball and Coxeter, in medieval times this was called the "Turks and Christians problem", described as n Turks and n Christians aboard a ship in a storm, which will sink unless half the passengers are thrown overboard; every q-th person will be tossed in the sea.
Schumer (2002) mentions this version along with more variants (e.g., eliminating all odd-numbered people first) in the section "Subsets marked for elimination".
Graham, Knuth and Patashnik say a non-rigorous argument suggests that a "random" value of q will succeed with probability (n/(2n)) * ((n-1)/(2n-1)) * ... * (1/(n+1)) = 1/binomial(2n,n) ~ sqrt(Pi*n)/4^n, so we might expect to find such a q less than 4^n (page 500). All the known values of a(n) are (much) less than 4^n.

			For n = 2, we have four people; with q = 7 we count 1,2,3,4,1,2,3 and person 3 is eliminated. Next we count 4,1,2,4,1,2,4, so person 4 is eliminated, leaving only 1 and 2. Attempting this with any q < 7 does not eliminate 3 and 4 first.

R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994, p. 20.
W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover, 1987, pp. 32-36.

Bert Dobbelaere, Table of n, a(n) for n = 1..40
P. Schumer, The Josephus Problem: Once More Around, Mathematics Magazine, Vol. 75:1 (2002), 12-17.
Index entries for sequences related to the Josephus Problem
Bert Dobbelaere, Python program

Cf. A198791, least q eliminating the odd-numbered people.
Cf. A006257, last survivor with q = 2.
Cf. A054995, last survivor with q = 3.
Cf. A321781, least q leaving position j as last survivor.
Cf. A321793, maximum q needed to ensure survival of one of n people.

def A343780(n):
    q = 1
    while True:
        s, c = [1]*n+[0]*n, 0
        for i in range(n):
            c = (c+q)%(2*n-i)
            if s[c]: break
            s = s[:c]+s[c+1:]
        else:
            return q+1
        q += 1 # Chai Wah Wu, Apr 30 2021

a(17)-a(21) from Chai Wah Wu, Apr 30 2021
a(22) from Nicholas Matteo, Apr 30 2021
a(23)-a(25) from Jon E. Schoenfield, Apr 30 2021
a(26)-a(27) from Bert Dobbelaere, May 01 2021

cp's OEIS Frontend

A321793 Josephus problem: Records in the rows of A321781.

Views

Author

Keywords

Comments

Links

Crossrefs

A321794 Josephus problem: Positions of records in the rows of A321781.

Views

Author

Keywords

Comments

Links

Crossrefs

A032434 Triangle read by rows: last survivors of Josephus elimination process.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A187788 a(n) is the least step for the Sankt-Petrus-game with n white and n black stones.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

A343780 If n good guys followed by n bad guys stand in a circle, a(n) is the least q such that executing every q-th person gets all bad guys first.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions