cp's OEIS Frontend

A006456 Number of compositions (ordered partitions) of n into squares.

%I A006456 M0528 #74 Jul 26 2025 17:18:49
%S A006456 1,1,1,1,2,3,4,5,7,11,16,22,30,43,62,88,124,175,249,354,502,710,1006,
%T A006456 1427,2024,2870,4068,5767,8176,11593,16436,23301,33033,46832,66398,
%U A006456 94137,133462,189211,268252,380315,539192,764433,1083764,1536498,2178364
%N A006456 Number of compositions (ordered partitions) of n into squares.
%D A006456 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006456 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 A006456 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 A006456 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 A006456 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 A006456 <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>
%F A006456 a(0) = 1; a(n) = Sum_{1 <= k^2 <= n} a(n-k^2), if n > 0. - _David W. Wilson_
%F A006456 G.f.: 1/(1-x-x^4-x^9-....) - _Jon Perry_, Jul 04 2004
%F A006456 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 A006456 G.f.: 2/(3 - theta_3(q)), where theta_3() is the Jacobi theta function. - _Ilya Gutkovskiy_, Aug 08 2018
%p A006456 a:= proc(n) option remember; `if`(n<0, 0,
%p A006456       `if`(n=0, 1, add(a(n-j^2), j=1..isqrt(n))))
%p A006456     end:
%p A006456 seq(a(n), n=0..44);  # _Alois P. Heinz_, Jul 26 2025
%t A006456 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 A006456 (PARI)
%o A006456 N=66;  x='x+O('x^N);
%o A006456 Vec( 1/( 1 - sum(k=1,1+sqrtint(N), x^(k^2) ) ) )
%o A006456 /* _Joerg Arndt_, Sep 30 2012 */
%o A006456 (Python)
%o A006456 from gmpy2 import is_square
%o A006456 class Memoize:
%o A006456     def __init__(self, func):
%o A006456         self.func=func
%o A006456         self.cache={}
%o A006456     def __call__(self, arg):
%o A006456         if arg not in self.cache:
%o A006456             self.cache[arg] = self.func(arg)
%o A006456         return self.cache[arg]
%o A006456 @Memoize
%o A006456 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 A006456 print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jul 28 2017, after _David W. Wilson_'s formula
%Y A006456 Cf. A280542.
%Y A006456 Row sums of A337165.
%K A006456 nonn,easy
%O A006456 0,5
%A A006456 _N. J. A. Sloane_
%E A006456 Name corrected by _Bob Selcoe_, Feb 12 2014