cp's OEIS Frontend

A047800 Number of different values of i^2 + j^2 for i,j in [0, n].

%I A047800 #59 Jul 07 2025 20:20:32
%S A047800 1,3,6,10,15,20,27,34,42,51,61,71,83,94,106,120,135,148,165,180,198,
%T A047800 216,235,252,273,294,315,337,360,382,408,431,457,484,508,536,567,595,
%U A047800 624,653,687,715,749,781,813,850,884,919,957,993,1031,1069,1108,1142
%N A047800 Number of different values of i^2 + j^2 for i,j in [0, n].
%C A047800 a(n-1) is the number of distinct distances on an n X n pegboard. What is its asymptotic growth? Can it be efficiently computed for large n? - _Charles R Greathouse IV_, Jun 13 2013
%C A047800 Conjecture (after Landau and Erdős): a(n) ~ c * n^2 / sqrt(log(n)), where c = 0.79... . - _Vaclav Kotesovec_, Mar 10 2016
%H A047800 T. D. Noe and Vaclav Kotesovec, <a href="/A047800/b047800.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..500 from T. D. Noe)
%H A047800 Paul Erdős, <a href="http://www.renyi.hu/~p_erdos/1946-03.pdf">On sets of distances of n points</a>, American Mathematical Monthly 53, pp. 248-250 (1946).
%H A047800 Vaclav Kotesovec, <a href="/A047800/a047800.jpg">Graph - The asymptotic ratio</a>
%H A047800 Edmund Landau, <a href="https://archive.org/details/handbuchderlehre02landuoft">Handbuch der Lehre von der Verteilung der Primzahlen</a>, vol. 2, Leipzig B. G. Teubner, 1909, p. 643.
%H A047800 Hugo Pfoertner, <a href="/A047800/a047800.png">Plot of asymptotic ratio</a>, 1.44*10^6 terms, logarithmic scale for n, indicating c > 0.8.
%t A047800 Table[ Length@Union[ Flatten[ Table[ i^2+j^2, {i, 0, n}, {j, 0, n} ] ] ], {n, 0, 49} ]
%t A047800 nmax = 100; sq = Table[i^2 + j^2, {i, 0, nmax}, {j, 0, nmax}]; Table[Length@Union[Flatten[Table[Take[sq[[j]], n + 1], {j, 1, n + 1}]]], {n, 0, nmax}] (* _Vaclav Kotesovec_, Mar 09 2016 *)
%o A047800 (Haskell)
%o A047800 import Data.List (nub)
%o A047800 a047800 n = length $ nub [i^2 + j^2 | i <- [0..n], j <- [i..n]]
%o A047800 -- _Reinhard Zumkeller_, Oct 03 2012
%o A047800 (PARI) a(n) = n++; #vecsort(vector(n^2, i, ((i-1)\n)^2+((i-1)%n)^2), , 8) \\ _Charles R Greathouse IV_, Jun 13 2013; edited by _Michel Marcus_, Jul 06 2025
%o A047800 (PARI) a(n) = #setbinop((i,j)->i^2+j^2, [0..n]); \\ _Michel Marcus_, Jul 07 2025
%o A047800 (Python)
%o A047800 def A047800(n): return len(set(i**2+j**2 for i in range(n+1) for j in range(i+1))) # _Chai Wah Wu_, Jul 07 2025
%Y A047800 Cf. A034966, A047801, A160663, A384797.
%K A047800 nonn,easy,nice
%O A047800 0,2
%A A047800 _Wouter Meeussen_