login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085945 Number of subsets of {1,2,...,n} with relatively prime elements. 6
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)

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 13:15 EST 2018. Contains 317149 sequences. (Running on oeis4.)