|
|
A085945
|
|
Number of subsets of {1,2,...,n} with relatively prime elements.
|
|
24
|
|
|
1, 2, 5, 11, 26, 53, 116, 236, 488, 983, 2006, 4016, 8111, 16238, 32603, 65243, 130778, 261566, 523709, 1047479, 2095988, 4192115, 8386418, 16772858, 33550058, 67100393, 134209001, 268418531, 536853986, 1073707991, 2147449814, 4294900694, 8589866963
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
Partial sums of A000740. G.f.: 1/(1-x)* Sum_{k>0} mu(k)*x^k/(1-2*x^k).
|
|
EXAMPLE
|
For n=4 there are 11 such subsets: {1}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}.
|
|
MAPLE
|
b:= n-> add(`if`(d=n, 2^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
|
|
MATHEMATICA
|
Table[Sum[MoebiusMu[k] (2^Floor[n/k] - 1), {k, 1, n}], {n, 1, 31}] (* Geoffrey Critzer, Jan 03 2012 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|