Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Note that the 0s in the ASCII representation represent 1s and the dots represent 0s. –  joriki Aug 5 '11 at 13:18
    
The two-dimensional analogue of this problem, 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 (oeis.org/A064194) –  Michael Lugo Aug 5 '11 at 14:50

1 Answer 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))$.

share|improve this answer
    
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$. –  Brian M. Scott Aug 25 '11 at 5:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.