A160663 Number of distinct sums that one can obtain by adding two squares among the n first ones.

2, 5, 9, 14, 19, 26, 33, 41, 50, 60, 70, 82, 93, 105, 119, 134, 147, 164, 179, 197, 215, 234, 251, 272, 293, 314, 336, 359, 381, 407, 430, 456, 483, 507, 535, 566, 594, 623, 652, 686, 714, 748, 780, 812, 849, 883, 918, 956, 992, 1030, 1068, 1107, 1141, 1181

Offset: 1

Author

Romain CARRE (romain.carre.2008(AT)enseirb.fr), May 22 2009

Keywords

• nonn

Comments

Essentially the same as A047800: a(n) = A047800(n) - 1.

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.

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

An upper bound is a(n) <= A102548(2n^2) << n^2/log n. - Charles R Greathouse IV, Jan 16 2023

Examples

			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.
		

References

• Melvyn B. Nathanson (1996). "Additive Number Theory: the Classical Bases" Graduate Texts in Mathematics. 164. Springer-Verlag. p. 192. ISBN 0-387-94656-X.

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from Alois P. Heinz)
• L. G. Schnirelmann, Über additive Eigenschaften von Zahlen, Math. Ann. 107 (1933) 649-690.
• L. G. Schnirelmann, Über additive Eigenschaften von Zahlen, Math. Ann. 107 (1933) 649-690. doi:10.1007/BF01448914.
• Samuel S. Wagstaff, Jr., The Schnirelmann density of the sums of three squares, Proc. Amer. Math. Soc. 52 (1975), 1-7.
• Wikipedia, Additive number theory
• Wikipedia, Schnirelmann density
• Wikipedia, Edmund Landau

Programs

Maple

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

Mathematica

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 *)

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

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

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

Python

def a(n):
    SUM, SQR = set(), set(x**2 for x in range(1, n + 1))
    for i in SQR:
        SUM.add(i)
        for j in SQR: SUM.add(i + j)
    return len(SUM)
# Romain CARRE (romain.carre.2008(AT)enseirb.fr), Apr 16 2010

Formula

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}.

Trivially 2n <= a(n) <= n(n+1)/2. - Charles R Greathouse IV, Oct 30 2015

a(n) << n^2/sqrt(log n) [see A000404]. - Charles R Greathouse IV, Oct 30 2015

Extensions

More terms from Alois P. Heinz, Jun 16 2009