login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..3321 (first 300 terms from T. D. Noe)

Ayad, Mohamed; Kihel, Omar, The number of relatively prime subsets of {1,2,...,n}, Integers 9, No. 2, Article A14, 163-166 (2009).

M. Ayad, V. Coia, 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.

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 * A005469 A218575 A159929

Adjacent sequences:  A085942 A085943 A085944 * A085946 A085947 A085948

KEYWORD

nonn

AUTHOR

Vladeta Jovovic, Aug 17 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 13 08:26 EDT 2020. Contains 335685 sequences. (Running on oeis4.)