Result
Let $n\in\mathbb{N}_{\geq1}$
$n$ is by definition a perfect power iff $\,\ \exists m,k\in\mathbb{N}_{>1}:n=m^{\,k}$
Let $N(n)$ be the number of perfect powers $\leq n$
We define $$\mathbb{P}_n:=\left\{p\in\mathbb{P}: p\leq\left\lfloor\log_4n\right\rfloor\right\}$$ It holds $$N(n)=\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\sum_{k=2}^{|\mathbb{P}_n|}(-1)^{k}\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)$$
Question
After getting the result, I searched for mathematical language to describe what I did.
I found the following literature:
- A counting function for the sequence of perfect powers (Theorem $2$)
- On the Distribution of Perfect Powers (Theorem $5$)
- Exact Formulae for the Perfect Power Counting Function and the $n$-th Perfect Power (Theorem $2.2$)
- Counting Perfect Powers
Overall, I found connections between my result and:
I did not study mathematics, and thus don't speak the language of mathematics, thus didn't know any of the mathematical things I just listed before I searched literature.
My question is Are there more connections?
I already asked that question on Matheplanet (german) but didn't get any answers. You can find more mathematical details over there.
Explanation
Lemma $1$
Let $n\in\mathbb{N}$ be a perfect power. It holds $$\exists\left(m\in\mathbb{N}_{>1},\,p\in\mathbb{P}\right):n=m^p$$
Proof
Let $m,k\in\mathbb{N}_{>1}\text{ with }n=m^k$ $$\exists\left(q\in\mathbb{N}_{\geq1},\,p\in\mathbb{P}\right):k=qp$$$$\Longrightarrow n=m^k=m^{qp}=\left(m^q\right)^p$$ We define $$\hat{m}:=m^q$$$$\Longrightarrow n=\hat{m}^p\text{ with }\hat{m}\in\mathbb{N}_{>1}\text{ and }p\in\mathbb{P}\,\square$$
Lemma $2$
Let $n\in\mathbb{N}_{\geq 1}$ and let $N(n)$ be the number of perfect powers $\leq n$
It holds $$N(n)\leq\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)$$
Proof
Let $m,k\in\mathbb{N}_{>1}\text{ with }m^k\leq n$
To maximize $k$ we need to minimize $m$ thus $2^k\leq n\Longleftrightarrow k\leq\left\lfloor\log_2n\right\rfloor$
Lemma $1$ yields that it's enough to consider $k\in\mathbb{P}$ to generate all perfect powers $\leq n$
Furthermore holds $m^k\leq n \Longleftrightarrow m\leq\left\lfloor\sqrt[k]{n}\right\rfloor$
Iteration over $k$ yields the result $\square$
Explanation of the $N(n)=\,...$ formula
Consider the sum: $$\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)$$ This counts how many perfect powers $\leq n$ can be generated by maximizing the value ranges for $m$ and $k$ and iterating over all possibilities with $k\in\mathbb{P}$. Due to the fact that $m^k=\hat{m}^\hat{k}$ for $m\neq\hat{m}$ and $k\neq\hat{k}$ can hold true, we count some perfect powers multiple times.
The question is: By how much are we over-counting? Let the prime factorization of $n$ be $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ such that all $p_{i\in\mathbb{N}_{\substack{\geq 1\\\leq k}}}$ are distinct. Then, $n$ is a perfect power if and only if $\gcd(a_1,\,a_2,\,...,\,a_k) > 1$. When we look at the prime factorization of the $\gcd$, the prime factors tell us whether the respective perfect power was counted multiple times. Let $M$ be the number of times a perfect power $n$ is counted, which can be expressed using the prime omega function: $$M=\omega(\gcd(a_1,\,a_2,\,...,\,a_k))$$ If $M>1$, we have over-counted by $M-1$. The expression $\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor$ is crucial for compensating for the over-counting. Since $n\geq 1$, these terms are always $\geq 1$ and reach the value of $2$ at $n=2^{\prod_{p\in P}p}$, the value of $3$ at $n=3^{\prod_{p\in P}p}$, and so on. They are thus triggered whenever an $n$ that has led to over-counting is reached.
Consider the sum: $$\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}$$ Note that $|X|\geq 2$, as $\sum_{k=2}^{|\mathbb{P}_n|}$ starts at $k=2$, so we only trigger for $M>1$ and not for $M=1$. Thus, we iterate over all $k$-element subsets of $\mathbb{P}_n$ for $k\geq 2$. The condition $\prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor$ serves to stop summing $\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor$ which would only equal $1$, resulting in $\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)=0$. The definition of $\mathbb{P}_n$ also has a stopping condition with $p\leq\left\lfloor\log_4n\right\rfloor$. The smallest prime is $2$, and the smallest $k$ is also $2$. It's about $\left\lfloor\sqrt[2p]{n}\right\rfloor>1$ with $p\in\mathbb{P}_{>2}$.
The only thing left is $(-1)^{k}$. Although we've already discussed triggers, we've only talked about them being triggered, not about what is subtracted when they are. When a trigger is triggered, the value of $k$ tells us by how much we've over-counted, which is $k-1$. However, we have to consider how many and which triggers are triggered at the same time. Using binomial coefficients, one eventually arrives at $(-1)^{k}$ as the "factor for subtraction" :)
From this, we realize that using the Möbius function, we can alternatively express the following: $$N(n)=\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\sum_{k=2}^{|\mathbb{P}_n|}\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}\mu\left(\prod_{p\in P}p\right)\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)$$
