|
%I #181 Apr 06 2024 15:09:18
%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 k is in this sequence, then so are all odd powers of k. - _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 k = x^2 + y^2 with x != y, then k^2 = (x^2-y^2)^2 + (2xy)^2 and k^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 Étienne 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 k = 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 k is a term iff 1) b_j == 0 (mod 2) for j=1..s and 2) r > 0 or t == 1 (mod 2) (or both).
%F From _Charles R Greathouse IV_, Nov 18 2022: (Start)
%F a(n) ~ k*n*sqrt(log n), where k = 1.3085... = 1/A064533.
%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. (End)
%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,changed
%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
|
