

A001481


Numbers that are the sum of 2 squares.
(Formerly M0968 N0361)


171



0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100, 101, 104, 106, 109, 113, 116, 117, 121, 122, 125, 128, 130, 136, 137, 144, 145, 146, 148, 149, 153, 157, 160
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Numbers n such that n = x^2 + y^2 has a solution in nonnegative integers x, y.
Closed under multiplication.  David W. Wilson, Dec 20 2004
Also, numbers whose cubes are the sum of 2 squares.  Artur Jasinski, Nov 21 2006 (Cf. A125110.)
Terms are the squares of smallest radii of circles covering (on a square grid) a number of points equal to the terms of A057961.  Philippe Lallouet (philip.lallouet(AT)wanadoo.fr), Apr 16 2007. [Comment corrected by T. D. Noe, Mar 28 2008]
Numbers with more 4k+1 divisors than 4k+3 divisors. If a(n) is a member of this sequence, then so too is any power of a(n).  Ant King, Oct 05 2010
A000161(a(n)) > 0; A070176(a(n)) = 0.  Reinhard Zumkeller, Feb 04 2012, Aug 16 2011
Numbers that are the norms of Gaussian integers. This sequence has unique factorization; the primitive elements are A055025.  Franklin T. AdamsWatters, Nov 25 2011
These are numbers n such that all of n's odd prime factors congruent to 3 modulo 4 occur to an even exponent (Fermat's twosquares theorem).  JeanChristophe Hervé, May 01 2013
Let's say that an integer n divides a lattice if there exists a sublattice of index n. Example: 2, 4, 5 divide the square lattice. The present sequence without 0 is the sequence of divisors of the square lattice. Say that n is a "prime divisor" if the indexn sublattice is not contained in any other sublattice except the original lattice itself. Then A055025 (norms of Gaussian primes) gives the "prime divisors" of the square lattice.  JeanChristophe Hervé, May 01 2013
For any i,j > 0 a(i)*a(j) is a member of this sequence, since (a^2 + b^2)*(c^2 + d^2) = (a*c + b*d)^2 + (a*d  b*c)^2.  Boris Putievskiy, May 05 2013
The sequence is closed under multiplication. Primitive elements are in A055025. The sequence can be split into 3 multiplicatively closed subsequences: {0}, A004431 and A125853.  JeanChristophe Hervé, Nov 17 2013
Generalizing Jasinski's comment, same as numbers whose odd powers are the sum of 2 squares, by Fermat's twosquares theorem.  Jonathan Sondow, Jan 24 2014
By the 4 squares theorem, every nonnegative integer can be expressed as the sum of two elements of this sequence.  Franklin T. AdamsWatters, Mar 28 2015
There are never more than 3 consecutive terms. Runs of 3 terms start at 0, 8, 16, 72, ... (A082982).  Ivan Neretin, Nov 09 2015
Any composite term of this sequence has at least one prime factor that is also in this sequence. This follows from Wilson's comment of 2004 and AdamsWatters's comment of 2011.  Alonso del Arte, Aug 12 2016


REFERENCES

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", SpringerVerlag, p. 106.
David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989.
L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 417.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 98104.
G. H. Hardy, Ramanujan, pp. 6063.
P. Moree and J. Cazaran, On a claim of Ramanujan in his first letter to Hardy, Expos. Math. 17 (1999), pp. 289312.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. van Wijngaarden, A table of partitions into two squares with an application to rational triangles, Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, Series A, 53 (1950), 869875.


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000
Michael Baake, Uwe Grimm, Dieter Joseph and Przemyslaw Repetowicz, Averaged shelling for quasicrystals, arXiv:math/9907156 [math.MG], 1999.
H. Bottomley, Illustration of initial terms
Richard T. Bumby, Sums of four squares, in Number theory (New York, 19911995), 18, Springer, New York, 1996.
John Butcher, Quadratic residues and sums of two squares
John Butcher, Sums of two squares revisited
Leonhard Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
Steven R. Finch, LandauRamanujan Constant [broken link]
Steven R. Finch, LandauRamanujan Constant [From the Wayback Machine]
Steven R. Finch, On a Generalized FermatWiles Equation [broken link]
Steven R. Finch, On a Generalized FermatWiles Equation [From the Wayback Machine]
J. W. L. Glaisher, On the function which denotes the difference between the number of (4m+1)divisors and the number of (4m+3)divisors of a number, Proc. London Math. Soc., 15 (1884), 104122. [Annotated scanned copy of pages 104107 only]
Darij Grinberg, UMN Spring 2019 Math 4281 notes, University of Minnesota, College of Science & Engineering, 2019.
Thomas Nickson, Igor Potapov, Broadcasting Automata and Patterns on Z^2, arXiv preprint arXiv:1410.0573 [cs.FL], 2014.
Peter Shiu, Counting Sums of Two Squares: The MeisselLehmer Method, Mathematics of Computation 47 (1986), 351360.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
William A. Stein, Quadratic Forms:Sums of Two Squares
Eric Weisstein's World of Mathematics, Square Number
Eric Weisstein's World of Mathematics, Generalized Fermat Equation
Eric Weisstein's World of Mathematics, LandauRamanujan Constant
Eric Weisstein's World of Mathematics, Gaussian Integer
Gang Xiao, Two squares
Index entries for sequences related to sums of squares
Index entries for "core" sequences


