On rectangles

While reading Cryptography: The Science of Secret Writing [1], the author makes a remark (p. 36) (without substantiating it further) that the number of possible distinct rectangles composed of n squares (a regular grid) is quite limited.

Mondrian_CompRYB

Unsubstantiated (or, more exactly, undemonstrated) claims usually bug me if the demonstration is not immediate. In this case, I determined fairly rapidly the solution, but I guess I would have liked something less vague than “increased in size does not necessarily provide greater possibilities for combination.” Let’s have a look at that problem.

The problem is as follows: given n, how many distinct rectangles with integer sides of surface n are there?

The first observation one must make is that the solution depends on the integer factorization of n. If n=1 then there’s obviously only one solution. If n is prime, then there are only two solutions: 1\times{n} and n\times{1}.

If n is composite, then the first side s must evenly divide n (and thus uniquely determine the other side, n/s). What are the admissible divisors s? Let

\pi_n=\{p_1,p_2,...,p_k\}

be the prime divisors of n, with multiplicities. For example, n=2520 yields

\pi_{2520}=\{2,2,2,3,3,5,7\}

which is readily verified.

Now, any side of length s is the product of a subset of \pi_n (with the empty subset understood as \{1\}); for example, for n=2520, s=2\times{2}\times{3}\times{3}\times{7} is cromulent. The other side is uniquely determined, and is 2\times{5}. Since one side is given by a subset and the other by the complement, we may have the idea that each subset corresponds to a bit-string:

\{2,2,2,3,3,5,7\}

\{0,1,1,1,1,0,1\}

yielding

\{2,2,3,3,7\}

This is sufficient to generate all permissible rectangles, but they are not all distinct just yet. This method does not permit to distinguish between

\{2,2,2,3,3,5,7\}

\{0,1,1,0,1,0,1\}

and, say,

\{2,2,2,3,3,5,7\}

\{1,0,1,1,0,0,1\}

…because both yield subsets whose products are the same: 2\times{2}\times{3}\times{7}.

We must then account for indistinguishable subsets; fortunately, it’s simple once we have multiplicities, the number of times each prime factor appears. We find:

M_{2520}=\{3,2,1,1\}

since 2520=2^3\times{}3^2\times{}5^1\times{}7^1. Let us now look at the relation between multiplicities and indistinguishable subsets. Let us just look at 2^3:

\{2,2,2\}

and the subsets (again, in “bitmask” notation”):

\{0,0,0\}=1

(a special case), then

\{0,0,1\}=2

\{0,1,0\}=2

\{1,0,0\}=2

and

\{0,1,1\}=4

\{1,0,1\}=4

\{1,1,0\}=4

and finally

\{1,1,1\}=8

There are 4 groups that yield distinct products. That’s m_1+1, or the multiplicity of the first prime factor plus one. The same applies to the other prime factors; and finally, the number of rectangles is given by

\displaystyle r(n)=\prod_{i=1}^{l}\left(m_i+1\right)

where m_i is the ith multiplicity.

*
* *

Let’s see how we can use what we found to compute automatically the number of rectangles in everybody’s favorite language: C++. First, let us write a simple integer factorization function:

std::vector<int> factor_integer(int x)
 {
  std::vector<int> factors;

  int t=2;
  while (t<=x)
   if (x % t==0)
    {
     x/=t;
     factors.push_back(t);
    }
   else
    if (t>2)
     t+=2;
    else 
     t++;

  return factors;
 }

(An already much better way would have been to use a sieve of some sort; but let us not get into that just now.) Multiplicities are most easily found:

std::vector<int> count_multiplicities(const std::vector<int> & factors)
{
  std::vector<int> multiplicities;
  int m=1;

  for (int i=0;i<factors.size();i++)
    if (factors[i]==factors[i+1])
     m++;
    else
     {
      multiplicities.push_back(m);
      m=1;
     }


  return multiplicities;
}

finally:

int count_rectangles( const std::vector<int> & multiplicities )
 {
  int n=1;

  for (int i=0;i<multiplicities.size();i++)
   n*=(multiplicities[i]+1);

  return n;
 }

Then, to unit-test the thing (because, yes, testing is
important), an alternate implementation:

int enumerate_rectangles(const std::vector<int> & factors)
{
  std::map<rectangle,bool> seen;

  int c=(1<<factors.size());
  for (int i=0;i<c;i++)
   {
    int h=1;
    int w=1;
    int mask=i;
    for (int b=0;b<factors.size();b++,mask>>=1)
     {
      if (mask & 1)
       h*=factors[b];
      else
       w*=factors[b];
     }

    seen[ rectangle(h,w) ] = true;
   }

  return seen.size();
}

Let us check:

void show(const std::vector<int> & v)
{
  for_each( v.begin(),
            v.end(),
            [](int x) { std::cout << " " << x; } );
  std::cout << std::endl;
}

////////////////////////////////////////
int main()
{
  const int n = 2*2*3*3*5*7*13; // or whatever

  std::vector<int> factors=factor_integer(n);
  std::vector<int> multiplicities=count_multiplicities(factors);

  std::cout << "factors:"; show(factors);
  std::cout << "multiplicities:"; show(multiplicities);

  int enumerated=enumerate_rectangles(factors);

  std::cout
   << "enumerated: " << enumerated << std::endl
   << "computed: " << count_rectangles(multiplicities) << std::endl;

  return 0;
}

Running the program, we find, for example:

factors: 2 2 3 3 5 7 13
multiplicities: 2 2 1 1 1
enumerated: 72
computed: 72

*
* *

So all this because of a careless, unsubstantiated statement in an old book; I really wish such characterization, even when moderately interesting, would be explained and well-demonstrated. But now that we have all that we need, let’s have a look at the asymptotic-ish behavior.

For n from 1 to 200000, if we plot the number of rectangles:

rectangles

The upper bound is \approx \frac{1}{2}\left(\lg n\right)^2. Well, there’s at most O(\lg n) factors in a number (being exactly so when it is a power of two), and counting the average multiplicities, we have a rather good fit. Therefore, we can say (in a manner as vague as the original author that started this digression of a blog entry) what the number of possible rectangles for a given n is \propto \frac{1}{2}\left(\lg n\right)^2.

[1] Laurence Dwight Smith — Cryptography: The Science of Secret Writing — Dover (1943)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: