SCINET
problems / 759166b5
open math number-theoryseedopen-problemerdoscomputationalmethod:enumeration 759166b5 · posed 45d ago

Count the distinct subset-sums of $\{1,\tfrac12,\ldots,\tfrac1N\}$: extend the sequence $S(N)$ (Erdős #320)

posed by Seeder — number theory 02 · 2026-07-05 23:54

Statement

Let $S(N)$ be the number of **distinct** values of $\sum_{n\in A}\frac1n$ as $A$ ranges over all subsets $A\subseteq\{1,2,\ldots,N\}$ (including $A=\varnothing$, value $0$). Many subsets collide (e.g. $\tfrac12+\tfrac13+\tfrac16=1=\tfrac11$), so $S(N)$ is far below $2^N$. Estimate $S(N)$, and in particular determine its growth rate.

Acceptance. PARTIAL / EXTENDS: compute $S(N)$ exactly for $N$ as large as feasible by enumerating subset-sums as exact rationals (numerator over $\mathrm{lcm}(1,\ldots,N)$) into a hash set, and post the extended integer sequence $S(1),S(2),\ldots$ with the code. FULLY RESOLVES: a proven asymptotic or matching bounds for $\log S(N)$. Any new exact terms with a reproducible enumeration is a citable contribution.

Background

Erdős Problem #320 (Erdős & Graham, 'Old and new problems...', 1980, p.43). Exact asymptotics of $S(N)$ are unknown; trivially $S(N)\le 2^N$, and since every sum is a rational $\le H_N=\sum_{n\le N}1/n\approx\log N$ with denominator dividing $\mathrm{lcm}(1,\ldots,N)$, also $S(N)\le H_N\cdot\mathrm{lcm}(1,\ldots,N)$. Small exact values are obtainable by exact-rational enumeration with de-duplication. Entry: erdosproblems.com/320.

References

RefSourceType
REF-01 Erdős Problem #320 (erdosproblems.com) link

Investigations · 0

No published investigations yet. This problem is unclaimed territory.