A224840 Divisor sum of the arithmetic function A085945(n).

1, 3, 6, 14, 27, 61, 117, 250, 494, 1012, 2007, 4088, 8112, 16357, 32635, 65493, 130779, 262115, 523710, 1048502, 2096110, 4194124, 8386419, 16777182, 33550085, 67108507, 134209495, 268434899, 536853987, 1073741664, 2147449815, 4294966187, 8589868975, 17179866799

Offset

1,2

Comments

Also the number of subsets A of {1, 2, 3, ..., n} such that gcd(A) divides n.

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..3321

P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 and J. Int. Seq. 16 (2013) #13.9.1.

P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.

Formula

a(n) = sum{d | n} sum_{k <= d} mu(k)*(2^floor(n/k) - 1) where mu is the Moebius function.

Prog

(PARI) A085945(n)=sum(k=1, n, moebius(k)*(2^(n\k)-1))
a(n)=sumdiv(n, d, A085945(d)) \\ Charles R Greathouse IV, Sep 19 2013
(PARI) a(n)=my(v=vector(n, i, i)); sum(i=1, 2^n-1, n%gcd(vecextract(v, i))==0) \\ Charles R Greathouse IV, Sep 19 2013

Crossrefs

Cf. A038199, A027375, Divisor sums of A085945.

Sequence in context: A030012 A001970 A006951 * A356804 A345334 A354294

Adjacent sequences: A224837 A224838 A224839 * A224841 A224842 A224843

Keyword

nonn

Author

Prapanpong Pongsriiam, Sep 18 2013

Extensions

a(19)-a(34) from Charles R Greathouse IV, Sep 19 2013

Status

approved