OFFSET
1,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..3321 (first 300 terms from T. D. Noe)
Mohamed Ayad and Omar Kihel, The number of relatively prime subsets of {1,2,...,n}, Integers 9, No. 2, Article A14, 163-166 (2009).
M. Ayad, V. Coia and O. Kihel, The Number of Relatively Prime Subsets of a Finite Union of Sets of Consecutive Integers, J. Int. Seq. 17 (2014) # 14.3.7, Theorem 1.
Mohamed El Bachraoui and Florian Luca, On a Diophantine equation of Ayad and Kihel, Quaestiones Mathematicae, Volume 35, Issue 2, pages 235-243, 2012; DOI:10.2989/16073606.2012.697265. - N. J. A. Sloane, Nov 29 2012
Adrian Łydka, On some properties of the function of the number of relatively prime subsets of {1,2,...,n}, arXiv:1910.02418 [math.NT], 2019.
Melvyn B. Nathanson, Affine Invariants, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ..., n}, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A1.
P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 [math.NT], 2013 and J. Int. Seq. 16 (2013) #13.9.1.
P. Pongsriiam, A remark on relative prime sets, arXiv:1306.2529 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.
M. Tang, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ... , n}, J. Int. Seq. 13 (2010) # 10.7.6.
László Tóth, Menon-type identities concerning subsets of the set {1,2,...,n}, arXiv:2109.06541 [math.NT], 2021.
FORMULA
Partial sums of A000740. G.f.: 1/(1-x)* Sum_{k>0} mu(k)*x^k/(1-2*x^k).
a(n) = 2^n - A109511(n) - 1. - Reinhard Zumkeller, Jul 01 2005
a(n) = Sum_{k=1..n} mu(k)*(2^floor(n/k)-1). - Geoffrey Critzer, Jan 03 2012
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:
seq(a(n), n=1..35); # Alois P. Heinz, Oct 05 2018
MATHEMATICA
Table[Sum[MoebiusMu[k] (2^Floor[n/k] - 1), {k, 1, n}], {n, 1, 31}] (* Geoffrey Critzer, Jan 03 2012 *)
PROG
(PARI) a(n)=sum(k=1, n, moebius(k)*(2^floor(n/k)-1)) \\ Charles R Greathouse IV, Feb 04 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladeta Jovovic, Aug 17 2003
STATUS
approved