cp's OEIS Frontend

A316296 a(n) = Sum_{k=1..n} f(k, n), where f(i, j) is the number of multiples of i greater than j and less than 2*j.

%I A316296 #29 Oct 24 2023 23:16:53
%S A316296 0,1,3,5,9,10,15,18,21,24,31,30,38,41,44,48,55,56,64,65,70,75,84,81,
%T A316296 90,95,98,103,112,109,120,123,129,134,139,139,150,155,160,161,173,170,
%U A316296 183,184,187,198,205,202,212,217,223,226,239,236,245,248,255,262,271,266,282,285,288
%N A316296 a(n) = Sum_{k=1..n} f(k, n), where f(i, j) is the number of multiples of i greater than j and less than 2*j.
%C A316296 f(n, m) is the number of multiples of n that are > m and < 2*m. n and m must be both >= 0.
%C A316296 By definition, this means that f(n, m) =
%C A316296   0    if n >= 2m;
%C A316296   1    if m < n < 2m;
%C A316296 If n <= m, then m = kn + q, where 0 <= q < n.
%C A316296 It can be proven that in this case f(n, m) =
%C A316296   k - 1    if q = 0;
%C A316296   k        if q > 0 and (n - q) >= q;
%C A316296   k + 1    if q > 0 and (n - q) < q.
%C A316296 Let sd(n) = A006218; then a(n) = sd(2n-1) - sd(n) - (n - 1).
%C A316296 Also, a(n) = Sum_{k=n+1..2n-1} (d(k) - 1), where d(k) is number of divisors (A000005).
%C A316296 Number of ways the numbers from 1..n divide the numbers from n+1..2n-1, n>=2. - _Wesley Ivan Hurt_, Feb 08 2022
%F A316296 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
%e A316296 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.
%o A316296 (JavaScript)
%o A316296 function f(n,m){
%o A316296     var count = 0;
%o A316296     for(var i=m+1; i<2*m; i++){
%o A316296         if(i%n === 0) count++;
%o A316296     }
%o A316296     return count;
%o A316296 }
%o A316296 function sf(n){
%o A316296     var sum = 0;
%o A316296     for(var i=1; i<=n; i++){
%o A316296         sum += f(i, n);
%o A316296     }
%o A316296     return sum;
%o A316296 }
%o A316296 (PARI) a(n) = n + sum(m = 1, n, (floor((n<<1 - 1) / m) - ceil((n + 1) / m))) \\ _David A. Corneth_, Jun 29 2018
%o A316296 (Python)
%o A316296 from math import isqrt
%o A316296 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
%K A316296 nonn,easy
%O A316296 1,3
%A A316296 _Andrea La Rosa_, Jun 29 2018