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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085945 Number of subsets of {1,2,..,n} with relatively prime elements. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Equals row sums of triangle A143446. [Gary W. Adamson, Aug 15 2008]

LINKS

T. D. Noe, Table of n, a(n) for n = 1..300

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.

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}.

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

Cf. A143446. [Gary W. Adamson, Aug 15 2008]

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 December 15 03:08 EST 2017. Contains 296020 sequences.