A357217 Array read by descending antidiagonals: T(n,k) is the number of cycles of the permutation given by the order of elimination in the Josephus problem for n numbers and a count of k; n, k >= 1.

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

Offset

1,3

Comments

n >= 2 is a Josephus_k prime if and only if T(n,k) = 1; see A163782-A163800.

Links

Pontus von Brömssen, Antidiagonals n = 1..100, flattened

James Dowdy and Michael E. Mays, Josephus permutations, Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 125-130.

Wikipedia, Josephus problem

Index entries for sequences related to the Josephus Problem

Formula

T(n,k+A003418(n)) = T(n,k), i.e., the n-th row is periodic with period A003418(n).

Example

Array begins:
  n\k|  1  2  3  4  5  6  7  8  9 10
  ---+------------------------------
   1 |  1  1  1  1  1  1  1  1  1  1
   2 |  2  1  2  1  2  1  2  1  2  1
   3 |  3  2  1  2  1  2  3  2  1  2
   4 |  4  2  2  2  2  2  2  2  2  2
   5 |  5  1  1  1  3  3  1  3  3  3
   6 |  6  1  2  3  2  3  2  1  2  3
   7 |  7  4  3  2  3  2  3  2  5  2
   8 |  8  2  2  2  4  2  2  4  6  2
   9 |  9  1  3  5  3  3  3  3  3  3
  10 | 10  5  2  1  2  3  2  1  2  3
For n = 4, k = 2, the order of elimination is (2,4,3,1) (row 4 of A321298). This permutation has two cycles, (1 2 4) and (3), so T(4,2) = 2.

Prog

(Python)
from sympy.combinatorics import Permutation
def A357217(n, k):
    return Permutation.josephus(k, n).cycles

Crossrefs

Cf. A003418, A006694 (column k=2), A163782-A163800 (Josephus primes), A198789, A321298 (the Josephus permutations for k=2).

Sequence in context: A343796 A139462 A236256 * A353595 A317086 A131376

Adjacent sequences: A357214 A357215 A357216 * A357218 A357219 A357220

Keyword

nonn,tabl

Author

Pontus von Brömssen, Sep 18 2022

Status

approved