Factors of $2n^2 \leq n$?

Question

How many factors of $2n^2$ are less than or equal to $n$? I know that the number of factors of $n^2$ less than $n$ is half the number of factors of $n^2$ (each factor $< n$ corresponds with one greater than $n$), but $2n^2$ is a whole different case, it seems. Is there any way to find an expression for this? And if not, is there an algorithm for it? I have looked into both combinatorics and prime factorization, but have arrived at dead-ends.

Answer 1

I see no general analytic solution, since it would seem to depend upon the prime factorization of $n$.

But the OP also asks for code. That is very straightforward. In Mathematica:

myfun[n_: Integer] := Length[
Select[Divisors[2 n^2], # <= n &]]

So:

myfun[9098345]

(* 27 *)

Here's a plot:

---

This isn't directly part of the problem, but seems to be the motivation of the problem. If the above function is $f(n)$, calculate $F(N) = \sum\limits_{n=1}^N f(n)$, for $N = 10^{12}$.

I think the approach is the following: Calculate the number of $2$s in that sum. Then calculate the number of $3$s. And so on, then add them up.

The number of $2$s is $10^{12}/2$. The number of $3$s is $10^{12}/3$. And so on. But what is the maximum we add those up to in the total calculation? I think it should be the largest factor allowed in the $10^{12}$ (last) term in the sum, i.e., $k_{max} = \sqrt{50} \cdot 10^5 = 707107$, obtained from the $2 n^2 = 10^{12}$ calculation.

If that's right, then: $F(10^{12}) = 10^{12} \sum\limits_{k = 1}^{k_{max}} \frac{1}{k} = 10^{12}\ {\rm HarmonicNumber}(k_{max}) = 10^{12} \cdot 14.0461536491411$.

There are probably some rounding artifacts that must be included, but I think this is the right approach. Someone should do this with greater care.

Answer 2

This is a very interesting question. Assume $n=2^{a}(2k+1)$ for some integer $a$ and $k$. Let $f(x)=$numbers of positive divisors of the integer $x$ . Since factors of $2n^2\leq n$ we need number of factors of $2^{2a+1}(2k+1)^2$. Thus we have $f(2^a(2k+1))+c_{a}$.Where $c_{a}$ is the error factor has a small factor of bound, which needs to be deterministic. Although it's a rough idea, I am not finding the bound but for hints, you can try small cases. However let $g(x)=$greatest integer lesser equal to x then, $$c_{a}\leq f(g(2^{\frac{2a+1}{2}}(2k+1)))-f(2^a(2k+1))$$.Where we know $f$ is famous divisor function or $\tau$ function and $g$ is the floor function. Use this link for bound, Lower bound for the sum of divisor function