A078134 Number of ways to write n as sum of squares > 1.

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

Offset: 1

Author

Reinhard Zumkeller, Nov 19 2002

Keywords

• nonn

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]

Examples

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

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

Crossrefs

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

See A134754 for the sequence representing b(k).

Cf. A090677, A078137, A134754, A134755.

Programs

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

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

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