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

Author

Prapanpong Pongsriiam, Sep 18 2013

Keywords

• nonn

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.

Crossrefs

Cf. A038199, A027375, Divisor sums of A085945.

Programs

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

Formula

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

Extensions

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