0
$\begingroup$

I have created a computer program which creates every possible 2x2, 3x3, 4x4 and 5x5 pixel black and white image.

I know how to get the total possible number of images:

2x2 = 16
3x3 = 512
4x4 = 65536
5x5 = 33554432

Generally, 2^(n^2)

However, these images are not really unique. Some can be rotated by 90 degrees and will be the same as another image from the set. Essentially, every bitmap from the set can be rotated 4 times, and they will (usually) be a duplicate.

Example in a 4x4 image:

#...               ...#    ....        ....
....   will yield  ....    ....        ....
....               ....    ....        ....
....               .... ,  ...# , and  #...

I'm trying to determine how many cannot be rotated, because they are unique. For example, given a 4x4 pixel image, this image is "unique" through all 4 rotations:

.##.
#..#
#..#
.##.

Rotating this image will not be a duplicate. It is the only image that can be generated in such a way.

My program will determine those images that are 4-rotation unique and 2-rotation unique, eg:

##..               ..##    ##..        ..##
##..   will yield  ..##    ##..        ..##
..##               ##..    ..##        ##..
..##               ##.. ,  ..## , and  ##..

The first image can be rotated once to produce a duplicate, but the second rotation produces the same image. So, I refer to these as 2-rotation uniques.

What I'm trying to get to is a formula to determine the number of 4-rotation uniques and 2-rotation uniques given an arbitrary (square) image.

Here are the numbers I have so far:

2x2 => 2 (4-rotations), and 2 (2-rotations)
3x3 => 8 (4-rotations), and 24 (2-rotations)
4x4 => 16 (4-rotations), and 240 (2-rotations)
5x5 => 120 (4-rotations), and 8064 (2-rotations)

If every image could be rotated 4x times, then I could just divide the total number of possible images by 4. But, ideally, 2-and-4-rotation uniques should be accounted for.

So, I'd like to find a formula for determining the number of 4-rotation and 2-rotation unique images given a canvas of arbitrary size.

For example, a 1000x1000 B&X pixel image has 300,000 digit long count of uniques. My program is not capable of such large numbers. At these scales, I could possibly just divide by 4 and be OK with the result, but I can't escape the fact that there's a pattern in the growing number of 2-rotation and 4-rotation uniques.

I've tried a ton of different exponential and factorial formulas, but nothing gives.

Any ideas on how to proceed?

$\endgroup$
  • $\begingroup$ This sort of thing can be elegantly solved by considering group actions: consider an action of the group of rotations on the collection of bitmaps $\endgroup$ – Nick Peterson Sep 19 '18 at 4:33
4
$\begingroup$

We need to distinguish odd and even $n$, since for odd $n$ there's a central square and for even $n$ there isn't.

Except for the central square, all squares are part of an orbit of $4$ squares under the rotations. There are $\frac{n^2}4$ of these orbits for even $n$ and $\frac{n^2-1}4$ for odd $n$; the total number of orbits for odd $n$ including the orbit containing only the central square is $\frac{n^2-1}4+1=\frac{n^2+3}4=\left\lceil\frac{n^2}4\right\rceil$. To be invariant under all rotations by $\frac\pi2$, a pattern needs to be constant on each orbit. Thus there are

$$ 2^{\left\lceil\frac{n^2}4\right\rceil} $$

different patterns that are invariant under rotations by $\frac\pi2$, so the count for $n=5$ should be $128$ instead of $120$. Analogously, there are

$$ 2^{\left\lceil\frac{n^2}2\right\rceil} $$

different patterns that are invariant under rotations by $\pi$. This includes the ones that are invariant under rotations by $\frac\pi2$, so the number of patterns that are invariant under rotations by $\pi$ but not by $\frac\pi2$ is

$$ 2^{\left\lceil\frac{n^2}2\right\rceil}-2^{\left\lceil\frac{n^2}4\right\rceil} \;,$$

and the number of patterns that aren't invariant under any rotation is

$$ 2^{n^2}-2^{\left\lceil\frac{n^2}2\right\rceil}\;.$$

Thus, the total number of equivalence classes of patterns under rotations is

$$ \frac{2^{n^2}-2^{\left\lceil\frac{n^2}2\right\rceil}}4+\frac{2^{\left\lceil\frac{n^2}2\right\rceil}-2^{\left\lceil\frac{n^2}4\right\rceil}}2+2^{\left\lceil\frac{n^2}4\right\rceil}=2^{n^2-2}+2^{\left\lceil\frac{n^2}2\right\rceil-2}+2^{\left\lceil\frac{n^2}4\right\rceil-1}\;. $$

$\endgroup$
  • 1
    $\begingroup$ Many thanks for the fast response... and you are absolutely correct, 5x5 => 128 4x rotations! $\endgroup$ – Jupe Sep 19 '18 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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