What percentage of the numbers from one to a million can be represented as the sum of a square and a non-negative cube?
There are about 1,000 perfect squares below a million and about 100 perfect cubes. In each case, the concentration is highest at the lowest end of the number line segment.
There are 100,000 ways of forming sums from these two sets, but of course some of the sums will lie above one million. This is mitigated by the fact that the member numbers are more concentrated at the lower end. More than 700 of the 1000 squares lie below the halfway mark of 500,000, and 79 out of the hundred cubes.
But also two such sums might add up to the same value, reducing the mitigation effect.
As an estimate then, let's assume half the squares are usable and half the cubes, in any combination: 500 * 50 = 25,000 valid sums, or 2.5% of the numbers from 1 to 1,000,000.
One would think that as the upper limit goes higher, the concentration effect and the double hits on numbers would both decrease and this calculation will be ever more valid asymptotically, with a resulting decrease in the percentage, as we'd be calculating sqrt(n)*cbrt(n)/4 out of a range of n. That's n^(5/6)/(4*n) = 1/(4*n^(1/6)). Converted to a percentage that's 25/n^(1/6).
Posted by Charlie
on 2016-08-22 10:03:49