Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
The number of ways to write $n$ as a product of two numbers is the number of divisors of $n$, much-studied in Number Theory, and sometimes denoted $d(n)$, sometimes $\tau(n)$. What you want is not quite this, since you are counting order and side of equation, but it should not be hard to express what you want in terms of $d(n)$. Then what you really want is the summatory function, which will be related to $\sum_1^Nd(n)$. That, too, is much studied and is known to be approximately $N\log N$. –  Gerry Myerson Sep 24 '12 at 1:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.