Searching for a positional function in recursive formula

First do note that my english in not the best here. If anyone is interested in helping me in solving this problem and want me detail something better, do not esitate in asking more details.

A specific solution in any tagged given language is much appreciated. Even if more general solution in term of formula is the target of this question.

Thanks

---

Let define Sequence Rule SR, a fixed sequence of integer numbers:

SR = (a, b, c, d, ..)

---

Example

SR = (1, 2, 3, 5)

---

Let define Shifting Sequence rule SS the sequence obtain开发者_StackOverflow中文版ed by SR as:

SS = (a-0,b-a,c-b,d-c,..-d)

---

Example

(1-0, 2-1, 3-2, 5-3) = (1, 1, 1, 2)

---

The shifting sequence rule SS should compute to an output sequence OS according to the following recursive formula:

OS(n) = 0, n=0

OS(n) = OS(n-1) + SS(i), n>0

where i is the position of n in the current subgroup SS.

---

Example

OS(n) = (1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15..)

where n=(1,2,3,4,5,6,7,8,9,10,11,12,..).

OS(0) = 0
OS(1)  = OS(0)  + SS(1) = 0 + 1  = 1
OS(2)  = OS(1)  + SS(2) = 1 + 1  = 2
OS(3)  = OS(2)  + SS(3) = 2 + 1  = 3
OS(4)  = OS(3)  + SS(4) = 3 + 2  = 5
OS(5)  = OS(4)  + SS(1) = 5 + 1  = 6
OS(6)  = OS(5)  + SS(2) = 6 + 1  = 7
OS(7)  = OS(6)  + SS(3) = 7 + 1  = 8
OS(8)  = OS(7)  + SS(4) = 8 + 2  = 10
OS(9)  = OS(8)  + SS(1) = 10 + 1 = 11
OS(10) = OS(9)  + SS(2) = 11 + 1 = 12
OS(11) = OS(10) + SS(3) = 12 + 1 = 13
OS(12) = OS(11) + SS(4) = 13 + 2 = 15

---

What actually I'm missing (not able to get) is the current position of n in the related shifting group given n only, such that:

pos(n)=i -> S(pos(n)) = S(i)

so finally I can write

OS(0) = 0

OS(n) = OS(n-1) + SS(pos(n))

---

What I've been able to get till now is a formula for the current index of the shifting group. I suspect it can help me in determining the wanted positional formula pos(n), but don't know how :((

The group index can be expressed as:

G(n)=ceiling(n/D(SS))

Where D(SS) is the dimension of SS, that is the number of elements in in the sequence rule.

---

Example

For example the $n$ sequence ranges 1 to 12. The number of shifting groups (1,1,1,2) of dimension 4 that makes a 1->1 mapping to OS(n) are 3 = 12/4.

The grouping index for n=9 can be computed as:

 G(9) = ceiling(n/D(SR)) = ceiling(9/4) = 3

---

FINAL ANSWER

---

The usage of the % operator is what I was missing. The final recursive formula is:

OS(n) = 0, n=0

OS(n) = OS(n-1) + SS((n + D(SR)-1) % D(SR) + 1), n>0

Or using a pure mathematical formula (and the definition of group index above):

OS(n) = 0, n=0

OS(n) = OS(n-1) + SS((n + D(SR)-1 - (D(SR) * G(n)) + 1), n>0

---

THANKS @GARETH

---

The question is quite hard to understand, but I think that you are looking for the modulus operation.

The sequence SS has 4 elements, so pos(n) is n modulo 4.

This operation can be computed in many programming languages—including C# and Ruby—by the % operator, and in Haskell by the mod function.

---

If you need the modulus to be in the range 1 to 4 rather than 0 to 3, use this expression:

(n + 3) % 4 + 1