Limiting memory usage while keeping score

For an assignment we are asked the following(simplified) :

A function F(a) has a non-negative integer as a result. This result is reused in the function itself. Like this, and where the first a is given:

new_a = (c1 * (previous_a or first_a) + c2) mod c3

Write, in C#, a sufficiently fast and memory efficient algorithm that tells how many iterations of the function does it take before new_a is within a specified range of any previous ones?

Now I have already made a "naive" solution as follows: I create an array of size c3 and for every new_a I check whether its corresponding index is set to true. If so, the number of iterations is returned. If not, the index and the given range around it is set to true. This goes on until there is a hit.

This solution is very fast but the downsize is that for large enough sizes of c3 there is just not enough memory available.

I have been thinking about a week now on how to solve the memory problem, but I just am stuck figuring out how to do it? The only thing I can think of is that given the function there is some kind of assumption I should/can make about the distribution of its outcomes but I just am stuck.

Any ideas on the direction I should take?

Your idea of an array of size $c_3$ is a good one.
But you can do better. First, since you need only be withing a range $r$,
you can use an array of size $c_3/r$, rounding upward, and just mark the entry
corresponding to the integer segment you fall in (there may be some details to work out).

Then, rather than using an array, if it is still too large, you can
build a binary structure, so that you create only the array entries you
need. Each node of the binary structure corresponds to a range of
consecutive entries.


Then, you can reduce the memory requirement further by merging contiguous ranges where all entries have been hit, and rebalance the tree.

Of course, there is a $\log_2 c_3/r$ price in access time. But this cost is limited by the tree shrinking as it gets full.

StackExchange Computer Science Q#42098, answer score: 2