Vtgyjfy

Since I have not found any formula for this, I've written a quick Python script to calculate the number of numbers that can be expressed as $x^2$ that are $le2^{30}$, just to see the result.

It took a little while to compute, and it returned $32769$. Wolframalpha says that $32769$ can be represented as $2^{15} + 1$, but I am still not seeing any pattern here.

EDIT: The script started from $0$, which explains the extra $+1$. The actual number of perfect squares that are $le2^{30}$ is $2^{15} = 32768$.

Also, thanks to Eevee Trainer, I've been able to solve this more efficiently for $x^2$, $x^3$ and $x^5$ using their formula:

$text{# of positive perfect k-th powers less than or equal to n} = lfloor sqrt[k] n rfloor$

Therefore, these are the number of numbers that are less than or equal to $2^{30}$ for each of the following types:

• perfect squares: $sqrt[2] {2^{30}} = 2^{15}$




• cubes: $sqrt[3] {2^{30}} = 2^{10}$




• powers of $5$: $sqrt[5] {2^{30}} = 2^{6}$

I assume you want positive integers $x$; if it's just any kind of integer (positive or negative or 0), the below can be modified to apply. If it's just any real number, then the number is clearly infinite, but I imagine that's not at all the scope. So going forward, we'll be considering positive perfect squares less than some other number.

First, let's establish the underlying pattern. This will explain why the number of squares is coincidentally equal to $2^{15}+1 = sqrt{2^{30}} + 1$.

This might be one of those kinds of cases where it's logical to try some small values first.

For example, let's find the number of positive perfect squares $s$ less than or equal to $n$.

Suppose $n=2^2$. Well, we have $s=1,4$. Suppose $n = 3^2$. Then $s=1,4,9$.

Keep trying further numbers, and it becomes clear: if $n$ is a perfect square, then

$$text{# of positive perfect squares less than or equal to n} = sqrt n$$

It should be easy to deduce that if $n$ is not a perfect square, it falls between two perfect squares, $lfloor sqrt n rfloor ^2$ and $lfloor sqrt{n+1} rfloor ^2$. But of course, there aren't going to be more perfect squares between the former and $n$, so we can just treat $n$ as the former. Then it can be deduced: for positive integers $n$,

$$text{# of positive perfect squares less than or equal to n} = lfloor sqrt n rfloor$$

Similar logic follows for the number of perfect cubes or perfect fifth powers or whatever:

$$text{# of positive perfect k-th powers less than or equal to n} = lfloor sqrt[k] n rfloor$$

(Note: This is by no means a formal argument, nor is meant to be. This is more a heuristic idea to show where the results you need come from.)

Take $n=2^{30} = (2^{15})^2$ to begin to get your solutions. So far, this only gets you $2^{15}$ solutions with respect to the number of squares (i.e. one off). This comes about on the assumption we have positive integer solutions (i.e. $x > 0$) and include the number we're searching at if it's a perfect square (i.e. $"..." leq 2^{30}$).

The only conclusion I can think of is that $0^2$ is being counted as a further solution. It depends on the exact framing of the question whether that counts - whether you wanted natural number solutions, whether you wanted nonnegative integer solutions, positive integer solutions, etc., and of course to touch on the first whether the problem comes with the implicit assumption that $0$ is a natural number (this a contentious issue in mathematics).

So whether this solution is valid needs to be addressed to whomever gave you the problem.

As for why it might have popped up in your solution and why Wolfram gave the same answer, it depends on the code you used. If you started checking squares at $0$ and not $1$, then that would explain it, but it depends on your specific implementation. Per a comment from you, it seems that you indeed included $0$ in your search so I figure that's why.

I think inclusion-exclusion should do it.

The number of the form
$x^k$ up to $n$ is
$p_k(n)
=lfloor n^{1/k} rfloor$.

So for 3 exponents,
the number,
with overcounting,
is
$s_1
=sum_{i=1}^3 p_{k_i}(n)$.

The number that
are two of the powers,
assuming that
the powers are relatively prime,
is
$s_2
=sum_limits{(i, j) = (1, 2), (1, 3), (2, 3)}p_{k_ik_j}(n)
$.

And the number that are
powers of all three exponents is
$s_3=p_{k_1k_2k_3}(n)
$.

Therefore the total number would be
$s_1-s_2+s_3$.

Only the squares up to $x=2^{15}$ satisfy the condition. Obviously there are $2^{15}+1$ of them.