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

Author

John W. Layman, Jul 03 2002

Keywords

• nonn

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

Crossrefs

Cf. A175952.

Programs

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; NumberOfApplications = 20;
Do[w = Union[Flatten[{w - (1/s), w + (1/s)}]]; AppendTo[o, Length[w]]; ++s,{NumberOfApplications}];o (* Dylan Hamilton, Oct 28 2010 *)

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

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

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