A077773 Number of integers between n^2 and (n+1)^2 that are the sum of two squares; multiple representations are counted once.

0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 6, 9, 8, 8, 10, 10, 11, 11, 12, 11, 14, 12, 13, 15, 16, 15, 15, 17, 16, 17, 19, 18, 19, 20, 19, 20, 21, 20, 22, 22, 24, 22, 25, 23, 26, 26, 24, 29, 26, 27, 28, 27, 29, 26, 31, 32, 30, 29, 33, 33, 31, 31, 35, 34, 35, 35, 35, 36, 37, 37, 33, 42, 37, 38

Offset

0,3

Comments

Related to the circle problem, cf. A077770. See A077774 for a more restrictive case. A077768 counts the representations multiply.

Number of integers k in range [n^2, ((n+1)^2)-1] for which 2 = the least number of squares that add up to k (A002828). Because of this interpretation a(0)=0 was prepended to the beginning. - Antti Karttunen, Oct 04 2016

This sequence is not surjective, since, for instance, there is no n such that a(n) = 46. This follows from a bound observed by Jon E. Schoenfield, that if a(n) = m then n < ((m+1)^2)/2, and the fact that a(n) != 46 for all n < 1105. - Rainer Rosenthal, Jul 25 2023

Links

Hugo Pfoertner, Table of n, a(n) for n = 0..10000 (terms 0..1024 from T. D. Noe and Antti Karttunen).

Hugo Pfoertner, Table of n, a(n) for n = 0..500000

Rainer Rosenthal, Illustrating A077773

Formula

a(n) = Sum_{i=n^2+1..(n+1)^2-1} A229062(i). - Ralf Stephan, Sep 17 2013

From Antti Karttunen, Oct 04 2016: (Start)

For n >= 0, a(n) + A277193(n) + A277194(n) = 2n.

For n >= 1, A277192(n) = a(n) + A277194(n). (End)

Example

a(8)=6 because 65=64+1=49+16, 68=64+4, 72=36+36, 73=64+9, 74=49+25 and 80=64+16 are between squares 64 and 81. Note that 65 is counted only once.

Mathematica

maxN=100; lst={}; For[n=1, n<=maxN, n++, sqrs={}; i=n; j=0; While[i>=j, j=1; While[i^2+j^2<(n+1)^2, If[i>=j&&i^2+j^2>n^2, AppendTo[sqrs, i^2+j^2]]; j++ ]; i--; j-- ]; AppendTo[lst, Length[Union[sqrs]]]]; lst

Prog

(PARI) a(N)=s=0; for(n=N^2+1, (N+1)^2-1, f=0; r=sqrtint(n); forstep(i=r, 1, -1, if(issquare(n-i*i), f=1; s=s+1; break))); s /* Ralf Stephan, Sep 17 2013 */
(Scheme)
(define (A077773 n) (add (lambda (i) (* (- 1 (A010052 i)) (A229062 i))) (A000290 n) (+ -1 (A000290 (+ 1 n)))))
;; Implements sum_{i=lowlim..uplim} intfun(i)
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))
;; Antti Karttunen, Oct 04 2016
(Python)
from sympy import factorint
def A077773(n): return sum(1 for m in range(n**2+1, (n+1)**2) if all(p==2 or p&3==1 or e&1^1 for p, e in factorint(m).items())) # Chai Wah Wu, Jun 20 2023

Crossrefs

Cf. A000290, A002828, A010052, A077768, A077770, A077774, A229062, A277192, A277193, A277194.

Cf. A363762 (terms not occurring in this sequence), A363763.

Sequence in context: A081608 A096532 A335380 * A308754 A339187 A309430

Adjacent sequences: A077770 A077771 A077772 * A077774 A077775 A077776

Keyword

nonn

Author

T. D. Noe, Nov 20 2002

Extensions

Term a(0)=0 prepended by Antti Karttunen, Oct 04 2016

Status

approved