login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001156 Number of partitions of n into squares.
(Formerly M0221 N0079)
110

%I M0221 N0079 #112 Oct 27 2023 19:13:15

%S 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 26,27,28,31,34,37,38,43,46,49,50,55,60,63,66,71,78,81,84,90,98,104,

%U 107,116,124,132,135,144,154,163,169,178,192,201,209,220,235,247,256

%N Number of partitions of n into squares.

%C 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 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 The Heinz numbers of these partitions are given by A324588. - _Gus Wiseman_, Mar 09 2019

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 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 H. L. Fisher, <a href="/A027601/a027601.pdf">Letter to N. J. A. Sloane, Mar 16 1989</a>

%H 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 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 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 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 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Partition.html">Partition</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SmarandacheSequences.html">Smarandache Sequences</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquareNumber.html">Square Number</a>

%F G.f.: Product_{m>=1} 1/(1-x^(m^2)).

%F G.f.: Sum_{n>=0} x^(n^2) / Product_{k=1..n} (1 - x^(k^2)). - _Paul D. Hanna_, Mar 09 2012

%F a(n) = (1/n)*Sum_{k=1..n} A035316(k)*a(n-k). - _Vladeta Jovovic_, Nov 20 2002

%F 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 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 From _Vaclav Kotesovec_, Dec 29 2016: (Start)

%F Correct values of these constants are:

%F 1/c = sqrt(3) * (4*Pi)^(7/6) / Zeta(3/2)^(2/3) = 17.49638865935104978665...

%F alfa = 7/6 = 1.16666666666666666...

%F beta = 3/2 * (Pi/2)^(1/3) * Zeta(3/2)^(2/3) = 3.307411783596651987...

%F 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 (End)

%e 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 G.f.: A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 +...

%e such that the g.f. A(x) satisfies the identity [_Paul D. Hanna_]:

%e A(x) = 1/((1-x)*(1-x^4)*(1-x^9)*(1-x^16)*(1-x^25)*...)

%e 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 From _Gus Wiseman_, Mar 09 2019: (Start)

%e The a(14) = 6 integer partitions into squares are:

%e (941)

%e (911111)

%e (44411)

%e (44111111)

%e (41111111111)

%e (11111111111111)

%e while the a(14) = 6 integer partitions in which the multiplicity of k is a multiple of k for all k are:

%e (333221)

%e (33311111)

%e (22222211)

%e (2222111111)

%e (221111111111)

%e (11111111111111)

%e (End)

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p b(n, i-1)+ `if`(i^2>n, 0, b(n-i^2, i))))

%p end:

%p a:= n-> b(n, isqrt(n)):

%p seq(a(n), n=0..120); # _Alois P. Heinz_, May 30 2014

%t CoefficientList[ Series[Product[1/(1 - x^(m^2)), {m, 70}], {x, 0, 68}], x] (* Or *)

%t Join[{1}, Table[Length@PowersRepresentations[n, n, 2], {n, 68}]] (* _Robert G. Wilson v_, Apr 12 2005, revised Sep 27 2011 *)

%t f[n_] := Length@ IntegerPartitions[n, All, Range@ Sqrt@ n^2]; Array[f, 67] (* _Robert G. Wilson v_, Apr 14 2013 *)

%t 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 (Haskell)

%o a001156 = p (tail a000290_list) where

%o p _ 0 = 1

%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Oct 31 2012, Aug 14 2011

%o (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 (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 (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 Cf. A000041, A000290, A033461, A131799, A218494, A285218, A304046.

%Y Cf. A078134 (first differences).

%Y Cf. A003108, A037444, A046042, A259792, A259793, A294529.

%Y Row sums of A243148.

%Y Euler trans. of A010052 (see also A308297).

%Y Cf. A001462, A003114, A006141, A011757, A039900, A047993, A052335, A062457, A064174, A078135, A109298, A117144.

%Y Cf. A324524, A324572, A324587, A324588.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _Eric W. Weisstein_

%E More terms from Gh. Niculescu (ghniculescu(AT)yahoo.com), Oct 08 2006

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:01 EDT 2024. Contains 371235 sequences. (Running on oeis4.)