login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047800 Number of different values of i^2 + j^2 for i,j in [0, n]. 12

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)