

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((nm)/4)+(nm) 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 np^2 (which is >b(k)) there are also k+1 representations B(r_p,i)+s_p*2^2, where r_p:=r(np^2), s_p:=s(np^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(nk), a(0) = 1.  Vladeta Jovovic, Nov 20 2002
G.f. g(x)=product{k>1, 1/(1x^(k^2))}1 = 1/((1x^4)*(1x^9)*(1x^16)*(1x^25)*(1x^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 (* JeanFranç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



