7
\$\begingroup\$

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)).

\$\endgroup\$
  • 1
    \$\begingroup\$ Is one number per line an acceptable output format? \$\endgroup\$ – Peter Taylor May 10 '11 at 12:23
  • \$\begingroup\$ 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 \$\endgroup\$ – YOU May 10 '11 at 13:33
  • \$\begingroup\$ @s-mark What if you print the output to the file? You can assume printing to files for large outputs. \$\endgroup\$ – fR0DDY May 10 '11 at 13:59
  • \$\begingroup\$ @peter-taylor Yes. \$\endgroup\$ – fR0DDY May 10 '11 at 14:00
  • \$\begingroup\$ @fR0DDY, Oh, ok if that is acceptable. I thought I have to output to console. \$\endgroup\$ – YOU May 10 '11 at 14:02

14 Answers 14

4
\$\begingroup\$

Golfscript, 18 characters

~.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.

\$\endgroup\$
4
\$\begingroup\$

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.

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

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

\$\endgroup\$
2
\$\begingroup\$

Python 68 Chars

r=input();i=0;exec'i+=1;print int(i+(i+i**(1./r))**(1./r));'*input()
\$\endgroup\$
2
\$\begingroup\$

Golfscript (18 17 chars)

~.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++);
}
\$\endgroup\$
  • \$\begingroup\$ @S.Mark, I see what the problem is. Hopefully fixed, if not I'll have a look when I have access to the interpreter. \$\endgroup\$ – Peter Taylor May 10 '11 at 15:13
  • 1
    \$\begingroup\$ Seems to work now. You can save 2 characters by joining with n instead of ' ' (see fR0DDY's comment on the question). \$\endgroup\$ – Ventero May 10 '11 at 15:20
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor May 10 '11 at 15:27
  • \$\begingroup\$ Woops, didn't realize that you were the one who asked :) \$\endgroup\$ – Ventero May 10 '11 at 15:40
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Windows PowerShell, 88

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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(" ")}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Are you sure this is solving the correct problem? I don't see any raising numbers to powers. \$\endgroup\$ – Peter Taylor May 10 '11 at 13:48
  • \$\begingroup\$ 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++. \$\endgroup\$ – Joey May 10 '11 at 13:58
  • \$\begingroup\$ 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. \$\endgroup\$ – user42 May 10 '11 at 18:24
0
\$\begingroup\$

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(","))}
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.