Let $x=2^6 3^4 5^2$, then how many distinct values of $|A-B|$ are possible where $A, B$ are the factors of $x$?

How to approach this problem?

  • $\begingroup$ Where did this problem come from? What have you tried so far? It's easy to establish an upper bound on the number of distinct values (how many factors of $x$ are there? If $N$ is the number of factors, how many ordered pairs of numbers $\lt N$ are there?), but 'coincidences' where two distinct pairs of factors $\langle A,B\rangle$ and $\langle C,D\rangle$ have the same difference can happen, and there's no immediately obvious way of tallying the coincidences except going through all the possibilities by hand. $\endgroup$ – Steven Stadnicki Jul 23 '12 at 16:43
  • 4
    $\begingroup$ Are you sure you aren't being asked to tally how many distinct values of $|A-B|$ are possible where $AB=x$? That would be a different (and much more easily manageable by hand) problem... $\endgroup$ – Steven Stadnicki Jul 23 '12 at 16:44
  • $\begingroup$ No, $AB$ doesn't necessarily equal to $x$. $\endgroup$ – Hyperbola Jul 23 '12 at 17:25

There are $7\times5\times3=105$ divisors of $x$. There are at most $\binom{105}{2}+1=5461$ non-negative differences among the elements. $\binom{105}{2}$ computes the number of pairs of distinct factors and $1$ is for $0$, the difference between a factor and itself. There may be fewer than this many because some differences may be repeated.

To compute the actual number of differences, one could use a program like Mathematica. I used this code

d = Divisors[2^6 3^4 5^2]; Length[Union[Abs[Flatten[Outer[Subtract, d, d]]]]]

to compute that there are $2856$ distinct non-negative differences.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.