How to find the ith element in two merged arithmetic progressions?

55 Views Asked by At

Suppose we have two sequences:

$a_i=ai, b_i=bi$ where $a>0, b>0, i\in\mathbb{N}, a\in\mathbb{R}, b\in\mathbb{R}$

We then define $u_i$ the result of merging the two sequences such that all elements come in order.

For example for $a=2$ and $b=3$:

$u_i=0,0,2,3,4,6,6,8,9,10,12,12,14,15,16,18,18,20,21,\ldots$ OEIS

I have came up the following Python algorithm to find $u_i$ in $O(1)$:

import math

def find(i, a, b):
    freq = a * b / (a + b)
    n = freq * (i - 1)
    
    guess_a = a * math.ceil(n / a)
    guess_b = b * math.ceil(n / b)
    
    return min(guess_a, guess_b)

However, I tried extending this to $a_i=ai+c$ where $c\in\mathbb{R}$, but I wasn't able to find any algorithm that works in $O(1)$. The closest I got is this:

import math

def find(i, a, b, c, x = ???):
    freq = a * b / (a + b)
    n = x + freq * (i - 1)
    
    guess_a = a * math.ceil((n - c) / a) + c
    guess_b = b * math.ceil(n / b)
    
    return min(guess_a, guess_b)

But I am unable to analytically find correct values for x without guessing.