The first odd multiple of a number in a given range

Question

As a part of a programming problem I was solving, we were required to find the first offset of a range at which the number is a odd multiple of another number. For e.g: Take the range $100$ to $120$. Only the odd multiples here are taken for the offsets - so offset 0 corresponds to 101, 1 to 103 and k to $100+2*k+1$ in general. Say we need to find the first odd multiple of 3 in this range - that would be 105. This corresponds to an offset of 2. So, I need to compute a function which can output these offsets, given the initial/ final number ($100/120$ here) in the range and the dividing number (3 in this case).

I found a solution here which says the function should be $(-1/2 × (L + 1 + Pk))\mod Pk$ , where L:start of range, Pk: dividing number (3 in our e.g). I'm unable to understand how this function is the right answer. Could some one please shed some light here?

Note: The above function is explained to some extent by the author here, in the comments - but I still don't get it.

Answer 1

it says $$Q_k = (-1/2x(L+1+P_k)) mod P_k$$ let take case of 100 to 120 and $P_k$ = 3
then, L = 100 => L+1+$P_k$ = 100+1+3 = 104, => -1/2*104 = -52
now, a = b mod n means, a-b is a multiple of n
that means, $Q_k$ + 52 is a multiple of 3.
remainder(52/3) = 1
=>1+2 = 3
=>$Q_k$ = 2
least number greater than or equal to 52, which is divisible by 3 is 54.
54-52 = 2 => $Q_k$ = 2

Answer 2

Most programming languages have a "mod" operator to calculate the remainder of a division of two integers. Therefore let's assume that $L$ and $n$ are positive integers and let's define the numbers $x$ and $y$ by $$\begin{align} x&:=(L+n-1)\mod 2n\\ y&:=L+2n-1-x \end{align}$$ We see that $L+n-1-x$ is an even multiple of $n$ and so $n+L+n-1-x=y$ is an odd multiple of $n$. Also, since $0 \le x <= 2n-1$, we see that $L \le y \le L+2n-1$, so $y$ must be the odd multiple of $n$ we're looking for (if $y$ does not exceed the range).

To calculate the "offset" of $y$ in the range, we have to solve $L+2k+1=y$ for $k$, so $$ 2k+1=2n-1-x \Leftrightarrow k=n-1-\frac{x}{2} $$ This can only be an integer if $x$ is even, for example if $L$ even and $n$ odd (like in your example).

To apply this to your example ($L=100$, $n=3$), we have $L+n-1=102\equiv0\pmod6$, so $x=0$ and $y=100+6-1-x=105$, the offset $k$ is $k=n-1-\frac{0}{2}=3-1=2$.