CINXE.COM
A087153 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A087153 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A087153" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA087153">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A087153 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A087153 </div> <div class=seqname> Number of partitions of n into nonsquares. </div> </div> <div class=scorerefs> 27 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 0, 1, 1, 1, 2, 3, 3, 5, 5, 8, 9, 13, 15, 20, 24, 30, 37, 47, 55, 71, 83, 103, 123, 151, 178, 218, 257, 310, 366, 440, 515, 617, 722, 857, 1003, 1184, 1380, 1625, 1889, 2214, 2570, 3000, 3472, 4042, 4669, 5414, 6244, 7221, 8303, 9583, 10998, 12655, 14502</div> <div class=seqdatalinks> (<a href="/A087153/list">list</a>; <a href="/A087153/graph">graph</a>; <a href="/search?q=A087153+-id:A087153">refs</a>; <a href="/A087153/listen">listen</a>; <a href="/history?seq=A087153">history</a>; <a href="/search?q=id:A087153&fmt=text">text</a>; <a href="/A087153/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,6</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>Also, number of partitions of n where there are fewer than k parts equal to k for all k. - <a href="/wiki/User:Jon_Perry">Jon Perry</a> and <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Aug 04 2004. E.g. a(8)=5 because we have 8=6+2=5+3=4+4=3+3+2.</div> <div class=sectline>Convolution of <a href="/A276516" title="Expansion of Product_{k>=1} (1-x^(k^2)).">A276516</a> and <a href="/A000041" title="a(n) is the number of partitions of n (the partition numbers).">A000041</a>. - <a href="/wiki/User:Vaclav_Kotesovec">Vaclav Kotesovec</a>, Dec 30 2016</div> <div class=sectline>From <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Apr 02 2019: (Start)</div> <div class=sectline>The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). The Heinz numbers of the integer partitions described in Perry and Jovovic's comment are given by <a href="/A325128" title="Numbers in whose prime factorization the exponent of prime(k) is less than k for all prime indices k.">A325128</a>, while the Heinz numbers of the integer partitions described in the name are given by <a href="/A325129" title="Heinz numbers of integer partitions into nonsquares (A087153).">A325129</a>. In the former case, the first 10 terms count the following integer partitions:</div> <div class=sectline> () (2) (3) (4) (5) (6) (7) (8) (9)</div> <div class=sectline> (32) (33) (43) (44) (54)</div> <div class=sectline> (42) (52) (53) (63)</div> <div class=sectline> (62) (72)</div> <div class=sectline> (332) (432)</div> <div class=sectline>while in the latter case they count the following:</div> <div class=sectline> () (2) (3) (22) (5) (6) (7) (8) (63)</div> <div class=sectline> (32) (33) (52) (53) (72)</div> <div class=sectline> (222) (322) (62) (333)</div> <div class=sectline> (332) (522)</div> <div class=sectline> (2222) (3222)</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>G. E. Andrews, K. Eriksson, Integer Partitions, Cambridge Univ. Press, 2004. See page 48.</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>T. D. Noe and Vaclav Kotesovec, <a href="/A087153/b087153.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)</div> <div class=sectline>Daniel I. A. Cohen, <a href="https://dx.doi.org/10.1016/0097-3165(81)90057-1">PIE-sums: a combinatorial tool for partition theory</a>. J. Combin. Theory Ser. A 31 (1981), no. 3, 223--236. MR0635367 (82m:10026). See Cor. 5. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Mar 27 2012</div> <div class=sectline>James A. Sellers, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Sellers/sellers58.html">Partitions Excluding Specific Polygonal Numbers As Parts</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.</div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>G.f.: Product_{m>0} (1-x^(m^2))/(1-x^m). - <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Aug 21 2003</div> <div class=sectline>a(n) = (1/n)*Sum_{k=1..n} (<a href="/A000203" title="a(n) = sigma(n), the sum of the divisors of n. Also called sigma_1(n).">A000203</a>(k)-<a href="/A035316" title="Sum of the square divisors of n.">A035316</a>(k))*a(n-k), a(0)=1. - <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Aug 21 2003</div> <div class=sectline>G.f.: Product_{i>=1} (Sum_{j=0..i-1} x^(i*j)). - <a href="/wiki/User:Jon_Perry">Jon Perry</a>, Jul 26 2004</div> <div class=sectline>a(n) ~ exp(Pi*sqrt(2*n/3) - 3^(1/4) * Zeta(3/2) * n^(1/4) / 2^(3/4) - 3*Zeta(3/2)^2/(32*Pi)) * sqrt(Pi) / (2^(3/4) * 3^(1/4) * n^(3/4)). - <a href="/wiki/User:Vaclav_Kotesovec">Vaclav Kotesovec</a>, Dec 30 2016</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>n=7: 2+5 = 2+2+3 = 7: a(7)=3;</div> <div class=sectline>n=8: 2+6 = 2+2+2+2 = 2+3+3 = 3+5 = 8: a(8)=5;</div> <div class=sectline>n=9: 2+7 = 2+2+5 = 2+2+2+3 = 3+3+3 = 3+6: a(9)=5.</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline>g:=product((1-x^(i^2))/(1-x^i), i=1..70):gser:=series(g, x=0, 60):seq(coeff(gser, x^n), n=1..53); # <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, Feb 09 2006</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>nn=54; CoefficientList[ Series[ Product[ Sum[x^(i*j), {j, 0, i - 1}], {i, 1, nn}], {x, 0, nn}], x] (* <a href="/wiki/User:Robert_G._Wilson_v">Robert G. Wilson v</a>, Aug 05 2004 *)</div> <div class=sectline>nmax = 100; CoefficientList[Series[Product[(1 - x^(k^2))/(1 - x^k), {k, 1, nmax}], {x, 0, nmax}], x] (* <a href="/wiki/User:Vaclav_Kotesovec">Vaclav Kotesovec</a>, Dec 29 2016 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(Haskell)</div> <div class=sectline>a087153 = p a000037_list where</div> <div class=sectline> p _ 0 = 1</div> <div class=sectline> p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Apr 25 2013</div> <div class=sectline>(PARI) first(n)=my(x='x+O('x^(n+1))); Vec(prod(m=1, sqrtint(n), (1-x^m^2)/(1-x^m))*prod(m=sqrtint(n)+1, n, 1/(1-x^m))) \\ <a href="/wiki/User:Charles_R_Greathouse_IV">Charles R Greathouse IV</a>, Aug 28 2016</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Cf. <a href="/A087154" title="Number of partitions of n into distinct nonsquares.">A087154</a>, <a href="/A001156" title="Number of partitions of n into squares.">A001156</a>, <a href="/A000009" title="Expansion of Product_{m >= 1} (1 + x^m); number of partitions of n into distinct parts; number of partitions of n into odd p...">A000009</a>, <a href="/A000037" title="Numbers that are not squares (or, the nonsquares).">A000037</a>, <a href="/A052335" title="Number of partitions of n into at most 1 copy of 1, 2 copies of 2, 3 copies of 3, ... .">A052335</a> (<=k parts of k).</div> <div class=sectline>Cf. <a href="/A115584" title="Number of partitions of n in which each part k occurs more than k times.">A115584</a>, <a href="/A172151" title="Number of partitions of n into two nonsquares.">A172151</a>, <a href="/A225044" title="Number of partitions of n into non-triangular numbers, cf. A014132.">A225044</a>, <a href="/A264393" title="Number of partitions of n having no perfect cube parts (n>=0).">A264393</a>, <a href="/A276516" title="Expansion of Product_{k>=1} (1-x^(k^2)).">A276516</a>.</div> <div class=sectline>Cf. <a href="/A033461" title="Number of partitions of n into distinct squares.">A033461</a>, <a href="/A114639" title="Number of partitions of n such that the set of parts and the set of multiplicities of parts are disjoint.">A114639</a>, <a href="/A117144" title="Partitions of n in which each part k occurs at least k times.">A117144</a>, <a href="/A276429" title="Number of partitions of n containing no part i of multiplicity i.">A276429</a>, <a href="/A324572" title="Number of integer partitions of n whose multiplicities (where if x < y the multiplicity of x is counted prior to the multipl...">A324572</a>, <a href="/A324588" title="Heinz numbers of integer partitions of n into perfect squares (A001156).">A324588</a>, <a href="/A325128" title="Numbers in whose prime factorization the exponent of prime(k) is less than k for all prime indices k.">A325128</a>, <a href="/A325129" title="Heinz numbers of integer partitions into nonsquares (A087153).">A325129</a>.</div> <div class=sectline>Sequence in context: <a href="/A120249" title="Numerator of cfenc[n] (see definition in comments).">A120249</a> <a href="/A058690" title="McKay-Thompson series of class 47A for the Monster group.">A058690</a> <a href="/A290369" title="Number of partitions of n into parts that contain primes to odd powers only (A002035).">A290369</a> * <a href="/A240176" title="Number of partitions of n such that (least part) > (multiplicity of least part).">A240176</a> <a href="/A134408" title="First differences of A006336.">A134408</a> <a href="/A051032" title="Summatory Rudin-Shapiro sequence for 2^(n-1).">A051032</a></div> <div class=sectline>Adjacent sequences: <a href="/A087150" title="Monotonically increasing sequence of least positive integers, a(1)=1, such that the self-convolution produces all squares.">A087150</a> <a href="/A087151" title="Positive square-root of terms of the self-convolution of A087150.">A087151</a> <a href="/A087152" title="Expansion of (1-sqrt(1-4*log(1+x)))/log(1+x)/2.">A087152</a> * <a href="/A087154" title="Number of partitions of n into distinct nonsquares.">A087154</a> <a href="/A087155" title="Primes having nontrivial palindromic representation in some (at least one) base.">A087155</a> <a href="/A087156" title="Nonnegative numbers excluding 1.">A087156</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Aug 21 2003</div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>Zeroth term added by <a href="/wiki/User:Franklin_T._Adams-Watters">Franklin T. Adams-Watters</a>, Jan 25 2010</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified April 8 13:02 EDT 2025. Contains 382588 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>