|
%I #52 Sep 15 2021 03:28:41
%S 1,2,5,11,26,53,116,236,488,983,2006,4016,8111,16238,32603,65243,
%T 130778,261566,523709,1047479,2095988,4192115,8386418,16772858,
%U 33550058,67100393,134209001,268418531,536853986,1073707991,2147449814,4294900694,8589866963
%N Number of subsets of {1,2,...,n} with relatively prime elements.
%H Alois P. Heinz, <a href="/A085945/b085945.txt">Table of n, a(n) for n = 1..3321</a> (first 300 terms from T. D. Noe)
%H Mohamed Ayad and Omar Kihel, <a href="https://doi.org/10.1515/INTEG.2009.015">The number of relatively prime subsets of {1,2,...,n}</a>, Integers 9, No. 2, Article A14, 163-166 (2009).
%H M. Ayad, V. Coia and O. Kihel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Kihel/kihel10.html">The Number of Relatively Prime Subsets of a Finite Union of Sets of Consecutive Integers</a>, J. Int. Seq. 17 (2014) # 14.3.7, Theorem 1.
%H Mohamed El Bachraoui and Florian Luca, <a href="http://dx.doi.org/10.2989/16073606.2012.697265">On a Diophantine equation of Ayad and Kihel</a>, Quaestiones Mathematicae, Volume 35, Issue 2, pages 235-243, 2012; DOI:10.2989/16073606.2012.697265. - _N. J. A. Sloane_, Nov 29 2012
%H Adrian Łydka, <a href="https://arxiv.org/abs/1910.02418">On some properties of the function of the number of relatively prime subsets of {1,2,...,n}</a>, arXiv:1910.02418 [math.NT], 2019.
%H Melvyn B. Nathanson, <a href="http://www.emis.de/journals/INTEGERS/papers/h1/h1.Abstract.html">Affine Invariants, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ..., n}</a>, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A1.
%H P. Pongsriiam, <a href="http://arxiv.org/abs/1306.4891">Relatively Prime Sets, Divisor Sums, and Partial Sums</a>, arXiv:1306.4891 [math.NT], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Pongsriiam/pong2.html">J. Int. Seq. 16 (2013) #13.9.1</a>.
%H P. Pongsriiam, <a href="http://arxiv.org/abs/1306.2529">A remark on relative prime sets</a>, arXiv:1306.2529 [math.NT], 2013.
%H P. Pongsriiam, <a href="http://www.emis.de/journals/INTEGERS/papers/n49/n49.Abstract.html">A remark on relative prime sets</a>, Integers 13 (2013), A49.
%H M. Tang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Tang/tang2.html">Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ... , n}</a>, J. Int. Seq. 13 (2010) # 10.7.6.
%H László Tóth, <a href="https://arxiv.org/abs/2109.06541">Menon-type identities concerning subsets of the set {1,2,...,n}</a>, arXiv:2109.06541 [math.NT], 2021.
%F Partial sums of A000740. G.f.: 1/(1-x)* Sum_{k>0} mu(k)*x^k/(1-2*x^k).
%F a(n) = 2^n - A109511(n) - 1. - _Reinhard Zumkeller_, Jul 01 2005
%F a(n) = Sum_{k=1..n} mu(k)*(2^floor(n/k)-1). - _Geoffrey Critzer_, Jan 03 2012
%e 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}.
%p b:= n-> add(`if`(d=n, 2^(n-1), -b(d)), d=numtheory[divisors](n)):
%p a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
%p seq(a(n), n=1..35); # _Alois P. Heinz_, Oct 05 2018
%t Table[Sum[MoebiusMu[k] (2^Floor[n/k] - 1), {k, 1, n}], {n, 1, 31}] (* _Geoffrey Critzer_, Jan 03 2012 *)
%o (PARI) a(n)=sum(k=1,n,moebius(k)*(2^floor(n/k)-1)) \\ _Charles R Greathouse IV_, Feb 04 2013
%Y Cf. A000740, A109511.
%Y Row sums of A143446.
%Y Column k=2 of A143327.
%K nonn
%O 1,2
%A _Vladeta Jovovic_, Aug 17 2003
|
