First, remark that if we plug in $x = a_{n-1}$ the RHS and you get the RHS is $1$ too large. Thus $a_n = a_{n-1} + 1$ if there does not exist positive integers $i,j$ such that $a_i \cdot j^k = a_n$. This motivates us to conjecture the sequence of $a_i$ is all numbers such that for all primes $p$ we have $p^k$ does not divide them. We prove this by induction. Suppose for all $i \le n-1$ we have the $a_i$ are the set of above described numbers. Call numbers $n$ such that $v_p(n) \ge k$ for some $p$ a ksunish number. Remark that each ksunish number can be uniquely decomposed into the product of a $k^th$ power and a non-ksunish number. Now consider the numbers $x$ above $a_{n-1}$. First set $x = a_{n-1} + 1$. Remark that $x$ is a solution to the equation iff $x$ is not a ksunish number. If $x$ is a ksunish number, due to the unique decomposition statement above the RHS only increments up by $1$ due to the inductive hypothesis. Thus the RHS remains $1$ higher. Continue incrementing $x$ by $1$ and by the same logic we get $x$ is a solution iff $x$ is not a ksunish number due to the difference between the two sides staying at $1$. Thus $a_n$ is the first non-ksunish number after $a_{n-1}$ so we have completed our induction. Now note that all primes are non-ksunish numbers so we are done.

Take $b_n$ as the set of numbers that are $k$-power free. We claim $a_n=b_n$ which proves the problem. We use strong induction. The base cases are trivial. The main claim is that $\sum_{i=1}^n \left\lfloor \sqrt[k]{\frac{c}{b_i}} \right\rfloor = c$, where $b_n \le c < b_{n+1}$. Partition $S=\{1,2, \cdots c\}$ by $S_i = \{a^k \cdot b_i | a \in \mathbb{N}\}$ for $1 \le i \le n$. Then, we have $|S_i| = \left\lfloor \sqrt[k]{\frac{c}{b_i}} \right\rfloor$, giving the desired statement. Therefore, assuming that $a_m=b_m$ for all $m \le n-1$, we have $$b_n=\sum_{i=1}^n \left\lfloor \sqrt[k]{\frac{b_n}{b_i}} \right\rfloor=1+\sum_{i=1}^{n-1} \left\lfloor \sqrt[k]{\frac{b_n}{b_i}} \right\rfloor$$ so $a_n \le b_n$. If $a_n<b_n$, we would have $$a_n = 1+\sum_{i=1}^{n-1} \left\lfloor \sqrt[k]{\frac{a_n}{b_i}} \right\rfloor = 1+a_n$$ by our previous lemma. This gives us that $a_n=b_n$, as required.

The bulk of the solution is contained in the following lemma: Lemma: The quotient $a_m / a_n$ is never the $k$th power of a rational number for $m > n \ge 1.$ Proof of Lemma: We go by strong induction on $m.$ Assume the claim true for $1, 2, \cdots, m$ and we'll prove it true for $m + 1.$ For $m \in \mathbb{N}$, introduce the function $f_m : \mathbb{N} \mapsto \mathbb{N}$ defined by $f_m(x) = x - \sum_{i = 1}^m \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor.$ We claim that $$\begin{align*} f_m(x) + 1 \ge f_m(x + 1) \ge f_m(x) \qquad (\star) \end{align*}$$ for all $x.$ Moreover, $f_m(x + 1) \ne f_m(x)$ iff $(x + 1)/a_n$ is not a perfect $k$th power of a rational number for all $1 \le n \le m. \qquad (\dagger)$ The left inequality is obvious. To prove the right inequality, observe that $$\begin{align*} f_m(x + 1) - f_m(x) = 1 - \sum_{i = 1}^m \left(\left\lfloor \sqrt[k]{\frac{x + 1}{a_i}} \right\rfloor - \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor\right). \end{align*}$$ Each term in the above summation is equal to $1$ if $(x + 1)/a_i$ is a perfect $k$th power and equal to $0$ otherwise. However, if two terms were equal to $1$, then $(x + 1)/a_i$ and $(x + 1)/a_j$ would both be perfect $k$th powers for some $1 \le i < j \le m.$ Hence, their quotient $a_i / a_j$ would be a $k$th power of a rational number, impossible. Thus, at most one term in the summation is equal to $1$ and both $(\star)$ and $(\dagger)$ follow. Now, by definition, $f_m(a_m) = 0$ and $a_{m + 1}$ is the minimal $x > a_m$ such that $f_m(x) = 1.$ Thus, $(\star)$ implies that $f_m(x) = 0$ for all $x \in [a_m, a_{m + 1})$ and $f_m(a_{m + 1}) = 1.$ Then $f(a_{m + 1}) \ne f(a_{m + 1} - 1)$, so according to $(\dagger), a_{m + 1} / a_n$ is never the $k$th power of a rational number for $m + 1 > n \ge 1$, completing the induction. $\blacksquare$ _________________________________________________________________________________________________________________ Back to the problem at hand, suppose by way of contradiction that $a_m < p < a_{m + 1}$ for some prime $p$ and $m \in \mathbb{N}.$ Then as $p \in (a_m, a_{m + 1})$, it follows from the above that $f_m(p) = f_m(p - 1) = 0.$ Thus by $(\dagger), p / a_n$ is the perfect $k$th power of a rational number for some $1 \ne n \le m.$ However, this is clearly impossible since $p \nmid a_n$ due to $p > a_m \ge a_n$ and therefore the exponent of $p$ in $p / a_n$ is not a multiple of $k.$ This contradiction completes the proof. $\square$

