Mainly Tech projects on Python and Electronic Design Automation.

Thursday, July 10, 2014

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)PolynomialOEIS Description
m(2,k)(k+1)Positive integers A000027
m(3,k)(k+1)*(k+2)/2Triangular numbers A000217
m(4,k)(k+1)*(k+1)Squares A000290
m(5,k)(k+1)(k+2)(2*(k+1)+1)/6Square pyramidal numbers A000330
m(6,k)(k+1)*2(k+2)/2Pentagonal pyramidal numbers A002411
m(7,k)(k+1)(2+k)(3+k)(1+3(k+1))/244-dimensional pyramidal numbers A001296
m(8,k)(k+1)^2(k+2)(k+3)/64-dimensional figurate numbers: A002417
m(9,k)((k+1)*(k+2)/2)^2Sum of first n cubes; or n-th triangular number squared A000537
m(10,k)(k+1)*2(k+2)(2k+3)/6A108678
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:
nk**0k**1k**2k**3k**4
211---
313/21/2--
4121--
5113/63/21/3-
615/221/2-
7131/1219/811/121/8
8117/617/67/61/6
91313/43/21/4
10119/611/311/61/3


nrearranged 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:

shortformfactored polynomialAlternate 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!

No comments:

Post a Comment

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive