OFFSET
1,1
COMMENTS
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
Also numbers whose cubes are the sum of two nonzero squares. - Joe Namnath and Lawrence Sze
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
The primes in this sequence are sequence A002313.
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
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]
Number of terms less than 10^k, k=1,2,3,...: 3, 34, 308, 2690, 23873, 215907, 1984228, ... - Muniru A Asiru, Feb 01 2018
REFERENCES
David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989.
GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 103.
E. Grosswald, Representations of Integers as Sums of Squares. Springer-Verlag, NY, 1985, p. 75, Theorem 4, with Theorem 2, p. 15.
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.
Ian Stewart, "Game, Set and Math", Chapter 8, 'Close Encounters of the Fermat Kind', Penguin Books, Ed. 1991, pp. 107-124.
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
J. M. De Koninck and V. Ouellet, On the n-th element of a set of positive integers, Annales Univ. Sci. Budapest Sect. Comput. 44 (2015), 153-164. See 2. on p. 162.
Étienne Fouvry, Claude Levesque, and Michel Waldschmidt, Representation of integers by cyclotomic binary forms, arXiv:1712.09019 [math.NT], 2017.
Joshua Harrington, Lenny Jones, and Alicia Lamarche, Representing integers as the sum of two squares in the ring Z_n, arXiv:1404.0187 [math.NT], 2014.
David Rabahy, Google Sheets
G. Xiao, Two squares.
Reinhard Zumkeller, Illustration for A084888 and A000404.
FORMULA
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).
From Charles R Greathouse IV, Nov 18 2022: (Start)
a(n) ~ k*n*sqrt(log n), where k = 1.3085... = 1/A064533.
EXAMPLE
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.
MAPLE
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
MATHEMATICA
nMax=1000; n2=Floor[Sqrt[nMax-1]]; Union[Flatten[Table[a^2+b^2, {a, n2}, {b, a, Floor[Sqrt[nMax-a^2]]}]]]
Select[Range@ 200, Length[PowersRepresentations[#, 2, 2] /. {0, _} -> Nothing] > 0 &] (* Michael De Vlieger, Mar 24 2016 *)
Module[{upto=200}, Select[Union[Total/@Tuples[Range[Sqrt[upto]]^2, 2]], #<= upto&]] (* Harvey P. Dale, Sep 18 2021 *)
PROG
(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
(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
(Haskell)
import Data.List (findIndices)
a000404 n = a000404_list !! (n-1)
a000404_list = findIndices (> 0) a025426_list
-- Reinhard Zumkeller, Aug 16 2011
(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
(GAP) P:=List([1..10^4], i->i^2);;
A000404 := Set(Flat(List(P, i->List(P, j -> i+j)))); # Muniru A Asiru, Feb 01 2018
(Python)
from itertools import count, islice
from sympy import factorint
def A000404_gen(startvalue=1): # generator of terms >= startvalue
for n in count(max(startvalue, 1)):
c = False
for p in (f:=factorint(n)):
if (q:= p & 3)==3 and f[p]&1:
break
elif q == 1:
c = True
else:
if c or f.get(2, 0)&1:
yield n
CROSSREFS
A001481 gives another version (allowing for zero squares).
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.
Column k=2 of A336725.
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Edited by Ralf Stephan, Nov 15 2004
Typo in formula corrected by M. F. Hasler, Feb 07 2009
Erroneous Mathematica program fixed by T. D. Noe, Aug 07 2009
PARI code fixed for versions > 2.5 by M. F. Hasler, Jan 01 2013
STATUS
approved