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

Author

Pontus von Brömssen, Sep 18 2022

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
		

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

Crossrefs

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

Programs

Python

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

Formula

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