Let's say we have a list of integers from 0
to (n-1)
, where n > 0
:
0, 1, 2, 3, 4, ..., n - 2, n-1
How many different ways are there to multiply two numbers together to produce the same product, when the order matters?
For example, let's say n=7
...
Here are some examples of products which are equal to each other:
order matters: 0 * 0 = 0 * 3 0 * 0 = 3 * 0 0 * 3 = 0 * 0 3 * 0 = 0 * 0 zeros: 0 * 6 = 0 * 2 4 * 0 = 0 * 0 0 * 0 = 0 * 0 same numbers on both sides: 1 * 6 = 6 * 1 1 * 6 = 1 * 6 6 * 1 = 6 * 1 6 * 1 = 1 * 6 6 * 6 = 6 * 6 more complex products: 2 * 3 = 6 * 1 4 * 3 = 6 * 2 2 * 2 = 4 * 1
I figured out the way to calculate how many permutations involve zeros: (e.g. 0 * 5 = 3 * 0
)
(A) 4n^2 - 4n + 1
Calculating how many involve the same non-zero numbers on both sides is easy too: (e.g. 1 * 6 = 6 * 1
)
(B) 2n^2 - 5n + 3
The only complicated part is figuring out different ways to generate the same product when it doesn't involve a zero and doesn't have the same numbers on both sides of the equation:
For example, if n=7
, these are the permutations that would be more difficult to calculate:
4's: 1 * 4 = 2 * 2 4 * 1 = 2 * 2 2 * 2 = 1 * 4 2 * 2 = 4 * 1 6's: 2 * 3 = 1 * 6 3 * 2 = 1 * 6 2 * 3 = 6 * 1 3 * 2 = 6 * 1 1 * 6 = 2 * 3 1 * 6 = 3 * 2 6 * 1 = 2 * 3 6 * 1 = 3 * 2 12's: 3 * 4 = 6 * 2 (7 other permutations involving 3/4 and 6/2 omitted)
Notice that when the product involves 3 distinct numbers (as in the case of 1 * 4 = 2 * 2
), there are 4 (2^2
) different permutations for the same product; and there are 8 (2^3
) permutations when all 4 numbers are unique.
I started working out the first few by hand by combining formulas A and B and then manually counting how many complex product permutations there are (C):
+----+-----+-----+----+-------+----------------------------------------+ | n | A | B | C | Total | Note: products added | +----+-----+-----+----+-------+----------------------------------------+ | 2 | 9 | 1 | 0 | 10 | - | | 3 | 25 | 6 | 0 | 31 | - | | 4 | 49 | 15 | 0 | 64 | - | | 5 | 81 | 28 | 4 | 113 | 1*4=2*2 | | 6 | 121 | 45 | 4 | 170 | - | | 7 | 169 | 66 | 20 | 255 | 1*6=2*3, 2*6=3*4 | | 8 | 225 | 91 | 20 | 336 | - | | 9 | 289 | 120 | 48 | 457 | 1*8=2*4, 2*8=3*6, 2*8=4*4, 3*8=4*6 | | 10 | 361 | 153 | 52 | 566 | 1*9=3*3 | | 11 | 441 | 190 | 84 | 715 | 1*10=2*5, 2*10=4*5, 3*10=5*6, 4*10=5*8 | +----+-----+-----+----+-------+----------------------------------------+
What I would like is a formula for calculating C, I would then be able to calculate the Total easily by combining all 3 formulas. Is there any way to create a function or pattern to calculate C?