Divisors near sqrt(n)

Analytic Number Theory Alert! An even more idle question than normal (that’s because it comes from twitter). Alex Kontorovich noted with pleasure the following pictorial representation of the integers from a Veritasium youtube video, where prime numbers are represented by \(1 \times n\) rectangles and all other numbers represented as \(a \times b\) rectangles (of area \(n\)) for some \(a > 1\).

This leads to the natural followup questions. How much horizontal space does it take to graph the first \(X\) integers this way if one either:

1. Plots the integers \(n\) as \(a \times b\) with \(a \le b\) as big as possible?
2. Plot the integers \(n\) as \(a \times b\) with \(a = 1\) if \(n\) is prime, and otherwise with \(a\) as small as possible, that is, the smallest divisor of \(n\) greater than \(1\)?

(From the graph, it actually appears that the second algorithm is actually used.)

In both cases, there is a trivial upper bound \( \ll X^{3/2}\). On the other hand, simply by considering products of primes in the interval \([X^{1/2}/C,X^{1/2}]\) for some constant \(C > 1\) you get at least a constant times [corrected] \((X^{1/2}/\log X)^2\) integers less than \(X\) with \(a \gg X^{1/2}\), and hence a lower bound (in both cases) of \(\gg X^{3/2}/(\log X)^2\). But neither of these bounds are presumably best possible. What then are the precise asymptotics? This seems like the type of question Kevin Ford might be able to answer. Actually, this might be a question that Kevin Ford already knows how to answer. I summon his spirit from the whispers of the internet to come and answer this for me. But if that doesn’t work, anyone else should feel free to give an answer or make a guess.

Update: Friend of the blog Boaty McBoatface emails me to say:

I think the second one is quite easy.

I think you just want to compute

\(\displaystyle{\sum_{p < X^{1/2}} p F(X/p, p)}\)

where \(F(y,p)\) is the number of integers \(\le y\) with all prime factors \(\ge p\). (This has a name, the Buchstab function).

Here the \(X/p\) should be \(\lfloor X/p \rfloor\) but this is of little consequence.

Using the trivial bound \(F(y,p) \le y\) shows that essentially all the contribution is from \(p > X^{1/2 – \varepsilon}\), and in this range a number \( \le X/p\) has all its prime factors \( \ge p\) if and only if it is in fact a prime \( \ge p\) . So in fact you want to compute

\(\displaystyle{\sum_{p \le X^{1/2}} p \pi(X/p)}.\)

There are various ways to do this more or less carefully, but by splitting into ranges \(cX^{1/2} < p < (c + 1/N) X^{1/2}\), summing over \(c = 0,1,2,\ldots, N-1\) and then letting \(N \rightarrow \infty\) I think one gets

\(\displaystyle{ \frac{4X^{3/2}}{(\log X)^{2}} \int^1_0 (1 – c^2) dc \sim \frac{8}{3} \cdot \frac{X^{3/2}}{(\log X)^{2}}}.\)

The first question is definitely much harder and, as you guess, feels pretty close to the kind of stuff Ford and Tenenbaum do in their work.