Consider the series,
$1,2,3,2,5,6,7,2,3,10,11,12,13,14,15,2,17,18,19,20,21,22,23,24,5,26,3,\ldots$
The $i_{th}$ number of the sequence is the least integer $k$ such that $i = k^{\alpha}$ for some $\alpha.$
How do we find the sum of first $N$ terms of the above series.
My Approach:
Sum of first $N$ terms would be less than $n*(n+1)/2$.
For each perfect power $k^{\alpha}$ less than equal to $N$, we need to subtract $k^{\alpha}-k$. But I am unable to converge onto the final formula or result.
The naive sum (ignoring all powers) would be $$\sum_{k=1}^N k=\frac{N(N+1)}2.$$ To correct perfect squares, subtract $k^2$ and add $k$ for eack $k\le\sqrt N$, i.e., add $$\Delta_2=\sum_{k=2}^{\lfloor \sqrt N\rfloor}(k-k^2) $$ To correct cubes, subtract $k^3$ and add $k$ for eack $k\le\sqrt[3] N$, i.e., add $$\Delta_3\sum_{k=2}^{\lfloor \sqrt[3] N\rfloor}(k-k^3) $$ More generally, for every $m$ with $\sqrt[m]N\ge 2$ (i.e., for $m\le \log_2 N$), we should add $$\Delta_m=\sum_{k=2}^{\lfloor \sqrt[m] N\rfloor}f_m(k), $$ where - contrary to what the formulas for $\Delta_2$ and $\Delta_3$ might suggest - the function $f_m$ is not given by $f_m(k)=k-k^m$. Rather, we notice that for every $m$th power we apply the correction $f_d$ for all divisors $d>1$ of $m$. Thus what we want is that (with the convention $f_1(x)=x$) $$ \sum_{d\mid m}f_d(x^{m/d})=x.$$ By Möbius inversion, $$ f_m(x)=\sum_{d\mid m}\mu(d)x^d.$$ So the result is $$ 1+\sum_{m=1}^{\lfloor \log_2 N\rfloor} \sum_{k=2}^{\lfloor\sqrt[m] N\rfloor}\sum_{d\mid m}\mu(d)k^d=1+\sum_{m=1}^{\lfloor \log_2 N\rfloor} \sum_{d\mid m}\mu(d)\sum_{k=2}^{\lfloor\sqrt[m] N\rfloor}k^d,$$ which should be feasible to compute for even largish $N$ (especially if one notices that $\sum k^d$ is some polynomial of degree $d+1$ in the upper limit)