What percentage of the numbers from one to a million can be represented as the sum of a square and a non-negative cube?
A055393 Sum of a square and a nonnegative cube in more than one way.
The b-file has a list of the first 10000 numbers. 1000000 is the 6706th term. This would contain many of the duplicates in Jer's count of 84545, leaving an upper bound of 77839 numbers from 1 to 1000000 which can be expressed as the sum of a square and a nonnegative cube.
Some help from the OEIS
