If you shop at Amazon anyway, consider using this
link. We receive a few cents from each purchase. Thanks.
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
Send an e-mail with your
comments about this program (or anything else).
Here's a puzzle sent to me by a viewer who says it is from a
set of questions written by computer pioneer and inventor Sir Clive
Sinclair. They were published many years ago as "Mensa Steps" in a magazine,
perhaps "Design Technology" as the viewer recalls ,
"If you draw a nine by nine square, thus giving
yourself eighty-one small squares in total; how many rectangles can
you count in total? "
One of my standard problem solving strategies is to "simplify"; solve a
smaller version of the program and hope that it provides a clue to solving
the larger one. The program generates the number of rectangles for
grids from from 1x1 to 9x9. It does it in a nested loop by
summing all rectangle counts from 1x1 to NxN for each grid
size. We count rectangles of size H x V where H
and V represent horizontal and vertical dimensions and range from
1 to N. For each H there are H+1-A
rectangles across and for each V there are N+1-V
rectangles down. The total numer of rectangles is the sum of all
products (N+1-H)*(N+1-V) for all H and V combinations
from 1 to N.
I did not discover the generating function based solely on the results, but
if you search on the sequences of results (1,9,36,100,225,441 ...)
you'll find lots of fascinating information including the formula in the
Online Encyclopedia of Integer Sequences page at
Also notice that the numbers in the sequence are perfect squares of the
sequence 1,3,6,10,15.... These are called "triangular numbers"
with the property that the Nth member is the number of dots in an
equilateral triangle with N dots per side! (Think of 4th entry
for example, being represented by 10 bowling pins arranged in the
traditional triangle with 4 pins per side.) See
http://en.wikipedia.org/wiki/Squared_triangular_number for more
I was planning to post this program on the Beginner's page
since there are less than 20 lines of code, but decided on the Math Topics
section after recognizing the interesting math.
Running/Exploring the Program
|Created March 6,,2012
March 06, 2012