cp's OEIS Frontend

A347275 a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).

%I A347275 #28 Nov 08 2023 10:08:55
%S A347275 1,3,6,10,15,19,25,29,35,40,46,50,58,62,68,74,81,85,93,97,105,111,117,
%T A347275 121,131,136,142,148,156,160,170,174,182,188,194,200,211,215,221,227,
%U A347275 237,241,251,255,263,271,277,281,293,298,306,312,320,324,334,340,350,356
%N A347275 a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).
%C A347275 Except for a(0) and a(1), a(n) = A006218(n + 1) - A049820(n + 1) + 2n - 1. Tested with first 10^9 numbers.
%C A347275 Since there are only O(sqrt(n)) different integers in the set S = {floor(n / 1), floor(n / 2), ..., floor(n / n)}, we can calculate a(n) in O(sqrt(n)).
%C A347275 There are many methods based on different kinds of formulas that are also known to work in O(n^(1/3)), but not all are effective. Some of them have lower complexity, but their use of too much division and multiplication makes them slower than expected; some of them use precalculation and caching to speed things up but are not as effective as the division-free algorithm that Richard Sladkey described.
%C A347275 a(n) is approximately epsilon*n^(1+delta) as delta approaches 0 and epsilon approaches +oo for n approaching +oo. The tighter relationship between epsilon and delta is unknown. Tested with 10^7 numbers n <= 10^15 using power regression algorithm.
%C A347275 For n > 1, a(n) = A006218(n)+2n-1. - _Chai Wah Wu_, Oct 07 2021
%H A347275 Richard Sladkey, <a href="https://arxiv.org/abs/1206.3369"> A Successive Approximation Algorithm for Computing the Divisor Summatory Function</a>, arXiv:1206.3369 [math.NT], 2012.
%F A347275 a(n) = Sum_{a=0..n} Sum_{b=0..n-a} [a*b<=n], where [] is the Iverson bracket.
%e A347275 a(1) = 3: (0, 0), (0, 1), (1, 0).
%p A347275 A347275 := proc(n)
%p A347275     local a,i,j ;
%p A347275     a := 0 ;
%p A347275     for i from 0 to n do
%p A347275     for j from 0 to n-i do
%p A347275         if i*j <= n then
%p A347275             a := a+1 ;
%p A347275         end if;
%p A347275     end do:
%p A347275     end do:
%p A347275     a ;
%p A347275 end proc:
%p A347275 seq(A347275(n),n=0..40) ; # _R. J. Mathar_, Sep 15 2021
%t A347275 a[n_] := Sum[Boole[i*j <= n], {i, 0, n}, {j, 0, n-i}];
%t A347275 Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Nov 08 2023 *)
%o A347275 (C) int T(int n) { int cnt = 0; for (int a = 0; a <= n; ++a) for (int b = 0; b <= n - a; ++b) if (a * b <= n) ++cnt; return cnt; }
%o A347275 (Python)
%o A347275 from math import isqrt
%o A347275 def A347275(n): return 2*n+1 if n <= 1 else 2*(n+sum(n//k for k in range(1, isqrt(n)+1)))-isqrt(n)**2-1 # _Chai Wah Wu_, Oct 07 2021
%Y A347275 Cf. A006218, A049820, A091626.
%K A347275 nonn,easy
%O A347275 0,2
%A A347275 _Vo Hoang Anh_, Aug 25 2021