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

Note: Posting in MO since it was unanswered in MSE

Definition: 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 non-degenerate triangle.

Eg: $$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$$

I am interested in the density of these numbers. In the linked questions users commented that the almost all integers are expected this property since because most numbers will have a several small prime factors so the natural density was initially thought to be $$1$$.

However, quite counter intuitively, in one of the long comment which was posted as an answer in the linked question, it was proved that if $$n$$ has triangular divisors then the largest prime factor of $$n$$ is less than $$\sqrt n$$ which immediately implies that the natural density of numbers with triangular divisors is $$< 1 - \log 2 \approx 0.3069$$. Experimentally, the data shows that the natural density approaches $$0$$. Let $$f(x)$$ be the number of integers $$\le x$$ with triangular divisors. We have $$f(46732002) = 3630678$$ The graph of $$\frac{f(x)}{x}$$ vs $$x$$ given below shows that the density decreases as $$x$$ increases.

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

A simple curve fitting gives $$\frac{a}{\log x}$$ as a good fit with $$R^2 = 0.9977$$ which suggests that $$f(x)$$ growth rate somewhere close to a constant times the prime counting function $$\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 significantly more even numbers with triangular divisors as compared to odd numbers. Let $$f_o(x)$$ be the number of odd numbers $$\le x$$ with triangular divisors. The graph of $$\frac{f_o(x)}{f(x)}$$ is shown below.

Question: How many numbers $$\le x$$ have triangular divisors and why are even numbers more dense than odd numbers?

• A fun fact is that for the first values of your sequence (call it $S$), $n\in S$ implies $nr_{0}(n)\in S$, where $r_{0}(n)=\inf\{r>0,(n-r,n+r)\in\mathbb{P}^{2}\}$. If it's true, it may shed light on your numerical observations. – Sylvain JULIEN Mar 12 at 7:39
• This has the feel of a project euler problem (which isn't necessarily a bad thing) – Thomas Browning Mar 12 at 11:06
• Your sequence 1,4,8,9,12,16,18,24,25,27,32,36,40,45,48,… is not in the Online Encyclopedia of Integer Sequences oeis.org You should include it! – Stopple Mar 12 at 22:40

This problem is related to the higher dimensional multiplication table problem (specifically, the three dimensional version). From the work of Tenenbaum, Ford, and Koukoulopoulos this is now well understood in many cases. From their work, one can show that the number of $$n$$ up to $$x$$ with triangular divisors is $$\ll \frac{x}{(\log x)^{\alpha}}(\log \log x)^{\frac 12}$$ where $$\alpha=1- \frac{2}{\log 3} +\frac{2}{\log 3} \log \frac{2}{\log 3} = 0.27016\ldots.$$ The power of $$\log \log x$$, which is the thrust of the work of Ford and Koukoulopoulos, is probably not correct here. But there should be a corresponding lower bound of size $$x/(\log x)^{\alpha +o(1)}$$; it should be possible to establish this from the techniques in Koukoulopoulos.
Let me now indicate why an upper bound of this magnitude holds. We want to count $$n \le x$$ that may be written as $$n=abc$$ with $$a\le b\le c$$ and $$c. Clearly we must have $$a\le x^{\frac 13}$$. Consider first the terms where $$a\le x^{\frac 13}/\log x$$. Given $$a$$, note that we must have $$b\le \sqrt{x/a}$$ and then $$c$$ lies in the range $$b \le c, so that given $$a$$ and $$b$$ there are at most $$a$$ choices for $$c$$. Thus the number of such $$n$$ with $$a\le x^{\frac 13}/\log x$$ is $$\le \sum_{a\le x^{\frac 13}/\log x} \sum_{a \le b\le\sqrt{x/a}} a \ll \sum_{a\le x^{\frac 13}/\log x} \sqrt{xa} \ll \frac{x}{(\log x)^{\frac 32}},$$ which is acceptably small.
It remains to count solutions where $$x^{\frac 13} \ge a>x^{\frac 13}/(\log x)$$. Note that $$b$$ (which is $$\ge a$$ and $$\le \sqrt{x/a}$$) then lies in the interval $$x^{\frac 13}/\log x$$ to $$x^{\frac 13} (\log x)^{\frac 12}$$. Break the possible values for $$a$$ and $$b$$ into dyadic intervals $$A < a\le 2A$$ and $$B< b\le 2B$$. There are about $$(\log \log x)^2$$ such dyadic intervals, and both $$A$$ and $$B$$ are about $$x^{\frac 13}$$, and we can assume that $$B \le \sqrt{x/A}$$. Now we apply Theorem 2.6 from Koukoulopoulos's thesis which gives $$\#\{ n\le 4x: \ ab |n, \ \ A< a\le 2A, \ \ B< b\le 2B\} \asymp \frac{x}{(\log x)^{\alpha} (\log \log x)^{\frac 32}}.$$
Since there are $$\ll (\log \log x)^2$$ such dyadic blocks, we conclude that the number of $$n=abc$$ with $$a>x^{\frac 13}/(\log x)$$ is $$\ll \frac{x}{(\log x)^{\alpha}} (\log \log x)^{\frac 12}.$$ This gives the claimed upper bound.