FORMULA

n = square * 2^{0 or 1} * {product of distinct primes == 1 (mod 4)}.
The number of integers less than N that are sums of two squares is asymptotic to constant*N/sqrt(log(N)), hence lim n > inf a(n)/n = infinity.
Nonzero terms in expansion of Dirichlet series Product_p (1  (Kronecker(m, p) + 1)*p^(s) + Kronecker(m, p)*p^(2s))^(1) for m = 1.
a(n) ~ k*n*sqrt(log n), where k = 1.3085... = 1/A064533.  Charles R Greathouse IV, Apr 16 2012


MAPLE

readlib(issqr): for n from 0 to 160 do for k from 0 to floor(sqrt(n)) do if issqr(nk^2) then printf(`%d, `, n); break fi: od: od:


MATHEMATICA

upTo = 160; With[{max = Ceiling[Sqrt[upTo]]}, Select[Union[Total /@ (Tuples[Range[0, max], {2}]^2)], # <= upTo &]] (* Harvey P. Dale, Apr 22 2011 *)
Select[Range[0, 160], SquaresR[2, #] != 0 &] (* JeanFrançois Alcover, Jan 04 2013 *)


PROG

(PARI) isA001481(n)=local(x, r); x=0; r=0; while(x<=sqrt(n) && r==0, if(issquare(nx^2), r=1); x++); r \\ Michael B. Porter, Oct 31 2009
(PARI) is(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]%2 && f[i, 1]%4==3, return(0))); 1 \\ Charles R Greathouse IV, Aug 24 2012
(PARI) B=bnfinit('z^2+1, 1);
is(n)=#bnfisintnorm(B, n) \\ Ralf Stephan, Oct 18 2013, edited by M. F. Hasler, Nov 21 2017
(PARI) list(lim)=my(v=List(), t); for(m=0, sqrtint(lim\=1), t=m^2; for(n=0, min(sqrtint(limt), m), listput(v, t+n^2))); Set(v) \\ Charles R Greathouse IV, Jan 05 2016
(PARI) is_A001481(n)=!for(i=2bittest(n, 0), #n=factor(n)~, bittest(n[1, i], 1)&&bittest(n[2, i], 0)&&return) \\ M. F. Hasler, Nov 20 2017
(Haskell)
a001481 n = a001481_list !! (n1)
a001481_list = [x  x < [0..], a000161 x > 0]
 Reinhard Zumkeller, Feb 14 2012, Aug 16 2011
(MAGMA) [n: n in [0..160]  NormEquation(1, n) eq true]; // Arkadiusz Wesolowski, May 11 2016


CROSSREFS

Union of A000290 and A000404. Complement of A022544.
Cf. A004018, A000161, A002654, A064533, A055025, A002828, A000378, A025284A025320, A125110, A118882, A125022.
A000404 gives another version. Subsequence of A091072 and of A046711.
Cf. A057961, A232499.
Sequence in context: A121996 A269176 A091072 * A248151 A245226 A034026
Adjacent sequences: A001478 A001479 A001480 * A001482 A001483 A001484


KEYWORD

nonn,nice,easy,core


AUTHOR

N. J. A. Sloane


STATUS

approved



