Help coming up with a optimal function

Question

I am working on solving this problem: https://open.kattis.com/problems/tractor

Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a terrible driver, and can only move according to the following rules:

Each of her movements is in the same direction as either the positive x-axis or the positive y-axis. Her nth movement takes her $2^{n−1}$ units forward in her chosen direction. (On her first movement, n=1, so she moves 1 unit.) Farmer John’s farm is on the coordinate plane, in the shape of a rectangle with corners at (0,0), (A,0), (0,B) and (A,B). If Bessie starts at (0,0), how many points inside the farm, including the boundary, could she reach?

I believe I have reduced the problem to the following:

Consider a set $X$ such that $X =\{ (a,b) \in \mathbb{N}^2 | \exists n \in \mathbb{N} (a+b = 2^n-1) \} $. The points in this set fall on the line $y = -x + 2^n $ for all $n \in \mathbb{N}$ (and also $(0,0)$).

Given $(A,B)$, return $|\{ (a,b) \in X | (a \le A \land b \le B) \}|$.

I feel like this can be done quite efficiently by calculating the value of an elementary function, but I am drawing a blank here. My initial approach involved summing along the larger of $A$ and $B$, but I couldn't quite get it right--and it'd be much too slow for maximum inputs: $1 < A, B < 10^8$.

Any insights or hints would be much appreciated.

Answer 1

Suppose $B \le A$ and the farm is the points $(x,y)$ where $0\le x \le A$ and $0 \le y \le B.$ Set up a function $g(m,n)$ which counts the number of integers $w$ of the form $2^k-1$ for which $m \le w \le n.$ This should be simple based on log base 2, which if that is denoted $\lg(x)$ gives (I think, but check it) that $g(m,n)$ is the floor of $\lg(n+2)$ minus the ceiling of $\lg(m+1).$

Note now that, starting from the left of the rectangular field, the lengths of the downward diagonals go $1,2,\cdots,A$ for the diagonals of sum $0,1,\cdots A-1$ respectively. In this region, each of the $g(0,A-1)$ diagonals that count toward the sum contributes $2^k$ toward the total count. That sum may be possible to express in closed form, but even if not it can likely be computed quickly.

The diagonals after that have the constant length $A+1$, for each of the diagonals from the $A$ to the $B$ diagonal. In this region we have a simple computation, namely $(A+1)\cdot g(A,B).$ In the final region the diagonals start decreasing by $1$ each time, and a similar calculation is needed to the initial part where diagonal lengths are increasing by $1$ each time. Diagonal $B+1$ has length $A$, and so on, up to the final diagonal $A+B$ having length $1$. I think each diagonal which counts contributes $A+B-(2^k-1)-1$ to the count. Again, maybe a closed form can be worked out for this last "triangular" section of the field.