login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006456 Number of compositions (ordered partitions) of n into squares.
(Formerly M0528)
26
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 (list; graph; refs; listen; history; text; internal format)
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 xrange(1, n + 1) if is_square(k)])

print map(a, xrange(101)) # Indranil Ghosh, Jul 28 2017, after David W. Wilson's formula

CROSSREFS

Cf. A280542.

Sequence in context: A259466 A046420 A108318 * A018134 A245823 A143284

Adjacent sequences:  A006453 A006454 A006455 * A006457 A006458 A006459

KEYWORD

nonn,easy,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Name corrected by Bob Selcoe, Feb 12 2014

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 August 18 22:07 EDT 2018. Contains 313840 sequences. (Running on oeis4.)