%I #34 Mar 10 2016 04:22:07
%S 1,3,6,10,15,20,27,34,42,51,61,71,83,94,106,120,135,148,165,180,198,
%T 216,235,252,273,294,315,337,360,382,408,431,457,484,508,536,567,595,
%U 624,653,687,715,749,781,813,850,884,919,957,993,1031,1069,1108,1142
%N Number of different values of i^2 + j^2 for i,j in [0, n].
%C 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 Conjecture (after Landau and Erdős): a(n) ~ c * n^2 / sqrt(log(n)), where c = 0.79... . - _Vaclav Kotesovec_, Mar 10 2016
%H 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 Erdős, P., <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 Vaclav Kotesovec, <a href="/A047800/a047800.jpg">Graph - The asymptotic ratio</a>
%H 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.
%t Table[ Length@Union[ Flatten[ Table[ i^2+j^2, {i, 0, n}, {j, 0, n} ] ] ], {n, 0, 49} ]
%t 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 (Haskell)
%o import Data.List (nub)
%o a047800 n = length $ nub [i^2 + j^2 | i <- [0..n], j <- [i..n]]
%o -- _Reinhard Zumkeller_, Oct 03 2012
%o (PARI) a(n)=#vecsort(vector(n^2,i,((i-1)\n)^2+((i-1)%n)^2),,8) \\ _Charles R Greathouse IV_, Jun 13 2013
%Y Cf. A034966, A047801, A160663.
%K nonn,easy,nice
%O 0,2
%A _Wouter Meeussen_
|