A072207 a(0) = 1; for n>0, a(n) = number of distinct sums of subsets of {1, 1/2, 1/3, 1/4, ..., 1/n} (allowing the empty subset).

1, 2, 4, 8, 16, 32, 52, 104, 208, 416, 832, 1664, 1856, 3712, 7424, 9664, 19328, 38656, 59264, 118528, 126976, 224128, 448256, 896512, 936832, 1873664, 3747328, 7494656, 7771136, 15542272, 15886336, 31772672, 63545344, 112064512, 224129024, 231010304, 237031424, 474062848, 948125696

Offset

0,2

Comments

Define L to be a set of rational numbers with L={0}, s=1 in generation 0 and the rule "replace each term t in L with terms t-1/s, t+1/s, then increment s" to generate the next generation. a(n) is the size of the set in generation n. First generation = {-1,1}, second generation = {-3/2,-1/2,1/2,3/2}, 3rd generation = {-11/6,-7/6,-5/6,-1/6,1/6,5/6,7/6,11/6}. - Dylan Hamilton, Oct 28 2010

If n is a prime power, a(n) = 2*a(n-1). However, this is not "if and only if", e.g., a(10) = 2*a(9). - Robert Israel, Nov 23 2016

Links

Bert Dobbelaere, Table of n, a(n) for n = 0..83

M. N. Bleicher and P. Erdős, The number of distinct subsums of sum 1..N 1/i, Math. Comp. 29 (1975), 29-42, Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday, see Front matter.

Bert Dobbelaere, Python program

Formula

a(p) = 2 * a(p-1) for p prime. a(2*p) = 2 * a(2*p-1) for p>3 prime. - Giovanni Resta, Jul 18 2019

Maple

S[1]:= {0, 1}: A[1]:= 2:
for n from 2 to 30 do
  S[n]:= S[n-1] union (1/n +~ S[n-1]);
  A[n]:= nops(S[n]);
od:
seq(A[i], i=1..30); # Robert Israel, Nov 23 2016

Mathematica

w = {0}; o = {1}; s = 1
Do[w = Union[Flatten[{w - (1/s), w + (1/s)}]]; AppendTo[o, Length[w]]; ++s, {NumberOfApplications}]; o # Dylan Hamilton, Oct 28 2010

Prog

(PARI) M72207=List([[0]]); A072207(n)={for(k=#M72207, n, listput(M72207, setunion(Set([x+1/k|x<-M72207[k]]), M72207[k]))); #M72207[n+1]} \\ M. F. Hasler, Oct 29 2022

Crossrefs

Cf. A175952.

Sequence in context: A306314 A007055 A175951 * A176718 A033860 A231388

Adjacent sequences: A072204 A072205 A072206 * A072208 A072209 A072210

Keyword

nonn

Author

John W. Layman, Jul 03 2002

Extensions

More terms from Vladeta Jovovic, Jul 05 2002

Terms through a(32) from Sean A. Irvine, Nov 29 2010

Merged A175951 with this entry at the suggestion of Robert Israel. - N. J. A. Sloane, Nov 24 2016

Offset set to 0 and a(33)-a(38) from Giovanni Resta, Jul 20 2019

Status

approved