Supose we have a set $S$ of natural numbers. We define: $$ f(x) = \begin{cases} {x \over 2} & x \text{ is even } \\ {x - 1 \over 2} & x \text{ is odd }\end{cases} $$
Now let $a_0 = a_1 = 1$ and $a_n = a_{n-1} + a_{n-2}$ for $n \notin S$ and $a_n = f(a_{n-1} + a_{n-2})$ otherwise for $ n > 1$.
I want to calculate the remainder of $a_n \bmod p $ for $p$ prime. The problem is that the numbers become quite large so I can not store then. I must work with the reminders.
My fist idea was to work with the modular inverse of $2$ and e kept the remainder mod p at each step and instead of dividing by $2$, I multiply by $1/2$. The problem is that is does not work if $S$ has more than one element.
I think the solution is to keep the values $\bmod 2^y\cdot p$ where $y$ is the number of elements in $S$ $(\#S)$. And in the end take do remainder of $a_n \bmod p$. It seems to work but I don't understand why...
I'm sorry if I was not clear.
Thank you.