login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000404 Numbers that are the sum of 2 nonzero squares. 168

%I

%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 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, 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).

%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 *)

%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

%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, A004431, A007692.

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

%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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 00:25 EST 2019. Contains 329083 sequences. (Running on oeis4.)