

A067743


Number of divisors of n not in the halfopen interval [sqrt(n/2), sqrt(n*2)).


3



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

From Max Alekseyev, May 13 2008: (Start)
Direct proof of Joerg Arndt's g.f. (see formula section).
We need to count divisors dn such that d^2<=n/2 or d^2>2n. In the latter case, let's switch to codivisor, replacing d with n/d.
Then we need to find the total count of: 1) divisors dn such that 2d^2<=n; 2) divisors dn such that 2d^2<n.
Let dn and 2d^2<=n. Then n2d^2 must be a multiple of d, i.e., n2d^2=td for some integer t>=0.
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).
Similarly, the answer for 2) is Sum_{d>=1} x^(2d^2)/(1  x^d) * x^d.
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)


LINKS

Table of n, a(n) for n=1..102.
Robin Chapman, Kimmo Ericksson, Richard P. Stanley and Reiner Martin, On the Number of Divisors of n in a Special Interval: Problem 10847, The American Mathematical Monthly, Vol. 109, No. 1 (Jan., 2002), p. 80.


FORMULA

a(n) = A000005(n)  A067742(n).
G.f.: Sum_{k=1,N} z^(2*k^2)*(1+z^k)/(1z^k).  Joerg Arndt, May 12 2008


EXAMPLE

a(6)=2 because 2 divisors of 6 (i.e., 1 and 6) fall outside sqrt(3) to sqrt(12).


PROG

(PARI) A067743(n)=sumdiv( n, d, d*d<n/2  d*d >= 2*n ) \\ M. F. Hasler, May 12 2008


CROSSREFS

Cf. A067742, A000005.
Sequence in context: A001031 A035250 A165054 * A029230 A280945 A196067
Adjacent sequences: A067740 A067741 A067742 * A067744 A067745 A067746


KEYWORD

easy,nonn


AUTHOR

Marc LeBrun, Jan 29 2002


STATUS

approved



