cp's OEIS Frontend

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

%I A078134 #24 Feb 16 2025 08:32:48
%S A078134 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,
%T A078134 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,
%U A078134 9,15,15,16,9,18,18,18,13,19,23,18,17,21,28,22,19,26,30,28,19,31,34,34
%N A078134 Number of ways to write n as sum of squares > 1.
%C A078134 a(A078135(n))=0; a(A078136(n))=1; a(A078137(n))>0;
%C A078134 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_.
%C A078134 Also first difference of A001156 (number of partitions of n into squares). - _Wouter Meeussen_, Oct 22 2005
%C A078134 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).
%C A078134 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).
%C A078134 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.
%C A078134 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.
%C A078134 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.
%C A078134 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.
%C A078134 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)
%C A078134 A033183(n) <= a(n). [From _Reinhard Zumkeller_, Nov 07 2009]
%H A078134 Reinhard Zumkeller and Vaclav Kotesovec, <a href="/A078134/b078134.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..500 from Reinhard Zumkeller)
%H A078134 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquareNumber.html">Square Number</a>.
%H A078134 <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>
%F A078134 a(n) = 1/n*Sum_{k=1..n} (A035316(k)-1)*a(n-k), a(0) = 1. - _Vladeta Jovovic_, Nov 20 2002
%F A078134 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
%F A078134 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
%e A078134 a(42)=3: 2*3^2+6*2^2 = 4^2+2*3^2+2*2^2 = 5^2+3^2+2*2^2.
%t A078134 Join[{1}, Table[Length[PowersRepresentations[n, n, 2]], {n, 1, 90}]] // Differences
%t A078134 (* or *)
%t A078134 m = 91; CoefficientList[Product[1/(1 - x^(k^2)), {k, 1, m}] + O[x]^m, x] // Differences (* _Jean-François Alcover_, Mar 01 2019 *)
%o A078134 (Haskell)
%o A078134 a078134 = p $ drop 2 a000290_list where
%o A078134    p _          0 = 1
%o A078134    p ks'@(k:ks) x = if x < k then 0 else p ks' (x - k) + p ks x
%o A078134 -- _Reinhard Zumkeller_, May 04 2013
%Y A078134 Cf. A000290, A001156, A078138, A078139, A078128.
%Y A078134 See A134754 for the sequence representing b(k).
%Y A078134 Cf. A090677, A078137, A134754, A134755.
%K A078134 nonn
%O A078134 1,16
%A A078134 _Reinhard Zumkeller_, Nov 19 2002