5
$\begingroup$

How many order triple of positive integers (a,b,c) are there such that $a\leq b\leq c$ and $a\cdot b \cdot c \leq 1000$?
I have no idea how to attack this type of problem. Can anyone help. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ 1) Zero is not positive, and 2) if zero were allowed, there would be infinitely many solutions. $\endgroup$ – T. Linnell Jul 31 '17 at 9:50
  • 1
    $\begingroup$ What does $a.b.c$ mean? Multiplication? $\endgroup$ – user302982 Jul 31 '17 at 9:50
  • $\begingroup$ @sigmabe Yes it is multiplication. $\endgroup$ – rugi Jul 31 '17 at 10:00
1
$\begingroup$

It might help if you think about a slightly simpler problem - how many pairs of positive integers $b,c$ satisfy $bc \le n$ for $b \le c$ and $n$ being some other positive integer. You should be able to express this as a sum - find the number of possible values of $c$ for a given $b$, then sum over all possible values of $b$. Note that $b^{2} \le bc \le n$.

Then you just go the next step up - sum this over all possible values of $a$, with $n = 1000/a$. $a$ can only take one of a few values, which you can again find since $a^{3} \le abc \le 1000$. You should get a nested sum, which I believe you'd then just have to compute (but it might simplify).

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

In general, the number of positive integer solutions to $abc\le N$ with $a\le b\le c$ can be computed as

$$C(N)=\sum_{a=1}^{\lfloor\sqrt[3]{N}\rfloor}\sum_{b=a}^{\lfloor\sqrt{N/a}\rfloor}(\lfloor N/ab\rfloor-b+1)$$

Alternatively, let

$$T=\lfloor\sqrt[3]N\rfloor,\quad D=\sum_{n=1}^\sqrt{N}\left\lfloor{N\over n^2}\right\rfloor, \quad\text{and}\quad S=\sum_{n=1}^N\sigma(n)\left\lfloor{N\over n}\right\rfloor$$

where $\sigma(n)$ is the number of divisors of $n$. Then

$$C(N)={S+3D+2T\over6}$$

The latter formula is obtained by counting unordered triples. Basically, $T$ counts the number of triples $(a,a,a)$ with $a^3\le N$, $D$ counts the number of triples $(a,a,c)$ with $a^2c\le N$, and $S$ counts the number of triples $(a,b,c)$ with $abc\le N$: that is, there are $\sigma(n)$ pairs $(a,b)$ such that $ab=n$, and for each such pair there are $\lfloor N/n\rfloor$ possible values of $c$.

To give a very simple example, if $N=4$, then $T=1$, $D=4+1=5$, and

$$S=1\cdot4+2\cdot2+2\cdot1+3\cdot1=4+4+2+3=13,$$

so

$$C(4)={13+3\cdot5+2\cdot1\over6}={13+15+2\over6}=5,$$ which agrees with the explicit list of ordered triples $(1,1,1),(1,1,2),(1,1,3),(1,1,4)$, and $(1,2,2)$. For a number like $N=1000$, however, the first, nested-sum formula is probably easier to compute, since there are only a few hundred terms altogether and you don't have to compute $\sigma(n)$ for a thousand values of $n$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

You should find conditions to reduce the problem.

Firstly observe $a \leq 10$, because $a^3 \leq a \cdot b \cdot c$.

Another condition to reduce the problem is $b \leq \sqrt{1000} \approx 32$, in fact you have the stronger condition $b \leq \sqrt{1000/a}$.

Perhaps this gives you a manageable number of cases of possible pairs $(a,b)$. For each pair you have to find the number of integers on the interval $[b,1000/ab]$, and take the sum.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Small correction - the interval should be closed, since the inequalities are not strict. Not sure who downvoted you though, your solution is correct. $\endgroup$ – T. Linnell Jul 31 '17 at 10:13
  • $\begingroup$ Corrected, thank you. $\endgroup$ – Ögmundur Eiriksson Jul 31 '17 at 10:23
2
$\begingroup$

These are the maximum triplet for each possibility of $a$ (the first)

$1\times 31\times 32,\;2\times 22\times 22,\;3\times 18\times 18,\;4\times 15\times 16,\;5\times 14\times 14,\;6\times 12\times 13,\;7\times 11\times 12,\;8\times 11\times 11,\;9\times 10\times 11,\;10\times 10\times 10$

and then the number of combinations allowed for each of the previous cases

$3550+1106+505+263+146+76+38+17+6+1=5\,708$

For instance if $a=1$ then you can have $1\times 1\times 1, 1 \times 1\times 2\ldots$ up to $1\times 1\times 1000$ plus $1 \times 2 \times 2, 1\times 2 \times 3\ldots$ up to $1\times 2\times 500$ and so on

It's not that easy. I applied brute force with Mathematica function

pp = FindInstance[a b c <= 1000 && 0 < a <= b <= c, {a, b, c}, 
  Integers, 10000]

Hope this helps

| cite | improve this answer | |
$\endgroup$

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.