The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000404 Numbers that are the sum of 2 nonzero squares. 233

%I #176 Apr 22 2023 13:50:33

%S 2,5,8,10,13,17,18,20,25,26,29,32,34,37,40,41,45,50,52,53,58,61,65,68,

%T 72,73,74,80,82,85,89,90,97,98,100,101,104,106,109,113,116,117,122,

%U 125,128,130,136,137,145,146,148,149,153,157,160,162,164,169,170,173,178

%N Numbers that are the sum of 2 nonzero squares.

%C From the formula it is easy to see that if n is in this sequence, then so are all odd powers of n. - _T. D. Noe_, Jan 13 2009

%C Also numbers whose cubes are the sum of two nonzero squares. - Joe Namnath and Lawrence Sze

%C A line perpendicular to y=mx has its first integral y-intercept at a^2+b^2. The remaining ones for that slope are multiples of that primitive value. - _Larry J Zimmermann_, Aug 19 2010

%C The primes in this sequence are sequence A002313.

%C Complement of A018825; A025426(a(n)) > 0; A063725(a(n)) > 0. - _Reinhard Zumkeller_, Aug 16 2011

%C If the two squares are not equal, then any power is still in the sequence: if n = x^2 + y^2 with x != y, then n^2 = (x^2-y^2)^2 + (2xy)^2 and n^3 = (x(x^2-3y^2))^2 + (y(3x^2-y^2))^2, etc. - _Carmine Suriano_, Jul 13 2012

%C There are never more than 3 consecutive terms that differ by 1. Triples of consecutive terms that differ by 1 occur infinitely many times, for example 2(k^2 + k)^2, (k^2 - 1)^2 + (k^2 + 2 k)^2, and (k^2 + k - 1)^2 + (k^2 + k + 1)^2 for any integer k>1. - _Ivan Neretin_, Mar 16 2017 [Corrected by _Jerzy R Borysowicz_, Apr 14 2017]

%C Number of terms less than 10^k, k=1,2,3,...: 3, 34, 308, 2690, 23873, 215907, 1984228, ... - _Muniru A Asiru_, Feb 01 2018

%D David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989.

%D GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 103.

%D E. Grosswald, Representations of Integers as Sums of Squares. Springer-Verlag, NY, 1985, p. 75, Theorem 4, with Theorem 2, p. 15.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, p. 219, th. 251, 252.

%D Ian Stewart, "Game, Set and Math", Chapter 8, 'Close Encounters of the Fermat Kind', Penguin Books, Ed. 1991, pp. 107-124.

%H T. D. Noe, <a href="/A000404/b000404.txt">Table of n, a(n) for n = 1..10000</a>

%H J. M. De Koninck and V. Ouellet, <a href="http://ac.inf.elte.hu/Vol_044_2015/153_44.pdf">On the n-th element of a set of positive integers</a>, Annales Univ. Sci. Budapest Sect. Comput. 44 (2015), 153-164. See 2. on p. 162.

%H Etienne Fouvry, Claude Levesque, and Michel Waldschmidt, <a href="https://arxiv.org/abs/1712.09019">Representation of integers by cyclotomic binary forms</a>, arXiv:1712.09019 [math.NT], 2017.

%H Joshua Harrington, Lenny Jones, and Alicia Lamarche, <a href="http://arxiv.org/abs/1404.0187">Representing integers as the sum of two squares in the ring Z_n</a>, arXiv:1404.0187 [math.NT], 2014.

%H David Rabahy, <a href="https://goo.gl/KM3h81">Google Sheets</a>

%H G. Xiao, <a href="http://wims.unice.fr/~wims/en_tool~number~twosquares.en.html">Two squares</a>

%H Reinhard Zumkeller, <a href="/A084888/a084888.txt">Illustration for A084888 and A000404</a>

%H <a href="/index/Su#ssq">Index entries for sequences related to sums of squares</a>

%F Let n = 2^t * p_1^a_1 * p_2^a_2 *...* p_r^a_r * q_1^b_1 * q_2^b_2 *...* q_s^b_s with t>=0, a_i>=0 for i=1..r, where p_i = 1 mod 4 for i=1..r and q_j =-1 mod 4 for j=1..s. Then n is a member iff 1) b_j=0 mod 2 for j=1..s and 2) r>0 or t=1 mod 2 (or both).

%F a(n) ~ k*n*sqrt(log n), where k = 1.3085... = 1/A064533. - _Charles R Greathouse IV_, Nov 18 2022

