OFFSET
1,3
COMMENTS
f(n, m) is the number of multiples of n that are > m and < 2*m. n and m must be both >= 0.
By definition, this means that f(n, m) =
0 if n >= 2m;
1 if m < n < 2m;
If n <= m, then m = kn + q, where 0 <= q < n.
It can be proven that in this case f(n, m) =
k - 1 if q = 0;
k if q > 0 and (n - q) >= q;
k + 1 if q > 0 and (n - q) < q.
Let sd(n) = A006218; then a(n) = sd(2n-1) - sd(n) - (n - 1).
Also, a(n) = Sum_{k=n+1..2n-1} (d(k) - 1), where d(k) is number of divisors (A000005).
Number of ways the numbers from 1..n divide the numbers from n+1..2n-1, n>=2. - Wesley Ivan Hurt, Feb 08 2022
FORMULA
a(n) = Sum_{k=1..n} Sum_{i=n+1..2n-1} (1-ceiling(i/k)+floor(i/k)). - Wesley Ivan Hurt, Feb 08 2022
EXAMPLE
For n = 7, a(7) = f(1,7) + f(2,7) + f(3,7) + f(4,7) + f(5,7) + f(6,7) + f(7,7) = 6 + 3 + 2 + 2 + 1 + 1 = 15.
PROG
(JavaScript)
function f(n, m){
var count = 0;
for(var i=m+1; i<2*m; i++){
if(i%n === 0) count++;
}
return count;
}
function sf(n){
var sum = 0;
for(var i=1; i<=n; i++){
sum += f(i, n);
}
return sum;
}
(PARI) a(n) = n + sum(m = 1, n, (floor((n<<1 - 1) / m) - ceil((n + 1) / m))) \\ David A. Corneth, Jun 29 2018
(Python)
from math import isqrt
def A316296(n): return ((s:=isqrt(n))+(t:=isqrt(m:=(n<<1)-1)))*(s-t)+(sum(m//k for k in range(1, t+1))-sum(n//k for k in range(1, s+1))<<1)-n+1 # Chai Wah Wu, Oct 24 2023
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Andrea La Rosa, Jun 29 2018
STATUS
approved