Подсчет количества координат в гиперкубе

Question

В N-мерной сетке координаты ячейки обозначаются как X1, X2, ..., XN.Любая ячейка с отрицательной координатой окрашивается в белый цвет.Исходная ячейка (ячейка со всеми нулевыми координатами) окрашена в черный цвет.Цвет ячейки в (X1, X2, ..., XN) зависит от N ячеек с координатами (X1-1, X2, ..., XN), (X1, X2-1, ..., XN), ...., (X1, X2, ..., XN-1).Ячейка окрашивается в белый цвет, если и только если число черных ячеек среди этих N координат является четным, в противном случае ячейка окрашивается в черный цвет.

Теперь, учитывая начальную и конечную координаты субгиперкуба.Все координаты будут неотрицательными целыми числами, для которых выполнен запрос.Мы должны вычислить, сколько гиперэлементов в этом суб-гиперкубе окрашены в черный цвет?

Пожалуйста, предложите мне подсказку, ссылку или что-нибудь, что может помочь мне решить эту проблему.

Answer 1

Это правило приводит к хорошо известному фракталу - Треугольник Серпинского

Вот его изображение в 2D:

Answer 2

Алгоритм перебора:

fill the hypercube (the needed part) with value 'unknown'.
color[00000] = 1  #black

sum = 0
for each cell in sub-hypercube:
   sum += getcolor(cell)
   return sum

getcolor(cell):
   if color[cell] == unknown
      c = 0  #white
      for each neighbour cell in decreasing direction within non-negative boundary:
          c = c xor getcolor(neighbour)
      color[cell] = c
   return color[cell]