# How many order triple (a,b,c) are there such that $a.b.c \le 1000$

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.

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

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

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$.

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.

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

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