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

elementary-number-theoryinequalitynumber theoryprime numbersrecreational-mathematics

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.

enter image description here

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.

enter image description here

Related question: Reshaping an object into two integer sided cuboids without changing the total volume.

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

Update: Posted in MO since it is unanswered here

Best Answer

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

Related Question