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

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, 16, 17, 17, 17, 18, 18, 19, 19, 20, 21, 21, 21, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 27, 27, 28, 29, 29, 29, 29, 29, 30, 30, 30, 31, 31, 31, 32, 34, 34, 34, 35, 35, 35, 35, 36, 37, 38

Offset: 0

Author

Benoit Cloitre, Aug 18 2002

Keywords

• easy
• nonn

Examples

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

Links

• Amiram Eldar, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A000161, A001481.

Cf. A057655.

Programs

Mathematica

Accumulate @ Table[Length @ PowersRepresentations[n, 2, 2], {n, 0, 100}] (* Amiram Eldar, Mar 08 2020 *)

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

Python

from itertools import count, islice
from math import prod
from sympy import factorint
def A073092_gen(): # generator of terms
    yield (c:=1)
    for n in count(1):
        f = factorint(n)
        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)
        yield c
A073092_list = list(islice(A073092_gen(),30)) # Chai Wah Wu, Sep 08 2022

Formula

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

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