Closed form formula for repeated mods recursion

Question

I'm looking for a closed form formula for the recursion:

$$x_1=0$$ For $n\ge2$

$$x_n= x_{n-1}+k\mod n$$

i.e. for $k=5$,

$$x_1=0, x_2=1, x_3=0, x_4=1, x_5=1, x_6=0, x_7=5$$

Answer 1

It seems to me that finding a closed formula (in a traditional sense) for this kind of problem is quite hard, and maybe unfruitful (since the formula may not be efficiently computable).

But we can do the following, I don't know if this helps (I'm going to be sketchy and with an ordinal point of view, focused on the sequences as dynamical systems):

Suppose $n$ is already much bigger than $k$, and that $x_n=0$. Then, for a while, the following terms of the sequence are going to behave as a usual arithmetic progression (i.e., $x_m=k(m-n)$), until the sequence, due to its progression by $k$, catches again the size of $m'$, with its progression by $1$. Then the remainder operation will behave in a nontrivial manner and will "reset" the sequence, producing a number between $0$ and $k-1$ for $x_{m'}$.

So a good question is: Given $n$, can we find $m'$, i.e., can we predict when the sequence will reset? We can. Let call $next(n,k)$ to the first index $i$ such that the sequence $a_i:=k\cdot i$ equals or surpasses the sequence $b_i:=n+i$; then while $a_i$ covers the first $n$ elements in $n/k$ steps, $b_i$ covers $n/k$ elements more, which are covered by $a_i$ in $(n/k)/k$ steps, etc. Hence $$next(n,k)=\lceil n\cdot \sum_{i=0}^\infty\frac1{k^i}\rceil = \lceil\frac{kn}{k-1}\rceil.$$

Therefore, until $next(n,k)$, which is efficiently computed, the sequence just behaves as a usual arithmetic progression, then resets (we compute the remainder of the corresponding term of the sequence modulo $next(n,k)$) and continues until the index hits either $next(next(n,k),k)$ or the same number minus $1$, depending on whether the remainder is big enough or not to skip one index (i.e., close to $0$ or close to $k$).

---

Update: I'm adding an specific example due to request from the OP.

Suppose $k=3$. Then $\displaystyle\sum_{i=0}^\infty\frac1{k^i}=\frac32$, which is the number we need to compute the next function.

Using the trick stated above for $n\leq k$ is just a bit confusing if we want to understand it from the scratch, so let us compute up to $n=4$ just by hand: $x_1=0, x_2=1, x_3=1, x_4=0$.

Now we have $x_4=0$, and we can say that at index 4 the arithmetic progression by 3 has been reset, conveniently to 0 (we'll analyze other cases in a moment).

We know that from $n=4$ onwards, $x_n$ will behave as a usual arithmetic progression, until $n$ hits $next(4,3)=4\cdot\frac32 = 6$, value in which it resets again. Then simply $x_5=3$ and $x_6=0$, since we started at value $0$ (in $x_4$) and actually hit an integer inside the next function (because the product by $\frac32$ is an integer, not half-integer).

Now we start the arithmetic progression from value $0$ at index 6 until index $next(6,3)=6\frac32=9$, which is integer and therefore hit, so that $x_7=3, x_8=6, x_9=0$.

The next arithmetic progression goes from $n=9$ until $next(9,3)=\lceil 9\frac32 \rceil = \lceil 13.5\rceil = 14$, meaning that we should have $x_{13.5}=0$ and so $13$ is the last index before reset (and $14$ the first one after reset). Therefore $x_{10}=3, x_{11}=6, x_{12}= 9, x_{13}= 12$ and $x_{14}=1$.

We can also compute directly the values at $n=13$ and $n=14$, so that we do not need to follow the whole progression: the reset did not happen at value 0 because the starting index was an odd number $n=2m+1$; this implies that $next(n,3)=3m+2$ (index in which the reset has already produced), and the value at index $3m+1$ is just $3m$ (as we go from $2m+1$ to $3m+1$, in $m$ steps and starting from 0, so that our arithmetic progression by 3 grows up to $3m$). Therefore we have proved that if we start at 0 with odd index $2m+1$, then the value at $next(n,3)=3m+2$ is $1$ (from $3m+3$ mod $3m+2$).

Next arithmetic progression goes from $n=14$, starting at 1, up to $next(14,3)=21$, ending also at value 1 (since $n=14$ is even). Hence $x_{14}=1, x_{15}=4, x_{16}=7, x_{17}=10, x_{18}=13, x_{19}=16, x_{20}=19$.

Next one goes from $n=21$ (odd) starting at 1, supposedly up to $next(21,3)=32$, but the fact that we start at odd index plus the fact that the starting value is 1 complot to make the reset one index before, at $n=31$:

We start at odd index $n=2m+1$ with value 1. Then $next(n,3)=3m+2$ as before and the value at $3m+1$ would be, as before, $3m$ if we started from 0, but as we started from 1, its actual value is $3m+1$, which is 0 mod $3m+1$.

The next nontrivial steps in our computations are $x_{31}=0$ (odd, start at 0), $x_{47}=1$ (odd, start at 1), $x_{70}=0$ (even, start at 0), $x_{105}=0$ (odd, start at 0), $x_{158}=1$, (even, start at 1), $x_{237}=1$, etc. We fill the holes with the respective arithmetic progressions.

Answer 2

It is easy to see that $$ x_n=((\ldots(k \mod 2+k) \mod 3+k) \mod 4) \ldots)\mod (n-1)+k) \mod n. $$ I don't sure that there is a closed formula.