A073092 - OEIS

%I #20 Sep 09 2022 02:37:18

%S 1,2,3,3,4,5,5,5,6,7,8,8,8,9,9,9,10,11,12,12,13,13,13,13,13,15,16,16,

%T 16,17,17,17,18,18,19,19,20,21,21,21,22,23,23,23,23,24,24,24,24,25,27,

%U 27,28,29,29,29,29,29,30,30,30,31,31,31,32,34,34,34,35,35,35,35,36,37,38

%N Number of numbers of the form x^2 + y^2 (0 <= x <= y) less than or equal to n.

%H Amiram Eldar, <a href="/A073092/b073092.txt">Table of n, a(n) for n = 0..10000</a>

%F a(n) = Sum_{k=0..n} A000161(k).

%F a(n) is asymptotic to Pi*n/8.

%e 0^2 + 0^2, 0^2 + 1^2, 1^2 + 1^2 are less than or equal to 2 hence a(2) = 3.

%t Accumulate @ Table[Length @ PowersRepresentations[n, 2, 2], {n, 0, 100}] (* _Amiram Eldar_, Mar 08 2020 *)

%o (PARI) a(n)=sum(x=0,n,sum(y=0,x,if((sign(x^2+y^2-n)+1)*sign(x^2+y^2-n),0,1)))

%o (Python)

%o from itertools import count, islice

%o from math import prod

%o from sympy import factorint

%o def A073092_gen(): # generator of terms

%o     yield (c:=1)

%o     for n in count(1):

%o         f = factorint(n)

%o         c += int(not any(e&1 for e in f.values())) + (((m:=prod(1 if p==2 else (e+1 if p&3==1 else (e+1)&1) for p, e in f.items()))+((((~n & n-1).bit_length()&1)<<1)-1 if m&1 else 0))>>1)

%o         yield c

%o A073092_list = list(islice(A073092_gen(),30)) # _Chai Wah Wu_, Sep 08 2022

%Y Cf. A000161, A001481.

%Y Cf. A057655.

%K easy,nonn

%O 0,2

%A _Benoit Cloitre_, Aug 18 2002