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
    Note that the `0`s in the ASCII representation represent `1`s and the dots represent `0`s.2011-08-05
  • 0
    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 (http://oeis.org/A064194)2011-08-05

1 Answers 1