cp's OEIS Frontend

A001156 Number of partitions of n into squares.

%I A001156 M0221 N0079 #115 Feb 16 2025 08:32:22
%S A001156 1,1,1,1,2,2,2,2,3,4,4,4,5,6,6,6,8,9,10,10,12,13,14,14,16,19,20,21,23,
%T A001156 26,27,28,31,34,37,38,43,46,49,50,55,60,63,66,71,78,81,84,90,98,104,
%U A001156 107,116,124,132,135,144,154,163,169,178,192,201,209,220,235,247,256
%N A001156 Number of partitions of n into squares.
%C A001156 Number of partitions of n such that number of parts equal to k is multiple of k for all k. - _Vladeta Jovovic_, Aug 01 2004
%C A001156 Of course p_{4*square}(n)>0. In fact p_{4*square}(32n+28)=3 times p_{4*square}(8n+7) and p_{4*square}(72n+69) is even. These seem to be the only arithmetic properties the function p_{4*square(n)} possesses. Similar results hold for partitions into positive squares, distinct squares and distinct positive squares. - _Michael David Hirschhorn_, May 05 2005
%C A001156 The Heinz numbers of these partitions are given by A324588. - _Gus Wiseman_, Mar 09 2019
%D A001156 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001156 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001156 Alois P. Heinz, <a href="/A001156/b001156.txt">Table of n, a(n) for n = 0..10000</a> (first 1001 terms from T. D. Noe)
%H A001156 J. Bohman et al., <a href="http://dx.doi.org/10.1007/BF01930983">Partitions in squares</a>, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301.
%H A001156 J. Bohman et al., <a href="/A001156/a001156.pdf">Partitions in squares</a>, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301. (Annotated scanned copy)
%H A001156 H. L. Fisher, <a href="/A027601/a027601.pdf">Letter to N. J. A. Sloane, Mar 16 1989</a>
%H A001156 G. H. Hardy and S. Ramanujan, <a href="http://ramanujan.sirinudi.org/Volumes/published/ram33.html">Asymptotic formulae in combinatory analysis</a>, Proceedings of the London Mathematical Society, 2, XVI, 1917, p. 373.
%H A001156 M. D. Hirschhorn and J. A. Sellers, <a href="http://dx.doi.org/10.1007/s11139-004-0138-0">On a problem of Lehmer on partitions into squares</a>, The Ramanujan Journal 8 (2004), 279-287.
%H A001156 F. Iacobescu, <a href="http://www.gallup.unm.edu/~smarandache/SN/ScArt5/SPartitionType.pdf">Smarandache Partition Type and Other Sequences</a>, Bull. Pure Appl. Sci. 16E, 237-240, 1997.
%H A001156 Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449 [math.CO], 2018.
%H A001156 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H A001156 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.
%H A001156 F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/Sequences-book.pdf">Sequences of Numbers Involved in Unsolved Problems</a>, Hexis, Phoenix, 2006.
%H A001156 Florentin Smarandache, <a href="http://arxiv.org/abs/math/0604019">Sequences of Numbers Involved in Unsolved Problems</a>, arXiv:math/0604019 [math.GM], 2006.
%H A001156 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Partition.html">Partition</a>
%H A001156 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SmarandacheSequences.html">Smarandache Sequences</a>
%H A001156 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquareNumber.html">Square Number</a>
%F A001156 G.f.: Product_{m>=1} 1/(1-x^(m^2)).
%F A001156 G.f.: Sum_{n>=0} x^(n^2) / Product_{k=1..n} (1 - x^(k^2)). - _Paul D. Hanna_, Mar 09 2012
%F A001156 a(n) = (1/n)*Sum_{k=1..n} A035316(k)*a(n-k). - _Vladeta Jovovic_, Nov 20 2002
%F A001156 a(n) = f(n,1,3) with f(x,y,z) = if x<y then 0^x else f(x-y,y,z)+f(x,y+z,z+2). - _Reinhard Zumkeller_, Nov 08 2009
%F A001156 Conjecture (Jan Bohman, Carl-Erik Fröberg, Hans Riesel, 1979): a(n) ~ c * n^(-alfa) * exp(beta*n^(1/3)), where c = 1/18.79656, beta = 3.30716, alfa = 1.16022. - _Vaclav Kotesovec_, Aug 19 2015
%F A001156 From _Vaclav Kotesovec_, Dec 29 2016: (Start)
%F A001156 Correct values of these constants are:
%F A001156 1/c = sqrt(3) * (4*Pi)^(7/6) / Zeta(3/2)^(2/3) = 17.49638865935104978665...
%F A001156 alfa = 7/6 = 1.16666666666666666...
%F A001156 beta = 3/2 * (Pi/2)^(1/3) * Zeta(3/2)^(2/3) = 3.307411783596651987...
%F A001156 a(n) ~ 3^(-1/2) * (4*Pi*n)^(-7/6) * Zeta(3/2)^(2/3) * exp(2^(-4/3) * 3 * Pi^(1/3) * Zeta(3/2)^(2/3) * n^(1/3)). [Hardy & Ramanujan, 1917]
%F A001156 (End)
%e A001156 p_{4*square}(23)=1 because 23 = 3^2 + 3^2 + 2^2 + 1^2 and there is no other partition of 23 into squares.
%e A001156 G.f.: A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 +...
%e A001156 such that the g.f. A(x) satisfies the identity [_Paul D. Hanna_]:
%e A001156 A(x) = 1/((1-x)*(1-x^4)*(1-x^9)*(1-x^16)*(1-x^25)*...)
%e A001156 A(x) = 1 + x/(1-x) + x^4/((1-x)*(1-x^4)) + x^9/((1-x)*(1-x^4)*(1-x^9)) + x^16/((1-x)*(1-x^4)*(1-x^9)*(1-x^16)) + ...
%e A001156 From _Gus Wiseman_, Mar 09 2019: (Start)
%e A001156 The a(14) = 6 integer partitions into squares are:
%e A001156   (941)
%e A001156   (911111)
%e A001156   (44411)
%e A001156   (44111111)
%e A001156   (41111111111)
%e A001156   (11111111111111)
%e A001156 while the a(14) = 6 integer partitions in which the multiplicity of k is a multiple of k for all k are:
%e A001156   (333221)
%e A001156   (33311111)
%e A001156   (22222211)
%e A001156   (2222111111)
%e A001156   (221111111111)
%e A001156   (11111111111111)
%e A001156 (End)
%p A001156 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A001156       b(n, i-1)+ `if`(i^2>n, 0, b(n-i^2, i))))
%p A001156     end:
%p A001156 a:= n-> b(n, isqrt(n)):
%p A001156 seq(a(n), n=0..120);  # _Alois P. Heinz_, May 30 2014
%t A001156 CoefficientList[ Series[Product[1/(1 - x^(m^2)), {m, 70}], {x, 0, 68}], x] (* Or *)
%t A001156 Join[{1}, Table[Length@PowersRepresentations[n, n, 2], {n, 68}]] (* _Robert G. Wilson v_, Apr 12 2005, revised Sep 27 2011 *)
%t A001156 f[n_] := Length@ IntegerPartitions[n, All, Range@ Sqrt@ n^2]; Array[f, 67] (* _Robert G. Wilson v_, Apr 14 2013 *)
%t A001156 b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i^2>n, 0, b[n-i^2, i]]]]; a[n_] := b[n, Sqrt[n]//Floor]; Table[a[n], {n, 0, 120}] (* _Jean-François Alcover_, Nov 02 2015, after _Alois P. Heinz_ *)
%o A001156 (Haskell)
%o A001156 a001156 = p (tail a000290_list) where
%o A001156    p _          0 = 1
%o A001156    p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
%o A001156 -- _Reinhard Zumkeller_, Oct 31 2012, Aug 14 2011
%o A001156 (PARI) {a(n)=polcoeff(1/prod(k=1, sqrtint(n+1), 1-x^(k^2)+x*O(x^n)), n)} \\ _Paul D. Hanna_, Mar 09 2012
%o A001156 (PARI) {a(n)=polcoeff(1+sum(m=1, sqrtint(n+1), x^(m^2)/prod(k=1, m, 1-x^(k^2)+x*O(x^n))), n)} \\ _Paul D. Hanna_, Mar 09 2012
%o A001156 (Magma) m:=70; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!( (&*[1/(1-x^(k^2)): k in [1..(m+2)]]) )); // _G. C. Greubel_, Nov 11 2018
%Y A001156 Cf. A000041, A000161 (partitions into 2 squares), A000290, A033461, A131799, A218494, A285218, A304046.
%Y A001156 Cf. A078134 (first differences).
%Y A001156 Cf. A003108, A037444, A046042, A259792, A259793, A294529.
%Y A001156 Row sums of A243148.
%Y A001156 Euler trans. of A010052 (see also A308297).
%Y A001156 Cf. A001462, A003114, A006141, A011757, A039900, A047993, A052335, A062457, A064174, A078135, A109298, A117144.
%Y A001156 Cf. A324524, A324572, A324587, A324588.
%K A001156 nonn,easy
%O A001156 0,5
%A A001156 _N. J. A. Sloane_
%E A001156 More terms from _Eric W. Weisstein_
%E A001156 More terms from Gh. Niculescu (ghniculescu(AT)yahoo.com), Oct 08 2006