login
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
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
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, A remark on relative prime sets, arXiv:1306.2529 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.
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
Row sums of A143446.
Column k=2 of A143327.
Sequence in context: A053429 A266879 A104237 * A365322 A371662 A005469
KEYWORD
nonn
AUTHOR
Vladeta Jovovic, Aug 17 2003
STATUS
approved