0
$\begingroup$

There is a 3D grid with cells for which we define its value (0 or 1) as F(i,j,k)=F(i-1,j,k) XOR F(i,j-1,k) XOR F(i,j,k-1), base cases are F(0,0,0)=1 and F(x,y,z)=0 for x < 0 or y < 0 or z < 0 (if at least one parameter is negative).
We want to count amount of cells with F()=1 in the cube with corners (0,0,0) and (N, M, K). Dimensions are about 10^9.

I'm looking for the fast approach on this problem. This function produces interesting picture, you may find it here.

  • 0
    The two-dimensional analogue of this pro$b$lem, with squares -- how many 1-cells are there in the upper-left N-by-N square in the first slice? -- is apparently a known sequence (http://oeis.org/A064194)2011-08-05

1 Answers 1

1

First things first:

$F(i,j,k) = 1$ if and only if the pairwise bitwise-ands of $i$, $j$ and $k$ are all $0$.

Proof: (by induction on $i + j + k$)

If $i + j + k = 0$, then $i=j=k=0$, and so the pairwise bitwise-ands of $i$, $j$ and $k$ are all $0$ and $F(i,j,k)=1$.

Suppose now that $i + j + k > 0$ and the pairwise bitwise-ands of $i$, $j$ and $k$ are all $0$. Note that not all of $i$, $j$ and $k$ are $0$. Thus at least one of $i$, $j$ and $k$ has a $1$ in its binary expansion. Since all of the $1$'s in the binary expansions of $i$, $j$ and $k$ occur in the lowest place, there is exactly one of $i$, $j$ and $k$ that has a least-significant $1$ in its binary expansion. Let us suppose that that is $i$ and that it contains a $1$ corresponding to $2^z$. Either $j = 0$, or $j-1$ will have a $1$ corresponding to $2^z$. Either way, $F(i,j-1,k) = 0$. Similarly, $F(i,j,k-1) = 0$. Finally, $i-1$ is similar to the bitwise-exclusive or of $1$ with $2^{z+1}-1$. Since this only changes bits that are not in $j$ or $k$, $F(i-1,j,k) = 1$, and so $F(i,j,k) = 1$.

Finally, suppose that $i + j + k > 0$ and that the bitwise-and of $i$ and $j$ is non-zero. Then in this case we know that $F(i,j,k-1) = 0$, and so we are just required to prove that $F(i-1,j,k) =$ $F(i,j-1,k)$. Since they are both in $\{0,1\}$, it follows that we need to show that if either of them is equal to $1$, then so is the other. To that end, let us suppose that $F(i-1,j,k) = 1$, and we will argue that $F(i,j-1,k)$ must also be equal to $1$.

Since $i$ and $j$ have at least one bit in common, but $i-1$ and $j$ do not, the least significant bit of $i$ must be equal to the least significant bit of $j$ and must be the only bit they have in common. Furthermore, $k$ must have no bits that low down. Thus it follows that $F(i,j-1,k)$ will equal $1$.

QED

Thus you are asking: How many $0 \le i \le N, 0 \le j \le M$ and $0 \le k \le K$ have pairwise bitwise-ands equal to $0$.

Let this answer be $f(N, M, K)$.

Note that $i$, $j$, $k$ must be all even, or exactly one of them must be odd.

The number with $i, j, k$ all even is equal to $f(\lfloor N/2 \rfloor, \lfloor M/2 \rfloor, \lfloor K/2 \rfloor)$. The number with $i$ odd and $j, k$ both even is equal to $f(\lfloor (N - 1)/2 \rfloor, \lfloor M/2 \rfloor, \lfloor K/2 \rfloor)$, and so on.

Thus $\begin{align*}f(N, M, K) &= f(\lfloor N/2 \rfloor, \lfloor M/2 \rfloor, \lfloor K/2 \rfloor)\\ &+ f(\lfloor (N - 1)/2 \rfloor, \lfloor M/2 \rfloor, \lfloor K/2 \rfloor)\\ &+ f(\lfloor N/2 \rfloor, \lfloor (M-1)/2 \rfloor, \lfloor K/2 \rfloor)\\ &+ f(\lfloor N/2 \rfloor, \lfloor M/2 \rfloor, \lfloor (K-1)/2 \rfloor). \end{align*}$ Using this inductive definition and caching (and stopping at $f(0,0,0) = 1$) you can calculate $f(N, M, K)$ in $O(\max(\log N, \log M, \log K))$.

  • 0
    The formula for $f(N,M,K)$ is off slightly: the number of even integers in $[0,n]$ is $\lceil (n+1)/2\rceil$, and the number of odd integers is $\lfloor (n+1)/2\rfloor$.2011-08-25