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,1

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

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

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

Example

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.

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

Prog

(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
(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

Crossrefs

Sequence in context: A266899 A112265 A025281 * A024201 A110443 A130029

Adjacent sequences: A160660 A160661 A160662 * A160664 A160665 A160666

Keyword

nonn

Author

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

Extensions

More terms from Alois P. Heinz, Jun 16 2009

Status

approved