%I M0528 #70 Feb 04 2021 15:21:57
%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.
%Y Row sums of A337165.
%K nonn,easy
%O 0,5
%A _N. J. A. Sloane_
%E Name corrected by _Bob Selcoe_, Feb 12 2014