login
Array T(n,k) read by antidiagonals: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, k >= 1.
6

%I #32 Mar 27 2023 05:16:54

%S 1,1,2,1,1,3,1,2,3,4,1,1,2,1,5,1,2,2,1,3,6,1,1,1,2,4,5,7,1,2,1,2,1,1,

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

%U 2,2,3,1,5,3,3,1,4,7,12,1,1,1,4,2,3,5,1,8,5,7,9,13

%N Array T(n,k) read by antidiagonals: Last survivor positions in Josephus problem for n numbers and a count of k, n >= 1, k >= 1.

%C 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).

%C The main diagonal (1, 1, 2, 2, 2, 4, 5, 4, ...) is A007495.

%C Concatenation of consecutive rows (up to the main diagonal) gives A032434.

%C The periods of the rows, (1, 2, 6, 12, 60, 60, 420, 840, ...), is given by A003418.

%H William Rex Marshall, <a href="/A198789/b198789.txt">First 141 antidiagonals of array, flattened</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F T(1,k) = 1; for n > 1: T(n,k) = ((T(n-1,k) + k - 1) mod n) + 1.

%e .n\k 1 2 3 4 5 6 7 8 9 10

%e ----------------------------------

%e .1 | 1 1 1 1 1 1 1 1 1 1

%e .2 | 2 1 2 1 2 1 2 1 2 1

%e .3 | 3 3 2 2 1 1 3 3 2 2

%e .4 | 4 1 1 2 2 3 2 3 3 4

%e .5 | 5 3 4 1 2 4 4 1 2 4

%e .6 | 6 5 1 5 1 4 5 3 5 2

%e .7 | 7 7 4 2 6 3 5 4 7 5

%e .8 | 8 1 7 6 3 1 4 4 8 7

%e .9 | 9 3 1 1 8 7 2 3 8 8

%e 10 | 10 5 4 5 3 3 9 1 7 8

%t T[n_, k_] := T[n, k] = If[n == 1, 1, Mod[T[n-1, k]+k-1, n]+1];

%t Table[T[n-k+1, k], {n, 1, 13}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Mar 04 2023 *)

%Y Cf. A000027 (k = 1), A006257 (k = 2), A054995 (k = 3), A088333 (k = 4), A181281 (k = 5), A360268 (k = 6), A178853 (k = 7), A109630 (k = 8).

%Y Cf. A003418, A007495 (main diagonal), A032434, A198788, A198790.

%K nonn,easy,tabl

%O 1,3

%A _William Rex Marshall_, Nov 21 2011