# Division by $2p+1$

Can $\left\lfloor{\dfrac{x}{2p+1}} \right\rfloor$ be expressed in terms of $\left\lfloor{\dfrac{x}{p}} \right\rfloor$ for prime $p$?

How to divide by $2p+1$ by only using division by $p$?

EDIT: The above formulation is wrong. I meant "expressed in terms" in a sense broader that "a function that takes $\left\lfloor{\dfrac{x}{p}} \right\rfloor$ as an argument.

Different version: let $0\leq a,b < 2p+1$ ($a,b$ known integers) and $x=ab$. How to divide $x$ by $2p+1$ in a way cheaper than just dividing by $2p+1$? Dividing by $p$ is cheaper than dividing by $2p+1$. It doesn't have to be a formula, algorithm is also ok.

-
Is $x$ necessarily an integer, or could it be fractional? – MJD Jun 20 '12 at 16:29
$x$ is an integer and $x<(2p+1)^2$. – asmith Jun 20 '12 at 16:34

$$\frac{x}{2p+1} = \frac{x}{2p} \frac{1}{1+1/(2p)} = \sum_{j=0}^\infty (-1)^j \frac{x}{(2p)^{j+1}}$$ For $\left\lfloor \dfrac{x}{2p+1} \right\rfloor$, you can stop the series if you come to a point where further terms can't make a difference (which should happen unless $x$ is an integer multiple of $2p+1$). Thus if $$S_N = \sum_{j=0}^N (-1)^j \dfrac{x}{(2p)^{j+1}}$$ $\left\lfloor \dfrac{x}{2p+1} \right\rfloor = \left\lfloor S_N \right\rfloor$ if $N$ is even and $x/(2p)^{N+2} < S_N - \lfloor S_N \rfloor$ or $N$ is odd and $x/(2p)^{N+2} < \lceil S_N \rceil - S_N$.

-
This is just the old trick of reducing division by $11$ to division by $10$ - see my answer. – Bill Dubuque Jun 20 '12 at 19:28

I don't think it can, in general. By the time you get $\lfloor{x\over p}\rfloor$, information has already been lost that was required in order to know $\left\lfloor{x\over 2p+1}\right\rfloor$.

Say for example that you had $p=2$. You need an expression for $\left\lfloor{x\over 2p+1}\right\rfloor = \left\lfloor{x\over 5}\right\rfloor$ that yields 0 when $x=4$ and 1 when $x=5$. But no function of $\left\lfloor{x\over 2}\right\rfloor$ can do this, because $\left\lfloor{x\over 2}\right\rfloor = 2$ for both $x=4$ and $x=5$.

-
+1 I guess the natural question would be "does it work for odd primes?" but the reasoning seems to work fine anyway. – Simon Markett Jun 20 '12 at 16:57
I was imprecise. I didn't mean a function of $floor(x/p)$, but a function that doesn't explicitly use division by $2p+1$. – asmith Jun 20 '12 at 17:00
@simon It's easy to find examples for any prime $p$. We want $x_1$ and $x_2$ such that $\lfloor x_1/p \rfloor = \lfloor x_2/p \rfloor$ but $\lfloor x_1/(2p+1) \rfloor \ne \lfloor x_2/(2p+1) \rfloor$. So take $x_1=2p$ and $x_2=2p+1$. – MJD Jun 20 '12 at 17:06
See my edit.... – asmith Jun 20 '12 at 17:07
@MarkDominus I think asmith is looking for something along the lines of the well-known division by 3 algorithm using bitshifting. Here's a reference that goes into some detail into the $p=2$ case: hackersdelight.org/divcMore.pdf – Erick Wong Jun 20 '12 at 17:38

Hint $\$ Reverse engineer this old trick that reduces dividing by $11$ to dividing by $10$.

$\ \ \begin{eqnarray}13717.4\, -\, 1371.74\, &=&\, 12345.66_{\phantom{M^{M^M}}} \\ \Rightarrow\quad \dfrac{137174}{11}\, &=&\, 12345.66 + 123.4566 + 1.234566 + 0.01234566+\,\cdots \\ &=&\, 12470.36... \end{eqnarray}$

-