Strange divisors

Question

Let $~m~$ and $~n~$ be positive integers. Let's call (my term - not sure there is any official term for such thing) number $~m~$ a "strange divisor" of number $~n~$ if dividing $~n~$ by $~m~$ we get equall quotient and remainder.

For example $~7 = 6\cdot 1 + 1~$ so $~6~$ is a strange divisor of $~7~$. As another example $~15 = 4\cdot3 + 3~$ so $~4~$ is strange divisor of $~15$.

From my definition above we can deduce that $~m~$ is a strange divisor of $~n~$ iff there exists number $~0 \leq r < m~$ such that $~n = (m + 1)r$. Let's denote by $~f(n)~$ the number of all strange divisors of number $~n$. I wonder what is the average value of $~f(n)~$ so i need an efficient way to compute $~\sum_{n=1}^{N} f(n)~$. Any ideas how to do it fast will be highly appreciated. I think that there must be some way to reduce upper limit from $~N~$ to $~\sqrt{N}~$ since we work with divisors. But i don't see the way to do it.

Answer 1

Let's work backwards:

m is a strange divisor of a number n, iff:

1. m+1 is a divisor of n, and
2. the quotient of n & m+1 is less than m.

Which means, for a number m, it's a strange divisor of m+1, 2*(m+1), 3*(m+1).... (m-1)*(m+1), which is exactly m-1 numbers.

If we cap "strange dividends" of m to be less than some fixed number N, then m will be a strange divisor of:

min(floor($\frac{N}{(m+1)}$), m-1) numbers.

Roughly, for values of m < sqrt(n), the expression is m-1. For values of m > sqrt(n), the expression is floor(N/(m+1))

I make the following claim:

$\sum_{i=1}^N \text{(number of strange divisors of i)} = \sum_{m=1}^N \text{(number of numbers for which m is a strange divisor)}$

So our sum is:

$\sum_{i=1}^{N} f(i) = \sum_{m=1}^{N} min(floor(\frac{N}{(m+1)}), m-1)$

$ \approx (\sum_{m=1}^{floor(\sqrt{N})} m - 1) + (\sum_{m=floor(\sqrt{N})}^N floor(\frac{N}{m+1})) $

$ \approx (floor(\sqrt{N}))*(floor(\sqrt{N}) - 1) * \frac{1}{2}$ + $ N*H_N - floor(\sqrt{N})*H_{floor(\sqrt{N})} $

where $H_k$ is the $k^{th}$ harmonic number

Note: this value is not exactly the same as the sum of # divisors of numbers from 1 to N, because not every divisor d corresponds to a strange divisor d-1 (It has to satisfy N/d < d-1)

Answer 2

Say we have: $$n=ab$$Then: $$n = a(b-1)+a$$ So $b-1$ would be what you call a strange divisor of $n$.

So what you could say is that $$f(n) \approx \frac{1}{2}d(n)$$ Where $d(n)$ is the number of divisors of $n$. Since $b-1$ must be greater than $a$, you can only use one half of the pairs $a,b$, which is why we multiply with one half.

We can approximate $\sum_{N}^{n=1}f(n)$ when we realize that all integers all divisible by $1$, one half of the integers is divisible by $2$, one third by $3$ etc. We get: $$\sum_{i=1}^{N}f(i) \approx \frac{1}{2}N\bigg(\sum_{i=1}^{N}\dfrac{1}{i}\bigg)=\frac{1}{2}N\cdot H_{N}\approx \frac{1}{2}N(\log N + \gamma)$$ Where $\gamma$ is the Euler-Mascheroni constant (about $0.5772$).

I checked this formula and it keeps getting closer. $$\sum_{i=1}^{100}f(i)=236$$ $$50(\log 100 + \gamma)=259$$

And for a way larger number: $$\sum_{i=1}^{10000}f(i)=46784$$ $$5000(\log 10000 + \gamma)=48938$$ The first result is off by $7.47 \%$ and the second one by $4.49\%$.