login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006456 Number of compositions (ordered partitions) of n into squares.
(Formerly M0528)
37

%I M0528

%S 1,1,1,1,2,3,4,5,7,11,16,22,30,43,62,88,124,175,249,354,502,710,1006,

%T 1427,2024,2870,4068,5767,8176,11593,16436,23301,33033,46832,66398,

%U 94137,133462,189211,268252,380315,539192,764433,1083764,1536498,2178364

%N Number of compositions (ordered partitions) of n into squares.

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

%H Seiichi Manyama, <a href="/A006456/b006456.txt">Table of n, a(n) for n = 0..5000</a> (terms 0..500 from T. D. Noe)

%H Jan Bohman, Carl-Erik Fröberg, Hans Riesel, <a href="https://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 N. Robbins, <a href="http://ac.inf.elte.hu/Vol_043_2014/239_43.pdf">On compositions whose parts are polygonal numbers</a>, Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 239-243. See p. 242.

%H <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>

%F a(n) = 1, if n = 0; a(n)=Sum(1 <= k^2 <= n, a(n-k^2)), if n > 0. - _David W. Wilson_

%F G.f.: 1/(1-x-x^4-x^9-....) - _Jon Perry_, Jul 04 2004

%F a(n) ~ c * d^n, where d is the root of the equation EllipticTheta(3, 0, 1/d) = 3, d = 1.41774254618138831428829091099000662953179532057717725688..., c = 0.46542113389379672452973940263069782869244877335179331541... - _Vaclav Kotesovec_, May 01 2014, updated Jan 05 2017

%F G.f.: 2/(3 - theta_3(q)), where theta_3() is the Jacobi theta function. - _Ilya Gutkovskiy_, Aug 08 2018

%t a[n_]:=a[n]=If[n==0, 1, Sum[a[n - k], {k, Select[Range[n], IntegerQ[Sqrt[#]] &]}]]; Table[a[n], {n,0, 100}] (* _Indranil Ghosh_, Jul 28 2017, after _David W. Wilson_'s formula *)

%o (PARI)

%o N=66; x='x+O('x^N);

%o Vec( 1/( 1 - sum(k=1,1+sqrtint(N), x^(k^2) ) ) )

%o /* _Joerg Arndt_, Sep 30 2012 */

%o (Python)

%o from gmpy2 import is_square

%o class Memoize:

%o def __init__(self, func):

%o self.func=func

%o self.cache={}

%o def __call__(self, arg):

%o if arg not in self.cache:

%o self.cache[arg] = self.func(arg)

%o return self.cache[arg]

%o @Memoize

%o def a(n): return 1 if n==0 else sum([a(n - k) for k in range(1, n + 1) if is_square(k)])

%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jul 28 2017, after _David W. Wilson_'s formula

%Y Cf. A280542.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_

%E Name corrected by _Bob Selcoe_, Feb 12 2014

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:52 EDT 2020. Contains 334671 sequences. (Running on oeis4.)