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

1, 1, 1, 1, 2, 3, 4, 5, 7, 11, 16, 22, 30, 43, 62, 88, 124, 175, 249, 354, 502, 710, 1006, 1427, 2024, 2870, 4068, 5767, 8176, 11593, 16436, 23301, 33033, 46832, 66398, 94137, 133462, 189211, 268252, 380315, 539192, 764433, 1083764, 1536498, 2178364

Offset

0,5

References

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

Links

Seiichi Manyama, Table of n, a(n) for n = 0..5000 (terms 0..500 from T. D. Noe)

Jan Bohman, Carl-Erik Fröberg, Hans Riesel, 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)

N. Robbins, On compositions whose parts are polygonal numbers, Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 239-243. See p. 242.

Index entries for sequences related to sums of squares

Formula

a(n) = 1, if n = 0; a(n)=Sum(1 <= k^2 <= n, a(n-k^2)), if n > 0. - David W. Wilson

G.f.: 1/(1-x-x^4-x^9-....) - Jon Perry, Jul 04 2004

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

G.f.: 2/(3 - theta_3(q)), where theta_3() is the Jacobi theta function. - Ilya Gutkovskiy, Aug 08 2018

Mathematica

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

Prog

(PARI)
N=66;  x='x+O('x^N);
Vec( 1/( 1 - sum(k=1, 1+sqrtint(N), x^(k^2) ) ) )
/* Joerg Arndt, Sep 30 2012 */
(Python)
from gmpy2 import is_square
class Memoize:
    def __init__(self, func):
        self.func=func
        self.cache={}
    def __call__(self, arg):
        if arg not in self.cache:
            self.cache[arg] = self.func(arg)
        return self.cache[arg]
@Memoize
def a(n): return 1 if n==0 else sum([a(n - k) for k in range(1, n + 1) if is_square(k)])
print([a(n) for n in range(101)]) # Indranil Ghosh, Jul 28 2017, after David W. Wilson's formula

Crossrefs

Cf. A280542.

Row sums of A337165.

Sequence in context: A046420 A108318 A358876 * A018134 A245823 A143284

Adjacent sequences: A006453 A006454 A006455 * A006457 A006458 A006459

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Name corrected by Bob Selcoe, Feb 12 2014

Status

approved