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*