Hmm... Interesting So we get for every natural number $n$ there is unique $i,j$ that $n=a_{i}j^{k}$

We claim $a_m$ is the $m$'th $k$'th power free number. We induct on $m$, with $m=1$ clear. Suppose $a_1,\ldots,a_{m}$ is the sequence of $k$'th power free numbers. We know when $x=a_m$, the LHS and RHS are equal by induction. Notice that if $a_m+1$ is $k$'th power free, then the LHS increases by 1, while the RHS increases by 2; 1 since we have added one more term, and 1 since one of the existing terms increase from what they were at $x=a_m$ (note that it increases exactly by 1 since every number can be uniquely written as a $k$'th power times a $k$'th power free number). After this, at each step where we don't have a $k$'th power free number, both the LHS are RHS will increase by 1. We can keep continuing in this logic, which means we know that unless $a_{m+1}$ is divisible by some $k$'th power, the LHS and RHS cannot be equal. This process will only stop when $a_{m+1}$ is $k$'th power free; in that case, the LHS will increases by 1 and the RHS will stay the same as it was with $x=a_{m+1}-1$. This completes the induction. Obviously, primes are $k$'th power free, so we are done.

Weird problem. For positive integers $u$ and $v,$ let $f_u(v)$ be the number of integers $m$ such that $1\le m\le u$ and $v/a_m$ is a perfect $k$th power. Note that for all $n,$ $a_{n+1}$ is the smallest integer solution to $$x=1+\sum_{i=a_n+1}^{x}f_n(i).$$ $\textbf{Claim: }$ $a_n$ is the $n$th integer that is $k$th-power free. $\textbf{Proof: }$ Induct on $n,$ the base case being clear. Suppose the numbers $a_1,a_2,\dots,a_i$ are the first $i$ positive integers that are $k$th-power free. This implies that for all integers $x>a_i,$ we have $f_i(x)\in\{0,1\}.$ Hence, by our observation above, $a_{i+1}$ is the smallest integer $x$ greater than $a_i$ for which $f_i(x)=0.$ But this implies that $a_{i+1}$ is the next $k$th-power free integer, completing the induction. $\blacksquare$ The problem statement is a natural corollary of our above claim.

