login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032434 Triangle read by rows: last survivors of Josephus elimination process. 11
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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 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 link "Fast recurrence".

(End)

REFERENCES

Ball, W. W. R. and Coxeter, H. S. M., Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 32-36, 1987.

Kraitchik, M. "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W.W. Norton, pp. 93-94, 1942.

LINKS

T. D. Noe, Rows n=1..50, flattened

Ph. Dumas, Algebraic aspects of B-regular series

L. Halbeisen, The Josephus Problem

L. Halbeisen and N. Hungerbuehler, The Josephus Problem, Journal de Théorie des Nombres de Bordeaux 9 (1997) 303-318

A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991.

A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991. [Cached copy, with permission.]

Eric Weisstein's World of Mathematics, Josephus Problem.

Gerhard Kirchner, Fast recurrence

FORMULA

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", pg. 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)

EXAMPLE

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: n=7, 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.

MATHEMATICA

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 *)

PROG

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

CROSSREFS

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

Sequence in context: A102746 A123143 A128133 * A002347 A006642 A210595

Adjacent sequences:  A032431 A032432 A032433 * A032435 A032436 A032437

KEYWORD

nonn,tabl,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by Ralf Stephan, May 18 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 23 05:28 EST 2017. Contains 281185 sequences.