Unique numbers in multiplication tables

 I answered a Stack overflow question that asked for the number of unique numbers in an n-by-n multiplication table and got it horribly wrong.

I decided to look into the maths of it a little further last night and now know a bit more about the question but still have no formula for generating the number of distinct integers in an n-by-n multiplication table.

Table generator

In [1]:

def ptable(n):
    width = len(str(n*n))
    nrange = range(1, n+1)
    for i in nrange:
        print(' '.join('%*i' % (width, i * j) for j in nrange))

for n in range(1, 4):
    n2 = 2**n
    print('\n%i-by-%i times table' % (n2, n2))
    ptable(n2)

    

2-by-2 times table
1 2
2 4

4-by-4 times table
 1  2  3  4
 2  4  6  8
 3  6  9 12
 4  8 12 16

8-by-8 times table
 1  2  3  4  5  6  7  8
 2  4  6  8 10 12 14 16
 3  6  9 12 15 18 21 24
 4  8 12 16 20 24 28 32
 5 10 15 20 25 30 35 40
 6 12 18 24 30 36 42 48
 7 14 21 28 35 42 49 56
 8 16 24 32 40 48 56 64

Unique number counter

The only way i could think of counting the number of unique integers is to generate the table then get the size of the set of the tables numbers:

In [2]:

def mult_table_numbs(n):
    nrange = range(1, n+1)
    return len(set(n0 * n1 for n0 in nrange for n1 in nrange))

for n in range(1,11):
    print('%2i: %i' % (n, mult_table_numbs(n)))

 1: 1
 2: 3
 3: 6
 4: 9
 5: 14
 6: 18
 7: 25
 8: 30
 9: 36
10: 42

So for n of 4 there are 9 distinct numbers counted.

Stick the numbers 1,3,6,9,14,18,25,30,36,42 into OEIS and the integer sequence search engine indeed recognises it as A027424

I simplified. I actually first used Pythons itertools.product and reduce. for product I had to use product(range(1,n+1), repeat=2). The repeat=2 is because it is for a two-dimensional multiplication table.

That got me thinking and I quickly realised that I could create a k-dimensional multiplication table unique number counter by setting the repeat to a new argument k with default value 2.

The k-dimensional multiplication table unique number counter

In [3]:

from itertools import product
from functools import reduce

mul = int.__mul__

def mult_table_numbers(n, k=2):
    return len(set(reduce(mul, p, 1) 
                   for p in product(range(1,n+1), repeat=k)))

Dimension hopping

OEIS mentioned no formulae for generating the unique number counts except by direct counting so I thought "what if I explore the dimensions k as well as varying n"?

print('n,k=2.. matrix')

for n in range(2,13):

    print('%2i: %s' % (n, repr([mult_table_numbers(n, k)

                                for k in range(2,10)]).replace(' ','')))

The above takes several tens of minutes to run but finally gives the following results:

n,k=2.. matrix

 2: [3,4,5,6,7,8,9,10]

 3: [6,10,15,21,28,36,45,55]

 4: [9,16,25,36,49,64,81,100]

 5: [14,30,55,91,140,204,285,385]

 6: [18,40,75,126,196,288,405,550]

 7: [25,65,140,266,462,750,1155,1705]

 8: [30,80,175,336,588,960,1485,2200]

 9: [36,100,225,441,784,1296,2025,3025]

10: [42,120,275,546,980,1632,2565,3850]

The 2: [3,4,5,6,7,8,9,10] line reads that for n=2: a 2-dimensional multiplication table has 3 distinct numbers; a 3D table 4; a 5D table 6 distinct numbers, and so on...

Now each line with its series of distinct numbers for different k- dimensions is itself a sequence. The n=2 line is the sequence k+1 for example. I could look up the sequences in OEIS and extract the formulas for each row. If I could then link the formulas for different rows I might be able to finally generate a formula for the unique count, lets call it m(n, k) for dimension k=2.

OEIS extraction

Time on OEIS revealed the following information:

m(n,k)	Polynomial	OEIS Description
m(2,k)	(k+1)	Positive integers A000027
m(3,k)	(k+1)*(k+2)/2	Triangular numbers A000217
m(4,k)	(k+1)*(k+1)	Squares A000290
m(5,k)	(k+1)(k+2)(2*(k+1)+1)/6	Square pyramidal numbers A000330
m(6,k)	(k+1)*2(k+2)/2	Pentagonal pyramidal numbers A002411
m(7,k)	(k+1)(2+k)(3+k)(1+3(k+1))/24	4-dimensional pyramidal numbers A001296
m(8,k)	(k+1)^2(k+2)(k+3)/6	4-dimensional figurate numbers: A002417
m(9,k)	((k+1)*(k+2)/2)^2	Sum of first n cubes; or n-th triangular number squared A000537
m(10,k)	(k+1)*2(k+2)(2k+3)/6	A108678

Whilst playing around with the polynomials using SymPy Gamma and the Wolfram sites I rearranged them to help find patterns

Constant multipliers for the polynomials above (when expanded)

I could find no patterns in this:

n	k**0	k**1	k**2	k**3	k**4
2	1	1	-	-	-
3	1	3/2	1/2	-	-
4	1	2	1	-	-
5	1	13/6	3/2	1/3	-
6	1	5/2	2	1/2	-
7	1	31/12	19/8	11/12	1/8
8	1	17/6	17/6	7/6	1/6
9	1	3	13/4	3/2	1/4
10	1	19/6	11/3	11/6	1/3

n	rearranged polynomial for m(n,k)
1	(1/(1)) * (1+0k)
2	(1/(1)) * (1+k)
3	(1/(1*2)) * (1+k)(2+k)
4	(1/(1*1)) * (1+k)(1+k)
5	(1/(1*2*3)) * (1+k)(2+k)(3+2k)
6	(1/(1*2*1)) * (1+k)(2+k)(1+k)
7	(1/(1*2*3*4)) * (1+k)(2+k)(3+k)(4+3k)
8	(1/(1*2*1*3)) * (1+k)(2+k)(1+k)(3+k)
9	(1/(1*2*1*2)) * (1+k)(2+k)(1+k)(2+k)
10	(1/(1*2*1*3)) * (1+k)(2+k)(1+k)(3+2k)

There are some patterns in the above. the divisor is always all the constant terms (x+yk) of the polynomial multiplied together.

I then saw that some later polynomials were multiples of earlier ones so decided on using the shorthand @n for m(n,k) to produce the following:

shortform	factored polynomial	Alternate factorisation
@1	(1+0k)
@2	(1+k)
@3	@2*(2+k) / 2
@4	@2*@2
@5	@3*(3+2k) / 3
@6	@2*@3
@7	@3*(3+k)(4+3k) / 6
@8	(@6 = @2*@3)*(3+k) / 3	@4*(2+k)(3+k) / 6
@9	(@6 = @2*@3)*(2+k) / 2	@3*@3
@10	(@6 = @2*@3)*(3+2k) / 3	@2*@5

Unfortunately I can see no pervasive patterns here either.

Conclusion

I've looked. I've enjoyed the journey, but I've still to find what I'm looking for!