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

We say that a natural number $$n$$ has triangular divisors if it has at least one triplet of divisors $$n = d_1d_2d_3, 1 \le d_1 \le d_2 \le d_3$$, such that $$d_1,d_2$$ and $$d_3$$ form the sides of a triangle (i.e. non degenerate triangle)

Example: $$60$$ has triangular divisors because $$60 = 3.4.5$$ and $$3,4,5$$ form a triangle. Note that another triplet of divisors of $$60 = 1.4.15$$ does not form a triangle but because of the triplet $$3,4,5$$ the number $$60$$ qualifies a number with triangular divisors. On the other the number $$10$$ does not have any triplet of triangular divisors.

The first few numbers in this sequence are

$$1,4,8,9,12,16,18,24,25,27,32,36,40,45,48,\ldots$$

Question: What is the growth rate of the number of positive integers $$\le x$$ which have at least one set of triangular divisors?

Experimental data: Let $$f(x)$$ be the number of integers $$\le x$$ with this property. The graph of $$\dfrac{f(x)}{x}$$ vs. $$x$$ is shown below.

A simple curve fitting gives $$\dfrac{a}{\log x}$$ as a good fit with $$R^2 = 0.9977$$ which suggests that $$f(x)$$ growth rate somewhere close to $$\pi(x)$$. This is rather counter intuitive as mentioned in the comments that we expect almost all integers to have this property.

Higher density of even numbers: A curious observation is the there are roughly $$2.4$$ more even numbers as compared to odd numbers in this sequence. Let $$f_o(x)$$ be the number of odd numbers $$\le x$$ with this property. The graph of $$\dfrac{f_o(x)}{f(x)}$$ is shown below.

Note: I searched this sequence in OEIS but could not find it. In case its is already known, please let me know else I was planning to add it.

Update 9-Mar-2020: Faster code using @quarague 's comment

a = 2
f = 1
odd = 1
even = 0
target = 10^4 - 1
step = 10^4

while True:
stop1 = floor(a^0.5)
l = prime_factors(a)[-1]

if l <= stop1:
d1 = 1
stop1 = floor(a^0.5)

while(d1 <= stop1):
if(a%d1 == 0):
b = a/d1
d2 = d1
stop2 = floor((a/d1)^0.5)

while(d2 <= stop2):
if(b%d2 == 0):
c = b/d2

if(d1 + d2 > c):
if(d1 + c > d2):
f = f + 1
# print f, a

if(a%2 == 0):
even = even + 1
else:
odd = odd + 1
stop1 = stop2 = 0
d2 = d2 + 1
d1 = d1 + 1

if a > target:
target = target + step
print a,f, odd, even, f/a.n(), odd/even.n(),f/prime_pi(a).n()
a = a + 1

• My intuitive guess would be that asymptotically almost all numbers can be written that way because most numbers have lots of small prime factors. One can easily build infinitely many examples (say squares) and non-examples (say primes) but all the sets I came up with have density zero. Mar 3, 2020 at 12:44
• Your list is missing $8=2 \cdot 2 \cdot 2$ and $27=3\cdot 3 \cdot 3$. Mar 3, 2020 at 13:17
• I think $1=1\cdot1\cdot1$ should be the first term in the sequence? Mar 3, 2020 at 18:18
• @KierenMacMillan: Those sequences match the initial terms given in the post, but they both contain $63$, which isn't in the present sequence. Mar 3, 2020 at 19:10
• @NilotpalSinha not $(2,2,3)$ because the divisors are supposed to be distinct. But $(3,4,6)$ hits. Aug 28, 2022 at 22:05

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

• Observation: Let $n$ have triangular divisors and $p$ be its largest prime factor. If $n$ is not a perfect square then $4p^2 < 3n$. Mar 5, 2020 at 12:46

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

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.