JOSEPHUS NUMBERS


Let the numbers 1, 2, ..., N be placed around acircle, and decimate every K-th number. For example if N=10 and K=3 the decimation sequence is 3, 6, 9, 2, 7, 1, 8, 5, 10, 4.
The last number is J(N;K). In the Example J(10;3)=4.

In general the recurrence relation holds (K fixed): 

   J(N+1) = min { J(N) + K - j * N ; 0 <= j < (J(N)+K)/N }

For example J(11;3) = min { 4 + 3 - j * 11 ; ... } = 7.

For a fixed K consider the sequence of the numbers N for which J(N;K) < K. Denote it A(i;K), and let B(i;K) = J( A(i);K); K ).
For example, for K=3, these sequences are 

  A  1  2  3  4  6  9 14 21 31 47 ...
  B  1  2  2  1  1  1  2  2  1  2 ...

The following recurrence holds (K fixed): 

   C = K * A(i) - B(i)
   A(i+1) = 1 + floor( C/(K-1) )
   B(i+1) = ( K - 1 - C % (K-1) ) mod(A(i+1))
where X mod(Y) = X%Y if this is positive, and Y if this is 0.

Example K=4: 

  A  1  2  3  4  5  7  9 12 16 22 29 39 52 68 92 ...
  B  1  1  2  2  1  2  1  1  1  3  2  3  3  2  2 ...
Example K=5: 
  A  1  2  3  4  5  6  8 10 12 15 19 24 30 37 47 ...
  B  1  2  1  2  2  1  3  3  1  1  2  3  3  1  4 ...
From the recurrence is clear that lim A(i+1)/A(i) = K/(K-1).

The values of J(N;K) for A(i) ≥ N > A(i+1) is 

    J(N;K) = B(i) + K * (N-A(i))

Conjecture.
The frequencies of the numbers 1, .., K-1 in the B sequence tend to 1/(K-1).

Marco Corvi - 2019