cp's OEIS Frontend

A067743 Number of divisors of n not in the half-open interval [sqrt(n/2), sqrt(n*2)).

%I A067743 #28 Jun 22 2022 20:31:58
%S A067743 0,1,2,2,2,2,2,3,2,4,2,4,2,4,2,4,2,5,2,4,4,4,2,6,2,4,4,4,2,6,2,5,4,4,
%T A067743 2,8,2,4,4,6,2,6,2,6,4,4,2,8,2,5,4,6,2,6,4,6,4,4,2,10,2,4,4,6,4,6,2,6,
%U A067743 4,6,2,9,2,4,6,6,2,8,2,8,4,4,2,10,4,4,4,6,2,10,2,6,4,4,4,10,2,5,4,8,2,8
%N A067743 Number of divisors of n not in the half-open interval [sqrt(n/2), sqrt(n*2)).
%C A067743 From _Max Alekseyev_, May 13 2008: (Start)
%C A067743 Direct proof of _Joerg Arndt_'s g.f. (see formula section).
%C A067743 We need to count divisors d|n such that d^2<=n/2 or d^2>2n. In the latter case, let's switch to co-divisor, replacing d with n/d.
%C A067743 Then we need to find the total count of: 1) divisors d|n such that 2d^2<=n; 2) divisors d|n such that 2d^2<n.
%C A067743 Let d|n and 2d^2<=n. Then n-2d^2 must be a multiple of d, i.e., n-2d^2=td for some integer t>=0.
%C A067743 Moreover it is easy to see that 1) is equivalent to n = 2d^2 + td for some integer t>=0. Therefore the answer for 1) is the coefficient of z^n in Sum_{d>=1} Sum_{t>=0} x^(2d^2 + td) = Sum_{d>=1} x^(2d^2)/(1 - x^d).
%C A067743 Similarly, the answer for 2) is Sum_{d>=1} x^(2d^2)/(1 - x^d) * x^d.
%C A067743 Therefore the g.f. for A067743 is Sum_{d>=1} x^(2d^2)/(1 - x^d) + Sum_{d>=1} x^(2d^2)/(1 - x^d) * x^d = Sum_{d>=1} x^(2d^2)/(1 - x^d) * (1 + x^d), as proposed. (End)
%C A067743 a(n) is odd if and only if n is in A001105. - _Robert Israel_, Oct 05 2020
%C A067743 Number of nonmiddle divisors of n. - _Omar E. Pol_, Jun 11 2022
%H A067743 Robert Israel, <a href="/A067743/b067743.txt">Table of n, a(n) for n = 1..10000</a>
%H A067743 Robin Chapman, Kimmo Ericksson, Richard P. Stanley and Reiner Martin, <a href="http://www.jstor.org/stable/2695782">On the Number of Divisors of n in a Special Interval: Problem 10847</a>, The American Mathematical Monthly, Vol. 109, No. 1 (Jan., 2002), p. 80.
%F A067743 a(n) = A000005(n) - A067742(n).
%F A067743 G.f.: Sum_{k>=1} z^(2*k^2)*(1+z^k)/(1-z^k). - _Joerg Arndt_, May 12 2008
%e A067743 a(6)=2 because 2 divisors of 6 (i.e., 1 and 6) fall outside sqrt(3) to sqrt(12).
%p A067743 f:=proc(n) nops(select(t -> t^2 < n/2 or t^2 >= 2*n, numtheory:-divisors(n))) end proc:
%p A067743 map(f, [$1..200]); # _Robert Israel_, Oct 05 2020
%t A067743 hoi[n_]:=Length[DeleteCases[Divisors[n],_?(Sqrt[n/2]<=#<Sqrt[2*n]&)]]; Array[ hoi,110] (* _Harvey P. Dale_, Aug 22 2020 *)
%o A067743 (PARI) A067743(n)=sumdiv( n,d, d*d<n/2 || d*d >= 2*n ) \\ _M. F. Hasler_, May 12 2008
%Y A067743 Cf. A067742, A000005, A001105, A302433.
%K A067743 easy,nonn
%O A067743 1,3
%A A067743 _Marc LeBrun_, Jan 29 2002