login
This site is supported by donations 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)
80
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, 26, 27, 28, 31, 34, 37, 38, 43, 46, 49, 50, 55, 60, 63, 66, 71, 78, 81, 84, 90, 98, 104, 107, 116, 124, 132, 135, 144, 154, 163, 169, 178, 192, 201, 209, 220, 235, 247, 256 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

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

REFERENCES

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

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

LINKS

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)

J. Bohman et al., Partitions in squares, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301.

J. Bohman et al., Partitions in squares, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301. (Annotated scanned copy)

H. L. Fisher, Letter to N. J. A. Sloane, Mar 16 1989

G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis, Proceedings of the London Mathematical Society, 2, XVI, 1917, p. 373.

M. D. Hirschhorn and J. A. Sellers, On a problem of Lehmer on partitions into squares, The Ramanujan Journal 8 (2004), 279-287.

F. Iacobescu, Smarandache Partition Type and Other Sequences, Bull. Pure Appl. Sci. 16E, 237-240, 1997.

Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449, 2018.

Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.

James A. Sellers, Partitions Excluding Specific Polygonal Numbers As Parts, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.

F. Smarandache, Sequences of Numbers Involved in Unsolved Problems, Hexis, Phoenix, 2006.

Florentin Smarandache, Sequences of Numbers Involved in Unsolved Problems, arXiv:math/0604019 [math.GM], 2006.

Eric Weisstein's World of Mathematics, Partition

Eric Weisstein's World of Mathematics, Smarandache Sequences

Eric Weisstein's World of Mathematics, Square Number

FORMULA

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

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

a(n) = 1/n*Sum_{k=1..n} A035316(k)*a(n-k). - Vladeta Jovovic, Nov 20 2002

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

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

From Vaclav Kotesovec, Dec 29 2016: (Start)

Correct values of these constants are:

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

alfa = 7/6 = 1.16666666666666666...

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

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]

(End)

EXAMPLE

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.

G.f.: A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 +...

such that the g.f. A(x) satisfies the identity [Paul D. Hanna]:

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

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)) + ...

MAPLE

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

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

    end:

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

seq(a(n), n=0..120);  # Alois P. Heinz, May 30 2014

MATHEMATICA

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

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

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

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 *)

PROG

(Haskell)

a001156 = p (tail a000290_list) where

   p _          0 = 1

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

-- Reinhard Zumkeller, Oct 31 2012, Aug 14 2011

(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 */

(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 */

CROSSREFS

Cf. A131799, A033461, A000041, A000290, A218494, A285218, A304046.

Cf. A078134 (first differences).

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

Row sums of A243148.

Sequence in context: A064475 A025774 A280168 * A199119 A035451 A304633

Adjacent sequences:  A001153 A001154 A001155 * A001157 A001158 A001159

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Eric W. Weisstein

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

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 October 16 10:09 EDT 2018. Contains 316262 sequences. (Running on oeis4.)