get index of concatenated range list

Question

I have list of ranges which all of the ranges in that list has the same start and stop, but not the same step.
eg:

[range(0, 10, 2), range(0, 10, 3)]

Of course, the list can contain more than only 2 ranges.
The concatenated range list represents the following numbers:

[0, 2, 3, 4, 6, 8, 9]

I want to get the x index of the concatenated range list.
For example, the 5 index of that last example will be 8.

The problem is that the range can be huge (millions) and I don't want to turn that range into a list to get the x index. I need somehow to calculate the value of that x index without "opening" that range list

Tried for several hours to think of an algorithm to do that, the best solution I found includes using binary search to do that, which I think it is not the ideal way of doing so.

Any idea of how can I acheive that?

Answer 1

You can make a new range with the same start and end, and pack all steps to a new list. Now on each number from the range you can check if it matches any step. You can make this into a generator:

def steps_range(start, end, steps):
    for i in range(start, end):
        if any(i % x == 0 for x in steps):
            yield i

Now you can loop on that generator until you reach the relevant index. According to your example:

ranges = [range(0, 10, 2), range(0, 10, 3)]

start = ranges[0].start
end = ranges[0].stop
steps = [r.step for r in ranges]

target_index = 5

for i, num in enumerate(steps_range(start, end, steps)):
    print(num)
    if i == target_index:
        break

And this will print out:

0
2
3
4
6
8