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)
```

# 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)))
```

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

`(`of the polynomial multiplied together.**x**+yk)
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!

This comment has been removed by a blog administrator.

ReplyDelete