How many numbers $\le x$ can be factorized into three numbers which form the sides of a triangle?

Solution 1:

This is not an answer but to long for a comment and possibly useful for numerics.

Lemma: A number $n$ which contains a prime factor $p$ which satisfies $p > \sqrt{n}$ cannot be decomposed into triangular divisors.

Proof: Assume $n=p\cdot q\cdot r$ then $p > \frac{n}{p}=q\cdot r \ge q+r$ if $q,r \ge 2$ so the triangle inequality is not satisfied. The tuple $p, \frac{n}{p}, 1$ doesn't satisfy the triangle inequality either.

I first thought that the converse of this lemma (ie numbers without such prime factors can be decomposed into triangular divisors) holds as well but this is false. It fails the first time for $n=30$.

Edit: Numbers with no prime factor bigger than $\sqrt{n}$ is a sequence in oeis.org. This sequence has density $1-\ln(2)$. As our sequence is a subset of this one, this disproves my intuition of almost all numbers and shows that the sequence has in fact density smaller equal $1-\ln(2)$ (the numerics suggest a density of $0$).

Solution 2:

COMMENT.-It is trivial to find a number having a triangular divisor and that there are infinitely many of them. But it is not trivial to answer if a given integer $N$ has triangular divisor. Here I give a geometrical version of such a problem hoping that it may be of some use to your program project (and if not, because this point of view seems nice to me).

Given $N$ if $xyz=N$ with $x\le y\le z$ then points $(x,y)$ searched must be in the hyperbola $xy =\dfrac{N}{z}$ and in the region bounded by straight lines $ x + y = z $ and $ x-y = z $ (condition for a triangle, with obviously $\gt$ and $\lt$ instead of $=$) and because $ (x, y) $ and $ (y, x) $ give the same result we can restrict our attention to points with $x\gt y$.

This way the desired points should be in the arc $\widehat{PQ}$ of the hyperbola in the attached figure

Solution 3:

As quarage pointed out, every factor must be $\leq\sqrt{n}$.

Wlog, let $z$ be the largest of three factors $x\cdot y\cdot z = n$.

Per construction, $x$, $y$ and $z$ are the side lengths of a triangle. Call $h$ the "height" of said triangle with respect to $z$, that is, the length of the line segment perpendicular to the side with length $z$, intersecting the point that is not an endpoint of said side. Call $z_1$ and $z_2$ the lengths of the two resulting line segments.

So we have two right angled triangles, and by Pythagoras:

$$ \begin{array}{rcl} h^2 + z_1^2 & = & x^2 \\ h^2 + z_2^2 & = & y^2 \\ \end{array} $$

which yields:

$$ z_1^2 - z_2^2 = x^2 - y^2 $$

When $x$, $y$ and $z$ are a pythagorean triple, one of $z_1$ or $z_2$ is zero, and thus variables can be shuffled around, yielding the very definition of a pythagorean triple. The other case is more interesting.

$x$, $y$ and $z$ form a ("non-pythagorean") triangle iff $x\cdot y\cdot z$ is integer and equal to two distinct differences of squares. By "Dixon's Method" this implies that there are two different factorizations of $n$, which we'd take to be $n = (x\cdot y)\cdot z = $ and $n = x\cdot(y\cdot z)$.

Take, for example, $n = 3\cdot 5\cdot 7 = 105$. We now have $s = 3+5+7 = 15$, $h = {2\over 7}\sqrt{s(s-7)(s-5)(s-3)} \approx 1.855$, $z_1 = \sqrt{9-h^2}$ and $z_2 = \sqrt{25-h^2}$. Obviously,

$$ \begin{array}{rcl} z_1^2-z_2^2 & = & -16 \end{array} $$

Since $3^2 - 5^2 = 9-25 = -16$.

Basically, stating that a triplet of numbers forms a triangle appears to say that it can be factored in more than one way, that it has more than two factors.

I'll expand on that later. For now, I think this is some sort of generalization of pythagorean triangles (two right triangles joined at the right angles, each having the hypotenuse integer, the adjacent cathedes equal and the other ones having a sum equal to an integer square). I also see a connection to penrose tiling.