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!)
A078134 Number of ways to write n as sum of squares > 1. 33
0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 2, 1, 1, 0, 2, 1, 1, 0, 2, 3, 1, 1, 2, 3, 1, 1, 3, 3, 3, 1, 5, 3, 3, 1, 5, 5, 3, 3, 5, 7, 3, 3, 6, 8, 6, 3, 9, 8, 8, 3, 9, 10, 9, 6, 9, 14, 9, 8, 11, 15, 12, 9, 15, 15, 16, 9, 18, 18, 18, 13, 19, 23, 18, 17, 21, 28, 22, 19, 26, 30, 28, 19, 31, 34, 34 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,16

COMMENTS

a(A078135(n))=0; a(A078136(n))=1; a(A078137(n))>0;

Conjecture (lower bound): for all k exists b(k) such that a(n)>k for n>b(k); see b(0)=A078135(12)=23 and b(1)=A078136(15)=39. This is true - see comments by Hieronymus Fischer.

Also first difference of A001156 (number of partitions of n into squares). - Wouter Meeussen, Oct 22 2005

Comments from Hieronymus Fischer, Nov 11 2007 (Start): First statement of monotony: a(n+k^2)>=a(n) for all k>1. Proof: we restrict ourselves on a(n)>0 (the case a(n)=0 is trivial). Let T(i), 1<=i<=a(n), be the a(n) different sum expressions of squares >1 representing n. Then, adding k^2 to those expressions, we get a(n) sums of squares T(i)+k^2, obviously representing n+k^2, thus a(n+k^2) cannot be less than a(n).

Second statement of monotony: a(n+m)>=max(a(n),a(m)) for all m with a(m)>1. Proof: let T(i), 1<=i<=a(n), be the a(n) different sum expressions of squares >1 representing n; let S(i), 1<=i<=a(m), be the a(m) different sum expressions of squares >1 representing m. Then, adding those expressions, we get a(n) sums of squares T(i)+S(1), representing n+m, further we get a(m) sums T(1)+S(i), also representing n+m, thus a(n+m) cannot be less than the maximum of a(n) and a(m).

The author's conjecture holds true. Proof by induction: b(0) exists; if b(k) exists, then a(j)>k for all j>b(k). Setting m:=b(k)+1, we find that there are k+1 sums B(0,i) of squares >1, 1<=i<=k+1, with m=B(0,i). Further there are k+1 such sum expressions B(1,i), B(2,i) and B(3,i), 1<=i<=k+1, representing m+1, m+2 and m+3, respectively. For n>b(k) we have n=m+4*floor((n-m)/4)+(n-m) mod 4.

Thus n=m+r+s*2^2, where r=0,1,2 or 3. Hence n can be written B(r,i)+s*2^2 and there are k+1 such representations. Let q be the maximal number (to be squared) occurring as a term within those sum expressions B(r,i), 0<=r<=3,1<=i<=k+1. We select a number p>q and we set c:=b(k)+p^2. For n>c, we have the k+1 representations B(r(n),i)+s(n)*2^2.

Additionally, for n-p^2 (which is >b(k)) there are also k+1 representations B(r_p,i)+s_p*2^2, where r_p:=r(n-p^2), s_p:=s(n-p^2). Thus n can be written B(r(n),i)+s(n)*2^2, 1<=i<=k+1 and B(r_p,i)+s_p*2^2+p^2, 1<=i<=k+1.

By choice of p all these sum representations of n are different, which implies, that there are 2k+2 such representations. It follows a(n)>2k+2>k+1 for all n>c, which implies, that b(k+1) exists.

A more precise formulation of the author's conjecture is "b(k):=min( n | a(j)>k for all j>n) exists for all k>=0". (End)

A033183(n) <= a(n). [From Reinhard Zumkeller, Nov 07 2009]

LINKS

Reinhard Zumkeller and Vaclav Kotesovec, Table of n, a(n) for n = 1..10000 (terms 1..500 from Reinhard Zumkeller)

Eric Weisstein's World of Mathematics, Square Number.

Index entries for sequences related to sums of squares

FORMULA

a(n) = 1/n*Sum_{k=1..n} (A035316(k)-1)*a(n-k), a(0) = 1. - Vladeta Jovovic, Nov 20 2002

G.f. g(x)=product{k>1, 1/(1-x^(k^2))}-1 = 1/((1-x^4)*(1-x^9)*(1-x^16)*(1-x^25)*(1-x^36)*...)-1. - Hieronymus Fischer, Nov 19 2007

a(n) ~ exp(3*Pi^(1/3) * Zeta(3/2)^(2/3) * n^(1/3) / 2^(4/3)) * Zeta(3/2)^(4/3) / (2^(11/3) * sqrt(3) * Pi^(5/6) * n^(11/6)). - Vaclav Kotesovec, Jan 05 2017

EXAMPLE

a(42)=3: 2*3^2+6*2^2 = 4^2+2*3^2+2*2^2 = 5^2+3^2+2*2^2.

MATHEMATICA

Join[{1}, Table[Length[PowersRepresentations[n, n, 2]], {n, 1, 90}]] // Differences

(* or *)

m = 91; CoefficientList[Product[1/(1 - x^(k^2)), {k, 1, m}] + O[x]^m, x] // Differences (* Jean-Fran├žois Alcover, Mar 01 2019 *)

PROG

(Haskell)

a078134 = p $ drop 2 a000290_list where

   p _          0 = 1

   p ks'@(k:ks) x = if x < k then 0 else p ks' (x - k) + p ks x

-- Reinhard Zumkeller, May 04 2013

CROSSREFS

Cf. A000290, A001156, A078138, A078139, A078128.

See A134754 for the sequence representing b(k).

Cf. A090677, A078137, A134754, A134755.

Sequence in context: A097516 A219052 A060826 * A282380 A083661 A029369

Adjacent sequences:  A078131 A078132 A078133 * A078135 A078136 A078137

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Nov 19 2002

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 22:45 EDT 2020. Contains 334756 sequences. (Running on oeis4.)