login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A067743 Number of divisors of n not in the half-open interval [sqrt(n/2), sqrt(n*2)). 2
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

REFERENCES

Problem 10847, Amer. Math. Monthly 109, (2002), p. 80.

LINKS

Table of n, a(n) for n=1..102.

FORMULA

a(n) = A000005(n) - A067742(n).

G.f.: sum(k=1,N, z^(2*k^2)*(1+z^k)/(1-z^k) ). - Joerg Arndt, May 12 2008

Direct proof of Joerg Arndt's g.f., from Max Alekseyev, May 13 2008 (Start):

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 by n/d.

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.

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.

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..oo] SUM[t=0..oo] x^(2d^2 + td) = SUM[d=1..oo] x^(2d^2)/(1 - x^d).

Similarly, the answer for 2) is SUM[d=1..oo] x^(2d^2)/(1 - x^d) * x^d.

Therefore the g.f. for A067743 is SUM[d=1..oo] x^(2d^2)/(1 - x^d) + SUM[d=1..oo] x^(2d^2)/(1 - x^d) * x^d = SUM[d=1..oo] x^(2d^2)/(1 - x^d) * (1 + x^d), as proposed. (End)

EXAMPLE

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

PROG

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 17 19:40 EST 2017. Contains 294834 sequences.