What percentage of the numbers from one to a million can be represented as the sum of a square and a non-negative cube?

(In reply to

potential solution by Charlie)

That 2.5% estimate has to be way conservative, Charlie. You have already said that 70% of the squares and almost 80% of the cubes are less that 500,000. These are all valid combinations. Admittedly, there may be some duplicates, but that will be more than offset by cases where one of the numbers is over 500,000. I estimate 100,000 * 80% * 80% / 1,000,000 ~ 6.5%.

Just guessing.