Deduction of the fast recurrence In the basic recurrence, k is a constant parameter and n varies. So we can write T(n) instead of T(n,k): (1) T(1) = 1, T(n) = 1 + [T(n-1)+k-1] mod n. The sought term is T(N), where N is a given value. Fast recurrence (with line numbers for reference): 1 z(1)=1, r(1)= 1 2 for m>=1: 3 if z(m)<k-1 then 4 z(m+1)=z(m)+1 5 r(m+1)=1+[r(m)+k-1] mod z(m+1) # basic recurrence 6 else 7 e(m) = -z(m) mod (k-1) 8 if r(m)+e(m)<=0 then e(m) -> e(m)+k-1 9 z(m+1) = z(m) + (z(m) + e(m))/(k-1) 10 r(m+1) = r(m) + e(m) 11 Result for m = M with z(M) <= N < z(M+1): 12 T(N) =r(M) + k(N - z(M)) Definitions: (D1) n is a so-called start number if T(n)<=k-1. (D2) z(m) is the sequence of start numbers. (D3) r(m) = T(z(m)) The basic recurrence leads to (2a) T(n+1) = T(n)+k if T(n)+k<=n+1 and (2b) T(n+1) = T(n)+k-(n+1) if not If d(m)=z(m+1)-z(m)>1, a linear progression (difference k) starts with r(m) according to (2a): (3a) T(z(m)+j) = r(m)+j*k, 0<=j<d(m). The monotony is broken with j=d(m), according to (2b): (3b) T(z(m)+d(m)) = T(z(m+1))= r(m+1) = r(m)+d(m)*k-z(m+1) For d(m)=1, (3a) is a tautology and (3b) still holds though there is no progression. d(m)=0 is forbidden. Conditions for consecutive start numbers: (4a) 1<= r(m) <=k-1, r(m+1)<=k-1, see (D1) and, according to (3b): (4b) r(m+1) = r(m)+(z(m+1)-z(m))*k-z(m+1), needed for line 10 After rearrangement: (4c) z(m+1) = (k*z(m)+e(m))/(k-1) = z(m) +(z(m)+e(m))/(k-1), see line 9 with e(m) = r(m+1)-r(m), see line 10 In order to make d(m)=(z(m)+e(m))/(k-1) an integer, we have to postulate: (4e) e(m) = q*(k-1)-p(m) with an integer q and p(m) = z(m) mod (k-1) So we get (4f) r(m+1) = r(m)-p(m)+q*(k-1) In order to fulfill (4a) we must select (5a) q=0 if r(m)-p(m)> 0 and (5b) q=1 if not This completes lines 7, 8. Lines 11, 12: The recurrence will stop if z(m)<= N < z(m+1). With (3a) and j=N-z(m) we yield the result: T(N) = T(z(m)+j) = r(m)+k*(N-z(m)) Lines 1, 3, 4, 5: As d(m)>=z(m)-z(m) mod(k-1), z(m)>=k-1 is sufficient for d(m)>0. If we fix z(1)=1 as the first start number and r(1)=T(1)=1, we must use the basic recurrence for z(m)<k-1. This makes the fast recurrence complete. Exponential increase of z(m): From (4c) we can see that z(m) increases by an average factor k/(k-1). So the approximate number s of steps can be taken from (k/(k-1))^s = N: s = log(N)/log(N/(k/(k-1))).