|
%I #43 Jan 16 2023 20:59:26
%S 2,5,9,14,19,26,33,41,50,60,70,82,93,105,119,134,147,164,179,197,215,
%T 234,251,272,293,314,336,359,381,407,430,456,483,507,535,566,594,623,
%U 652,686,714,748,780,812,849,883,918,956,992,1030,1068,1107,1141,1181
%N Number of distinct sums that one can obtain by adding two squares among the n first ones.
%C Essentially the same as A047800: a(n) = A047800(n) - 1.
%C Let A be the set of the n first squares (1,4,9,...,n^2). Let A+A be the corresponding sumset (= {a,b,a+b where (a,b) in A^2}). That very sequence describes the number of elements of A+A, relatively to n.
%C a(n-1) is the number of distinct positive 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 An upper bound is a(n) <= A102548(2n^2) << n^2/log n. - _Charles R Greathouse IV_, Jan 16 2023
%D Melvyn B. Nathanson (1996). "Additive Number Theory: the Classical Bases" Graduate Texts in Mathematics. 164. Springer-Verlag. p. 192. ISBN 0-387-94656-X.
%H Charles R Greathouse IV, <a href="/A160663/b160663.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Alois P. Heinz)
%H L. G. Schnirelmann, <a href="https://eudml.org/doc/159613">Über additive Eigenschaften von Zahlen</a>, Math. Ann. 107 (1933) 649-690.
%H L. G. Schnirelmann, <a href="https://doi.org/10.1007/BF01448914">Über additive Eigenschaften von Zahlen</a>, Math. Ann. 107 (1933) 649-690. doi:10.1007/BF01448914.
%H Samuel S. Wagstaff, Jr., <a href="https://doi.org/10.1090/S0002-9939-1975-0379425-4">The Schnirelmann density of the sums of three squares</a>, Proc. Amer. Math. Soc. 52 (1975), 1-7.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Additive_number_theory">Additive number theory</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Schnirelmann_density">Schnirelmann density</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Edmund_Landau">Edmund Landau</a>
%F a(n) = card(A+A) where A={k^2} k=1..n and A+A = {a,b,a+b where (a,b) in A^2}.
%F Trivially 2n <= a(n) <= n(n+1)/2. - _Charles R Greathouse IV_, Oct 30 2015
%F a(n) << n^2/sqrt(log n) [see A000404]. - _Charles R Greathouse IV_, Oct 30 2015
%e For n = 3, A = {1,4,9}, A+A = {1,4,9} U {2,5,10,8,13,18} thus A+A = {1,2,4,5,8,9,10,13,18}, and hence card(A+A) = 9; a(3) = 9.
%p a:= proc(n) local A, i, j; A:= [i^2$i=1..n]; nops([{A[], seq (seq (A[i]+A[j], j=1..i), i=1..nops(A))}[]]) end: seq (a(n), n=1..60); # _Alois P. Heinz_, Jun 16 2009
%t a[n_] := (Table[i^2 + j^2, {i, 0, n}, {j, i, n}] // Flatten // Union // Length) - 1; Array[a, 60] (* _Jean-François Alcover_, May 25 2018 *)
%o (Python)
%o def a(n):
%o SUM, SQR = set(), set(x**2 for x in range(1, n + 1))
%o for i in SQR:
%o SUM.add(i)
%o for j in SQR: SUM.add(i + j)
%o return len(SUM)
%o # Romain CARRE (romain.carre.2008(AT)enseirb.fr), Apr 16 2010
%o (PARI) a(n)=n++; #vecsort(vector(n^2,i,((i-1)\n)^2+((i-1)%n)^2),,8)-1 \\ _Charles R Greathouse IV_, Jun 13 2013
%o (PARI) a(n)=my(u=vector(n,i,i^2),v=List(u)); for(i=1,n, for(j=1,i, listput(v,u[i]+u[j]))); u=0; #Set(v) \\ _Charles R Greathouse IV_, Nov 18 2022
%o (PARI) first(n)=my(v=vector(n),u=[]); for(k=1,n, my(k2=k^2,w=vector(k,i,i^2+k2)); w=setunion(w,[k2]); u=setunion(u,w); v[k]=#u); v \\ _Charles R Greathouse IV_, Nov 18 2022
%K nonn
%O 1,1
%A Romain CARRE (romain.carre.2008(AT)enseirb.fr), May 22 2009
%E More terms from _Alois P. Heinz_, Jun 16 2009
|
