How many more odd divisors are there than even divisors

divisibilityelementary-number-theorynumber theoryprime numbers

Let $f(k)$ be the number of odd divisors of $k$ and $g(k)$ be the number of even divisors. Define $F(n) = \sum_{k \le n} f(k)$ and $G(n) = \sum_{k \le n} g(k)$. Thus $F(n)$ and $G(n)$ are the total number of odd and even divisors of natural numbers up to $n$. Experimental data show that

$$
\lim_{n \to \infty}\frac{F(n) – G(n)}{n} = \log 2
$$

Question: Is the above limit true?

Motivation: For a different question I had written a program to find length of the period $l_p$ of $1/p$. It is known that $l_p|p-1$ so we only need to search among the divisors of $p_1$ to find the smallest divisor $d$ such that $10^d – 1$ is divisible by $p$. This computation is slow but I observed that overall the program runs much faster if we first scan through even divisors first and only if we do not find a $d$ then we search through odd. This is because about $2/3$ of the divisors of $p-1$ seems to be even. This led me to investigate the proportion of odd and even divisors among natural numbers.

Source code:

p = 1
step = target = 10^6
odd = even = 0

while True:
    d = divisors(p)
    l = len(d)
    i = 0
    while i < l:
        e = d[i]
        if e%2 == 1:
            odd = odd + 1
        else:
            even = even + 1
        i = i + 1
        
    if even > odd:
        print("Found", p, odd, even)
    
    if p >= target:
        t = odd + even
        print(p, odd, even, odd/t.n(), even/t.n(), (odd - even)/p.n())
        target = target + step
        
    p = p + 1

Best Answer

Not an answer, not very rigorous either, but here is some progress I made:

The number of times $1$ occurs as divisor from $1 \cdots n$ is $\lfloor \frac{n}{1} \rfloor$.

The number of times $2$ occurs as divisor from $1 \cdots n$ is $\lfloor \frac{n}{2} \rfloor$.

a.s.o

We are interested in $$\lim_{n \to \infty} \frac{\lfloor \frac{n}{1} \rfloor - \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor + \cdots + (-1)^{n+1}\lfloor \frac{n}{n} \rfloor}{n}$$

Approximate this to $$\lim_{n \to \infty} \frac{\frac{n}{1} - \frac{n}{2} +\frac{n}{3}+ \cdots + (-1)^{n+1}\frac{n}{n}}{n}$$

Thus, it equals $$\lim_{n \to \infty} \frac{1}{1} - \frac{1}{2} + \frac{1}{3} + \cdots + (-1)^{n+1}\frac{1}{n}$$

Using the expansion of $\ln (1 + 1)$, we know this is $\ln 2$.

I think this approximation works because $\lfloor \frac{n}{x} \rfloor$ has only $O(\sqrt{n})$ distinct values for $1 \leq x \leq n$. These values decrease rapidly and stay equal for longer ranges, so I think the subtraction balances things out in normal division too. And as $n \to \infty$, the "leftovers" become less significant. But again this is not a rigorous way of proving.

Related Question