A surprisingly interesting structure is the *extended multiplication table*, shown above for the numbers seven to ten. The algorithm for drawing these is straight forward – for an *n*-extended table, start out as if you were writing a “regular” multiplication table, but extend each row so that it gets as close to, without exceeding, *n*. Another way to think about it is to write out rows of “skip counting up to *n*” by *i* for integers* i* from 1 to *n*.

This is called an extended multiplication table since it contains a “traditional” multiplication table inside it. The 12-extended table below contains a traditional 3×3 multiplication table.

It turns out that 1 appears in an extended table once, and prime numbers appear exactly twice (once in the first column, and once in the first row). In general, for a natural number *n*, how many times does *n* appear in the *n*-extended table?

Before looking at that question, you might want to think about finding easier ways to draw the tables. Drawing out these tables by hand can be tedious – a simple program or spreadsheet might be easier. You can use Fathom, for example, to create the table data and draw it in the collections display. Create a slider *m* and the attributes listed in the table below (click on the image to see a larger version).

Modify the collection display attributes to draw the tables in the collection box. By adding lots of cases and using the slider m to filter out the ones you don’t need, you can vary the size of the table easily.

“how many times does n appear in the n-extended table?”

# of occurrances of *n* in the *n*-extended table = # of nodes in the factor lattice *Fn*

You can also recast both of these questions (how many occurances of n in the n-extended table, and how many nodesin the Fn factor lattice) as a combinatorial “balls in urns” problem.

Consider a set of colored balls where there are m different colours, where there are ki balls of color i, where i ranges from 1 to m. This would give a total number of balls equal to k1+k2+…+km. Suppose you were to distribute these balls in two urns. How many different distributions would there be? Using some counting techniques, you will find that the answer is (k1+1)*(k2+1)*…*(km+1).

How is this connected to the other problems? Consider the prime factorization of the number. For each prime, choose a colour, and for each occurance of the prime in the factorization, add a new ball of that color. For example for 12 = 3*3*2, choose two colours – say blue=3 and red=2. Since 3 occurs twice and 2 occurs once, there should be two blue balls and one red ball. Now consider distributing these balls in two urns. It turns out that you get (2+1)*(1+1) = 6 possibilities. This is the same number of times 12 occurs in the 12-extended table, and the same number of nodes in the 12-factor lattice. The image below shows the 12-extended table, the 12-factor lattice, and the “ball and urn problem” for the numer 12.

For a number* n* with the prime factorization:

The answer to all three questions is given by:

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to dan.mackinnon*****