# Go deh!

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!

#### 1 comment:

1. This comment has been removed by a blog administrator.