# Remove r-th powers

Given two numbers r and n on separate lines, write a program to print n natural numbers starting from 1 onwards, excluding the r-th powers. For example,

If r=2 and n=10, the results would be 2,3,5,6,7,8,10,11,12,13

4 and 9 were excluded because 4 is 2^2 and 9 is 3^2

Sample Input
2
10
Sample Output
2 3 5 6 7 8 10 11 12 13

Sample Input
3
30
Sample Output
2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 29 30 31 32 33

1. 1 < r < 10
2. 0 < n < 1,000,000

Since nobody came up with this, here's a hint to reduce your solution sizes:

The ith term of the output is given by floor(i+pow(i+pow(i,1/r), 1/r)).

• Is one number per line an acceptable output format? – Peter Taylor May 10 '11 at 12:23
• Just printing numbers 2 to 1,000,000 with ruby/python take around 26 seconds on my dual core machine, I think your upper limit is too high, IMHO – YOU May 10 '11 at 13:33
• @s-mark What if you print the output to the file? You can assume printing to files for large outputs. – fR0DDY May 10 '11 at 13:59
• @peter-taylor Yes. – fR0DDY May 10 '11 at 14:00
• @fR0DDY, Oh, ok if that is acceptable. I thought I have to output to console. – YOU May 10 '11 at 14:02

~.3*,.{3$?}%-@;<n*  Basically a direct port of my Ruby solution. Also probably not completely golfed yet, I'll take a look at it later today again. ## Ruby, 56 characters r,n=$<.map &:to_i;puts ([*l=1..2*n]-l.map{|i|i**r})[0,n]


Pretty straightforward (and similar to Lars' solution). Takes about 5 seconds to complete for r = 2, n = 1000000 and 8 seconds for r = 10, n = 1000000 here.

• Nice improvement! Just had another of those "duh!" moments. – Lars Haugseth May 10 '11 at 16:43

## Python 2, 84 83 80 chars

r,n=input()
r+=.0
i=c=1
while c<=n:
p=i**(1/r)
if p!=int(p):print i;c+=1
i+=1


Runs in about 3 seconds for r=2, n=1000000

Python 68 Chars

r=input();i=0;exec'i+=1;print int(i+(i+i**(1./r))**(1./r));'*input()


~.3*,@{?}+1$%-<n*  This turns out to be similar to Ventero's solution, but slightly shorter (at time of writing!) For a more efficient solution, 26 chars gives ~2.@{.2$4$?={)\)\}*.p)}*];  which uses the obvious algorithm: int k = 2, x = 2; for (i = 0; i < n; i++) { if (pow(k,r) == x) {k++; x++;} println(x++); }  • @S.Mark, I see what the problem is. Hopefully fixed, if not I'll have a look when I have access to the interpreter. – Peter Taylor May 10 '11 at 15:13 • Seems to work now. You can save 2 characters by joining with n instead of ' ' (see fR0DDY's comment on the question). – Ventero May 10 '11 at 15:20 • @Ventero, why do you think I asked that? By I think there might be potential for saving a couple more by rewriting with a loop using p. – Peter Taylor May 10 '11 at 15:27 • Woops, didn't realize that you were the one who asked :) – Ventero May 10 '11 at 15:40 ## Ruby (79 77 chars) n,r=$<.map &:to_i
a=(0..n*2).map{|x|[x,x**r]}.transpose
p (a[0]-a[1])[0,n]*?,


Yes, this does a lot of wasted effort, but it completes in about 8 secs for n=1E6,r=10 on my laptop.

for($x,$r,[int]$n=,1+@($input);$n--){if((1..$n|%{[Math]::Pow($_,$r)})-eq$x){$x++}($x++)}  Fairly straightforward, but probably way too long. ## Qwerty RPN (52) @=r@=n>L$i)=i$i 1$r/^:\=<S$n(=n$i#32.>S 0$n=<B 1<L>B  Ungolfed @ =r ; input number r @ =n ; input number n, counter variable 0 =i ; the next number to be printed (pre-assigning variable is optional) >loop ; label loop$i ) =i ; pre-increase i

$i 1$r / ^ : \ = <skipped ; skip printing and increasing counter n if i^(1 / r) == round(i^(1 / r))
$n ( =n ; decrease n$i #    ; print number i
32 .    ; print space
>skipped

0 $n = <break ; if n == 0: break loop 1 ; TRUE <loop ; go back to beginning of loop >break ; this is where the loop ends  # J, 32 (4 :'y{.I.(~:<.)x%:i.1001000')/,  This assumes the input has the shape 2 1, i.e., a vertical list of two rows with one atom per row, e.g.,  2 10  This solution is instantaneous for r = 9, n = 999999, which (unless I've misread the question) are the upper bounds for the input parameters. ## JavaScript, 118 111 bytes function d(r,n){for(var a=[],i=m=0,p=1;i<n;p++,m=Math.pow(p,1/r))if((m|0)!=m){a.push(p);i++}return a.join(" ")}  # Perl - 51 map{print$_.$/if($_**(1/$ARGV[0])!~/^\d+$/)}1..pop;


Not quite up to spec, as it takes ~12/13s for r=10/n=1000000, and takes r/n as command line args instead of on separate lines -- but other than that it works.

C++, 97 95 90

int main(){int r,s,n,m=0;cin>>r;cin>>n;s=r;while(m++!=n)r!=m?cout<<m<<' ',r*=r<m?s:1:++n;}


(eventually +20)

using namespace std;

• Are you sure this is solving the correct problem? I don't see any raising numbers to powers. – Peter Taylor May 10 '11 at 13:48
• It solves the wrong problem, indeed. Also it's missing a few namespace declarations somewhere and an #include to even compile. And my compiler tells me that main() as default-int isn't valid in C++. – Joey May 10 '11 at 13:58
• sorry about that guys, thanks for support. glad your concerns joey, but my project file adds them by default. eventualy i can add using declaration. – user42 May 10 '11 at 18:24

Scala 172

def p(r:Int,n:Int)={def f(n:Int):Stream[Int]=n#::f(n+1);lazy val i=f(0);lazy val o=i.filter(a => math.pow(a,1.0/r)!=math.pow(a,1.0/r).toInt);print(o.take(n).mkString(","))}


# Python 2, 60 bytes

r,n=input();i=0
while n:
i+=1
if i**r**-1%1:
print i;n-=1


Try it online!