Later data often show patterns better than early data, so extend your table of partial sums a bit:
$$\begin{array}{rcc}
n:&1&2&3&4&5&6&7&8&9\\
s_n:&1&-1&3&-5&11&-21&43&-85&171
\end{array}$$
Ignoring the signs, it appears that the numbers in the bottom line are approximately doubling each time. Moreover, still ignoring signs, adjacent partial sums add up to a power of $2$: $|s_1|+|s_2|=2^1$, $|s_2|+|s_3|=2^2$, $|s_3|+|s_4|=2^3$, and apparently in general $|s_n|+|s_{n+1}|=2^n$. (If you go back to the definition of the partial sums, you’ll see why this happens.)
If $|s_n|+|s_{n+1}|=2^n$ and $|s_{n+1}|\approx 2|s_n|$, then $3|s_n|\approx 2^n$; this suggests that we should compare $3|s_n|$ with $2^n$:
$$\begin{array}{rcc}
n:&1&2&3&4&5&6&7&8&9\\
s_n:&1&-1&3&-5&11&-21&43&-85&171\\
3|s_n|:&3&3&9&15&33&63&129&255&513\\
2^n:&2&4&8&16&32&64&128&256&512
\end{array}$$
That pattern’s pretty clear: apparently $3|s_n|=2^n+1$ if $n$ is odd, and $3|s_n|=2^n-1$ if $n$ is even. Those cases can be combined as $3|s_n|=2^n+(-1)^{n+1}$, since $(-1)^{n+1}$ is $1$ when $n$ is odd and $-1$ when $n$ is even. And the algebraic sign of $s_n$ appears to be that of $(-1)^{n+1}$, so if these patterns are real,
$$\begin{align*}
s_n&=\frac{(-1)^{n+1}}3\left(2^n+(-1)^{n+1}\right)\\
&=\frac{(-1)^{n+1}2^n}3+\frac{(-1)^{2n+2}}3\\
&=\frac{(-1)^{n+1}2^n+1}3\\
&=\frac{1-(-2)^n}3\;.
\end{align*}$$
This result can then be proved by mathematical induction, but I suspect that you’re not expected to go that far.
If you’ve already learned the summation formula for finite geometric series, you can apply it to get $s_n$ without looking at any patterns at all, and it’s something that you should learn as soon as possible if you don’t already know it. However, skill at pattern-recognition is useful anyway, so I thought that it might be useful to see how the problem can be attacked in that way as well.
Disclaimer: This isn't a 100% complete answer, but for the case that I need it for, it works. Maybe someone with additional ideas can improve it...
One can make some progress by looking at different possible special cases:
If $P*r<2^{63}$, there is no problem with overflows to begin with, so we can just calculate the answer directly as $p=\lfloor P*r/R \rfloor$. The only thing we need to do is to perform the check as $P<\lfloor2^{63}/r \rfloor$ instead to allow for a false result without overflow.
To cover the other case, one can do the following transformation:
$$
p=\lfloor P*r/R \rfloor= \bigg\lfloor\frac{P}{R/r}\bigg\rfloor=\bigg\lfloor\frac{P}{\lfloor R/r \rfloor + (R\bmod{r})/r}\bigg\rfloor
$$
$$
=\bigg\lfloor\frac{P}{\lfloor R/r \rfloor}-\frac{P(R\bmod{r})/r}{\lfloor R/r \rfloor(R/r)}\bigg\rfloor=\Bigg\lfloor\bigg\lfloor\frac{P}{\lfloor R/r\rfloor}\bigg\rfloor + \frac{P\bmod{\lfloor R/r\rfloor}}{\lfloor R/r\rfloor}-\frac{P(R\bmod{r})}{R\lfloor R/r \rfloor}\Bigg\rfloor
$$
$$
=\bigg\lfloor\frac{P}{\lfloor R/r\rfloor}\bigg\rfloor + \Bigg\lfloor\frac{P\bmod{\lfloor R/r\rfloor}}{\lfloor R/r\rfloor}-\frac{P}{R}\frac{R\bmod{r}}{\lfloor R/r \rfloor}\Bigg\rfloor
$$
The first term in the sum can be calculated directly without overflow issues. The second half after the '$+$' - sign is a little more difficult. But, looking at it, one realizes the following: The fraction to the left of the '$-$' - sign is always between $\ge 0$ and $<1$. Also: $0 \le P/R < 1$. So, we can look at two different special cases here:
- If $R\ge r^2$, the entire part to the right of the '$+$' - sign can only be either $0$ or $-1$.
- Otherwise, things could get more complicated...
Luckily, in my application, I know for a fact, that $R\ge r^2$ is always true. Therefore, for me, the answer is:
$$
p = \left\{\begin{array}{1 1}\lfloor (P*r)/R \rfloor & \quad \text{if $P<\lfloor2^{63}/r \rfloor$} \\ \lfloor P/\lfloor R/r\rfloor \rfloor \;[-1] & \quad \text{if $P\ge \lfloor2^{63}/r \rfloor$ and $R\ge r^2$} \\ \text{here be dragons} & \quad \text{if $P\ge \lfloor2^{63}/r \rfloor$ and $R<r^2$} \end{array} \right.\
$$
Here, $[-1]$ indicates that I only subract -1 in some cases, which I check by first leaving it out, testing the value of $p$ I get and then putting it in if I need it.
In the third case, one could use an arbitrary precision approach (c.f. GMP) and calculate the answer by doing long division as suggested by MvG. But maybe someone can find a more elegant way to slay the dragons for completeness... ;) Otherwise, if I have time a little later, I (or someone else) might add the formula for implementing the long division.
Best Answer
$a_n=(1/2)(1+(-1)^{n+1})$, $n=0,1,2,.....$