I claim that for each positive integer $k \geq 2$, the sequence $a_i$ is the increasing sequence of $k$th power free positive integers. We will use proof via induction on $n$ for fixed $k$. The base case of $n = 1$ is clear; $a_1 = 1$. Next, for the inductive hypothesis, suppose that $a_1 < a_2 < \ldots < a_m$ are the $m$ smallest $k$th power free positive integers. We need to show that $a_{m+1}$ is the next largest $k$th power free positive integer. Consider the equation $$x = 1 + \left\lfloor\sqrt[k]{\frac{x}{a_1}}\right\rfloor + \ldots + \left\lfloor\sqrt[k]{\frac{x}{a_n}}\right\rfloor.$$ If $x = a_m + 1$ is $k$-th power free, then from $x = a_m$, the LHS increases by $1$ and the RHS by $2$, one from one new term and one from an already existing term. If $x = a_m + 1$ is not $k$th power free, then the LHS and RHS similarly both increase by $1$. This implies that $a_m + 1$ is the next $k$th power free positive integer, as desired. $\square$ Since all primes are $k$th power free for all $k \geq 2$, we are done. $\blacksquare$

.

I claim the sequence $a_1, a_2, \dots$ is exactly the sequence of integers not divisible by any $k$-th power besides $1$; call these integers $k$-free. Induct with base case obvious; assume $a_1, a_2, \dots , a_m$ are the $m$ smallest $k$-free integers, and we show $a_{m+1}$ is the next smallest one. Denote $$f(x)=1+\displaystyle\sum\limits_{i=1}^{m} \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor$$ Note $f(x+1)-f(x)$ is equal to the number of $a_i$ with $1 \le i \le m$ such that $\frac{x+1}{a_i}$ is a $k$-th power. If $x+1$ is $k$-free then this is zero. Otherwise, since the $a_i$ are $k$-free, there is exactly one such $a_j$ satisfying the condition. Since $f(a_m)$ is clearly equal to $a_m+1$, we get $a_{m+1}$ must be the next smallest $k$-free integer as desired.

Let $$f(x) := 1+\displaystyle\sum\limits_{i=1}^{m} \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor.$$ Note that $f(x)-f(x-1)$ is the number of $1 \le i \le m$ such that $\sqrt[k]{\tfrac{x}{a_i}}$ is integral. Thus, $f(x)-f(x-1)=0$ if and only if $x$ is $k$-free, so inductively we have that $a_n$ is the $n$th integer which is $k$-free, as desired.

wait f(x+1) - f(x) is a thing oops In fact, we have the following characterization of $a_n$: Claim: $a_n$ is the $n^{th}$ $k$-free integer, that is the $n^{th}$ integer that is not divisible by any perfect $k^{th}$ power. (This is clearly sufficient.) Proof. Induct, base case $n = 1$ with $a_1 = 1$ and $a_2 = 2$. Let $$f(x) = 1 + \sum_{i=1}^{n-1} \left\lfloor \sqrt[k]{\frac{x}{a_i}} \right\rfloor.$$ Note that as we increase $f(x)$ from $a_n$ to $a_{n+1}$ (the next integer that is $k$-free), $f(x)$ increases by $1$ and $x$ increases by $1$ until we hit $a_{n+1}$ - as $x$ is not $k$-free, there exists a unique representation $\sqrt[k]{x} = b_x\sqrt[k]{c_x}$ where $c_x$ is $k$-free, and thus the term $\left \lfloor \sqrt[k]{\frac{x}{c_k}} \right \rfloor$ in the definition of $f(x)$ will increase by $1$, and all others will remain the same as in the definition of $f(x-1)$. However, at $x = a_{n+1}$, $f(x)$ does not increases while $x$ increases by $1$, so $x$ will "catch up" to $f(x)$ and thus $f(x) = x$, while all numbers smaller than $x$ do not have this property. This completes the induction and we're done. $\square$

Fix $k \ge 2$, we provide the following characterization for $a_i$ which implies the problem. Lemma. $a_i$ is the increasing sequence of the non $k$-th powers. Proof. This is straightforward. $\Box$ For concreteness, we provide a small chart $$\begin{array}{c|cccccccccc} & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 & a_8 & \\ \hline 2 & 1 & 2 & \color{red}3 & \color{red}5 & 6 & 7 & \color{red}8 & \color{red}10 & \\ \hline 3 & 1 & 2 & 3 & 4 & 5 & 6 & \color{red}7 & \color{red}9 & \\ \end{array}$$ Where the numbers painted in red are consecutive to some perfect power that are skipped in the cases $k=2$ and $k=3$.