A338921 a(0)=1, a(n) for n >= 1 is the number of distinct sums of two elements in [a(0), ..., a(n-1)], chosen without replacement.

1, 0, 1, 2, 3, 5, 8, 12, 17, 22, 28, 35, 43, 52, 60, 69, 77, 86, 92, 103, 112, 123, 137, 151, 168, 180, 194, 204, 224, 245, 261, 280, 301, 318, 335, 352, 369, 387, 413, 433, 459, 482, 507, 528, 552, 586, 614, 638, 669, 701, 733, 761, 791, 824, 855, 885, 917, 952, 985, 1020

Offset

0,4

Comments

a(n) <= A000217(n)-n for n >= 1.

Without replacement means a(i)+a(i) is not included. However, if a(i)=a(j), a(i)+a(j) still counts because they have two different indices. If you include a(i)+a(i), the sequence becomes A000012 (all ones).

If you include the distinct sums between 3 elements and more, you arrive at the sequence 1, 0, followed by A000079 (2^n).

Same rule as in A247184, but with a(0)=1.

Links

Table of n, a(n) for n=0..59.

Example

a(1) gives the number of distinct sums between two elements of [1]. There aren't two elements so a(1)=0.
a(2) gives the number of distinct sums between two elements of [1,0]. The only sum are 1+0, so a(2) = 1.
a(3) gives the number of distinct sums between two elements of [1,0,1]. The two sums are 1+0 and 1+1 so a(3)=2.

Maple

s:= proc(n) option remember; `if`(n=0, {},
      {s(n-1)[], seq(a(i)+a(n), i=0..n-1)})
    end:
a:= proc(n) option remember;
      `if`(n=0, 1, nops(s(n-1)))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Nov 16 2020

Mathematica

a[0] = 1; a[1] = 0;
a[n_Integer?Positive] := a[n] = Length[Union[Total[Subsets[Array[a, n, 0], {2}], {2}]]];
Array[a, 61, 0] (* Jan Mangaldan, Nov 23 2020 *)

Prog

(PARI) my(v=[1], w=[], n=1); while(n<75, for(i=2, #v, w=concat(w, v[i-1]+v[#v])); w=vecsort(w, , 8); v=concat(v, #w); n++); v

Crossrefs

Cf. A000217, A000012, A247184, A247185.

Sequence in context: A028955 A246321 A104664 * A333343 A022856 A089071

Adjacent sequences: A338918 A338919 A338920 * A338922 A338923 A338924

Keyword

nonn

Author

Derek Orr, Nov 15 2020

Status

approved