%F There are B(x) = x/sqrt(log x) * (K + B2/log x + O(1/log^2 x)) terms of this sequence up to x, where K = A064533 and B2 = A227158. - _Charles R Greathouse IV_, Nov 18 2022

%e 25 = 3^2 + 4^2, therefore 25 is a term. Note that also 25^3 = 15625 = 44^2 + 117^2, therefore 15625 is a term.

%p nMax:=178: A:={}: for i to floor(sqrt(nMax)) do for j to floor(sqrt(nMax)) do if i^2+j^2 <= nMax then A := `union`(A, {i^2+j^2}) else end if end do end do: A; # _Emeric Deutsch_, Jan 02 2017

%t nMax=1000; n2=Floor[Sqrt[nMax-1]]; Union[Flatten[Table[a^2+b^2, {a,n2}, {b,a,Floor[Sqrt[nMax-a^2]]}]]]

%t Select[Range@ 200, Length[PowersRepresentations[#, 2, 2] /. {0, _} -> Nothing] > 0 &] (* _Michael De Vlieger_, Mar 24 2016 *)

%t Module[{upto=200},Select[Union[Total/@Tuples[Range[Sqrt[upto]]^2,2]],#<= upto&]] (* _Harvey P. Dale_, Sep 18 2021 *)

%o (PARI) is_A000404(n)= for( i=1,#n=factor(n)~%4, n[1,i]==3 && n[2,i]%2 && return); n && ( vecmin(n[1,])==1 || (n[1,1]==2 && n[2,1]%2)) \\ _M. F. Hasler_, Feb 07 2009

%o (PARI) list(lim)=my(v=List(),x2); lim\=1; for(x=1,sqrtint(lim-1), x2=x^2; for(y=1,sqrtint(lim-x2), listput(v,x2+y^2))); Set(v) \\ _Charles R Greathouse IV_, Apr 30 2016

%o (Haskell)

%o import Data.List (findIndices)

%o a000404 n = a000404_list !! (n-1)

%o a000404_list = findIndices (> 0) a025426_list

%o -- _Reinhard Zumkeller_, Aug 16 2011

%o (Magma) lst:=[]; for n in [1..178] do f:=Factorization(n); if IsSquare(n) then for m in [1..#f] do d:=f[m]; if d[1] mod 4 eq 1 then Append(~lst, n); break; end if; end for; else t:=0; for m in [1..#f] do d:=f[m]; if d[1] mod 4 eq 3 and d[2] mod 2 eq 1 then t:=1; break; end if; end for; if t eq 0 then Append(~lst, n); end if; end if; end for; lst; // _Arkadiusz Wesolowski_, Feb 16 2017

%o (GAP) P:=List([1..10^4],i->i^2);;

%o A000404 := Set(Flat(List(P, i->List(P, j -> i+j)))); # _Muniru A Asiru_, Feb 01 2018

%o (Python)

%o from itertools import count, islice

%o from sympy import factorint

%o def A000404_gen(startvalue=1): # generator of terms >= startvalue

%o for n in count(max(startvalue,1)):

%o c = False

%o for p in (f:=factorint(n)):

%o if (q:= p & 3)==3 and f[p]&1:

%o break

%o elif q == 1:

%o c = True

%o else:

%o if c or f.get(2,0)&1:

%o yield n

%o A000404_list = list(islice(A000404_gen(),30)) # _Chai Wah Wu_, Jul 01 2022

%Y A001481 gives another version (allowing for zero squares).

%Y Cf. A004431 (2 distinct squares), A063725 (number of representations), A024509 (numbers with multiplicity), A025284, A018825. Also A050803, A050801, A001105, A033431, A084888, A000578, A000290, A057961, A232499, A007692.

%Y Cf. A003325 (analog for cubes), A003336 (analog for 4th powers).

%Y Column k=2 of A336725.

%Y Cf. A355237, A355238.

%K nonn,nice,easy

%O 1,1

%A _N. J. A. Sloane_ and _J. H. Conway_

%E Edited by _Ralf Stephan_, Nov 15 2004

%E Typo in formula corrected by _M. F. Hasler_, Feb 07 2009

%E Erroneous Mathematica program fixed by _T. D. Noe_, Aug 07 2009

%E PARI code fixed for versions > 2.5 by _M. F. Hasler_, Jan 01 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 00:22 EST 2023. Contains 367717 sequences. (Running on oeis4.)