|
%I #85 Sep 09 2022 02:33:47
%S 1,1,1,0,1,1,0,0,1,1,1,0,0,1,0,0,1,1,1,0,1,0,0,0,0,2,1,0,0,1,0,0,1,0,
%T 1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,1,2,0,1,1,0,0,0,0,1,0,0,1,0,0,1,2,0,0,
%U 1,0,0,0,1,1,1,0,0,0,0,0,1,1,1,0,0,2,0,0,0,1,1,0,0,0,0,0,0,1,1,0,2,1,0,0,1,0,1,0
%N Number of partitions of n into 2 squares.
%C Number of ways of writing n as a sum of 2 (possibly zero) squares when order does not matter.
%C Number of similar sublattices of square lattice with index n.
%C Let Pk = the number of partitions of n into k nonzero squares. Then we have A000161 = P0 + P1 + P2, A002635 = P0 + P1 + P2 + P3 + P4, A010052 = P1, A025426 = P2, A025427 = P3, A025428 = P4. - _Charles R Greathouse IV_, Mar 08 2010, amended by _M. F. Hasler_, Jan 25 2013
%C a(A022544(n))=0; a(A001481(n))>0; a(A125022(n))=1; a(A118882(n))>1. - _Reinhard Zumkeller_, Aug 16 2011
%D J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 339
%H T. D. Noe, <a href="/A000161/b000161.txt">Table of n, a(n) for n = 0..10000</a>
%H B. K. Agarwala and F. C. Auluck, <a href="/A000093/a000093.pdf">Statistical mechanics and partitions into non-integral powers of integers</a>, Proc. Camb. Phil. Soc., 47 (1951), 207-216. [Annotated scanned copy]
%H Henry Bottomley, <a href="/A001481/a001481.gif">Illustration of initial terms</a>
%H R. T. Bumby, <a href="http://www.math.rutgers.edu/~bumby/squares1.pdf">Sums of four squares</a>, in Number theory (New York, 1991-1995), 1-8, Springer, New York, 1996.
%H J. H. Conway, E. M. Rains and N. J. A. Sloane, On the existence of similar sublattices, Canad. J. Math. 51 (1999), 1300-1306 (<a href="http://neilsloane.com/doc/sim.txt">Abstract</a>, <a href="http://neilsloane.com/doc/sim.pdf">pdf</a>, <a href="http://neilsloane.com/doc/sim.ps">ps</a>).
%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H E. Grosswald, <a href="http://dx.doi.org/10.1007/978-1-4613-8566-0_8">Representations of Integers as Sums of Squares</a>, Springer-Verlag, NY, 1985, p. 84.
%H M. D. Hirschhorn, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00159-4">Some formulas for partitions into squares</a>, Discrete Math, 211 (2000), pp. 225-228. [From _Ant King_, Oct 05 2010]
%H <a href="/index/Su#sublatts">Index entries for sequences related to sublattices</a>
%H <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F a(n) = card { { a,b } c N | a^2+b^2 = n }. - _M. F. Hasler_, Nov 23 2007
%F Let f(n)= the number of divisors of n that are congruent to 1 modulo 4 minus the number of its divisors that are congruent to 3 modulo 4, and define delta(n) to be 1 if n is a perfect square and 0 otherwise. Then a(n)=1/2 (f(n)+delta(n)+delta(1/2 n)). - _Ant King_, Oct 05 2010
%e 25 = 3^2+4^2 = 5^2, so a(25) = 2.
%p A000161 := proc(n) local i,j,ans; ans := 0; for i from 0 to n do for j from i to n do if i^2+j^2=n then ans := ans+1 fi od od; RETURN(ans); end; [ seq(A000161(i), i=0..50) ];
%p A000161 := n -> nops( numtheory[sum2sqr](n) ); # _M. F. Hasler_, Nov 23 2007
%t Length[PowersRepresentations[ #,2,2]] &/@Range[0,150] (* _Ant King_, Oct 05 2010 *)
%o (PARI) a(n)=sum(i=0,n,sum(j=0,i,if(i^2+j^2-n,0,1))) \\ for illustrative purpose
%o (PARI) A000161(n)=sum(k=sqrtint((n-1)\2)+1,sqrtint(n),issquare(n-k^2)) \\ _Charles R Greathouse IV_, Mar 21 2014, improves earlier code by _M. F. Hasler_, Nov 23 2007
%o (PARI) A000161(n)=#sum2sqr(n) \\ See A133388 for sum2sqr(). - _M. F. Hasler_, May 13 2018
%o (Haskell)
%o a000161 n =
%o sum $ map (a010052 . (n -)) $ takeWhile (<= n `div` 2) a000290_list
%o a000161_list = map a000161 [0..]
%o -- _Reinhard Zumkeller_, Aug 16 2011
%o (Python)
%o from math import prod
%o from sympy import factorint
%o def A000161(n):
%o f = factorint(n)
%o return int(not any(e&1 for e in f.values())) + (((m:=prod(1 if p==2 else (e+1 if p&3==1 else (e+1)&1) for p, e in f.items()))+((((~n & n-1).bit_length()&1)<<1)-1 if m&1 else 0))>>1) if n else 1 # _Chai Wah Wu_, Sep 08 2022
%Y Cf. A002654, A001481, A025427, A025428, A063725, A025426, A000290.
%Y Cf. A000925, A247367.
%Y Equivalent sequences for other numbers of squares: A010052 (1), A000164 (3), A002635 (4), A000174 (5).
%K nonn,core,easy,nice
%O 0,26
%A _N. J. A. Sloane_
|
