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

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

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 August 20 17:26 EDT 2017. Contains 290837 sequences.