A077773 - OEIS

%I #56 Jul 30 2023 08:10:30

%S 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,

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

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

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

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

%C 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

%C 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

%H Hugo Pfoertner, <a href="/A077773/b077773.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1024 from T. D. Noe and Antti Karttunen).

%H Hugo Pfoertner, <a href="http://www.randomwalk.de/sequences/a077773.txt">Table of n, a(n) for n = 0..500000</a>

%H Rainer Rosenthal, <a href="/A077773/a077773.png">Illustrating A077773</a>

%F a(n) = Sum_{i=n^2+1..(n+1)^2-1} A229062(i). - _Ralf Stephan_, Sep 17 2013

%F From _Antti Karttunen_, Oct 04 2016: (Start)

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

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

%e 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.

%t 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

%o (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 */

%o (Scheme)

%o (define (A077773 n) (add (lambda (i) (* (- 1 (A010052 i)) (A229062 i))) (A000290 n) (+ -1 (A000290 (+ 1 n)))))

%o ;; Implements sum_{i=lowlim..uplim} intfun(i)

%o (define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))

%o ;; _Antti Karttunen_, Oct 04 2016

%o (Python)

%o from sympy import factorint

%o 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

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

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

%K nonn

%O 0,3

%A _T. D. Noe_, Nov 20 2002

%E Term a(0)=0 prepended by _Antti Karttunen_, Oct 04 2016