A089887 Number of subsets of {1,.., n} containing no squares.

1, 2, 4, 4, 8, 16, 32, 64, 64, 128, 256, 512, 1024, 2048, 4096, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456

Offset

1,2

Comments

a(n) = Product(2-A010052(k): 1<=k<=n) = A089886(n,0) = A000079(n)-A089888(n).

Links

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

Index to divisibility sequences

Formula

a(n) = 2^(n-n^(1/2)).

Prog

(PARI) a(n)=2^(n-sqrtint(n)) \\ Charles R Greathouse IV, Apr 09 2012

Crossrefs

Cf. A089889, A089890.

Sequence in context: A321241 A290128 A291778 * A161816 A374821 A240347

Adjacent sequences: A089884 A089885 A089886 * A089888 A089889 A089890

Keyword

nonn

Author

Reinhard Zumkeller, Nov 13 2003

Status

approved