# Code-Challenge: Non trivial powers Revisted

## Challenge

In this task you would be given an integer N you have to output all non-trivial power representation of the integer.

Non-trivial power means the base and exponent are > 1

The input N is given in a single line,the inputs are terminated by EOF.The number of inputs would not exceed 10000 values.

The challenge is to implement the fastest solution so that it can process a maximum of 10000 values as fast as possible.

Input

`````` 1745041
1760929
1771561
1852321
1868689
1874161
1885129
1907161
1953125
113795717542678488615120001
113795717546049421004105281
``````

Output

`````` 1745041 = 1321^2
1760929 = 1327^2
1771561 = 11^6 121^3 1331^2
1852321 = 1361^2
1868689 = 1367^2
1874161 = 37^4 1369^2
1885129 = 1373^2
1907161 = 1381^2
1953125 = 5^9 125^3
113795717542678488615120001 = 10667507560001^2
113795717546049421004105281 = 10667507560159^2
``````

Constraints

• N is less than 30 digits long to test your favorite integer factorization algorithm ;-)
• Assume that for ever input N,at-least one non-trivial power representation is possible.
• You can use any language of your choice
• Fastest solution,with the most efficient time complexity wins!
-
most efficient time complexity and fastest (for finite input) are not equivalent :) – belisarius Apr 3 '11 at 13:22
It's kinda awkward competing for speed in such a fast task, since the program will end up I/O bound. – eBusiness Apr 3 '11 at 14:49
What if N has no non-trivial power representation? Should we output "N =" or nothing? – Keith Randall Apr 3 '11 at 15:44
@Keith Randall:I have updated the constraints. – Quixotic Apr 3 '11 at 16:06

# C - No bigints

My solution use a 64 bit float and a 64 bit integer in combination to produce the result without using slow bignumber arithmetic. First a possible set of values that fit the high-order bits are produced using floats, then the low order is checked using integers. Due to 64 bit floats having 53 bit mantissa the method will break for numbers around 106 bit in length, but the task was only for up to 100 bit numbers.

``````#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#define i64 unsigned long long
#define i32 unsigned int
#define f64 double

int main(){
char inp[31];
while(1==scanf("%30s",inp)){
printf("%s =",inp);

f64 upper=strtod(inp,NULL);
//i64 lower=strtoull(inp,NULL,10);
//i64 lower=atoll(inp);
//Neither library function produce input mod 2^64 like one would expect, fantabulous!
i64 lower=0;
i32 c=0;
while(inp[c]){
lower*=10;
lower+=inp[c]-48;
c++;
}
f64 a,b;
i64 candidate;
f64 offvalue;
f64 offfactor;
i32 powleft;
i64 product;
i64 currentpow;
for(a=2;a<50;a++){ //Loop for finding large bases (>3).
b=1.0/a;
b=pow(upper,b);
candidate=(i64)(b+.5);
if(candidate<4){
break;
}
offvalue=b-(f64)candidate;
offfactor=fabs(offvalue/b);
if(offfactor<(f64)1e-14){
product=1;
powleft=(i32)a;
currentpow=candidate;
while(powleft){ //Integer exponentation loop.
if(powleft&1){
product*=currentpow;
}
currentpow*=currentpow;
powleft=powleft>>1;
}
if(product==lower){
printf(" %I64u^%.0lf",candidate,a);
}
}
}
for(candidate=3;candidate>1;candidate--){ //Loop for finding small bases (<4), 2 cycles of this saves 50 cycles of the previous loop.
b=log(upper)/log(candidate);
a=round(b);
offfactor=fabs(a-b);
if((offfactor<(f64)1e-14) && (a>1)){
product=1;
powleft=(i32)a;
currentpow=candidate;
while(powleft){ //Integer exponentation loop.
if(powleft&1){
product*=currentpow;
}
currentpow*=currentpow;
powleft=powleft>>1;
}
if(product==lower){
printf(" %I64u^%.0lf",candidate,a);
}
}
}
printf("\n");
if(inp[0]==113){ //My keyboard lacks an EOF character, so q will have to do.
return 0;
}
}
return 0;
}
``````

As for runtime, ideone produce a clean 0 http://www.ideone.com/HJl2f this should be a pretty superior method, but any attempt to verify this will drown in I/O.

-

## Python, 207 chars

This takes O(log2 N) bigint ops. O(log N) different exponents to try, and O(log N) binary search to find each base.

``````import sys
p,s=2,''
while 1<<p<=N:
i,j=2,N
while j>i+1:
m=(i+j)/2
if m**p>N:j=m
else:i=m
if i**p==N:s+=' %d^%d'%(i,p)
p+=1
if s:print N,'=',s[1:]
``````
-
+1,cute use of binary search :-) – Quixotic Apr 3 '11 at 16:06
You know, you could ditch the golfing length variable names ;-) – eBusiness Apr 3 '11 at 16:07
@eBusiness, force of habit... – Keith Randall Apr 3 '11 at 16:11
`map(int, sys.stdin)` should work fine – gnibbler Apr 4 '11 at 2:55

## Ruby

Non-golfed, not-really-optimized solution. I hope I didn't mess up my math.

Roots are calculated first using core `sqrt` and `cbrt` methods, then using dumb approximation (binary search).

On my PC, 10000 long random inputs (not necessarily actually having non-trivial representations) take ~30 seconds (see the `bench` method).

``````def root start, exp, startapprox=nil
if exp==1
return start
elsif exp==2
return Math.sqrt(start).round
elsif exp==3 and Math.respond_to? :cbrt # 1.9 only
return Math.cbrt(start).round
else
lower=0
upper=startapprox||Math.sqrt(start).ceil

until upper-lower<=1
res=(lower+upper)/2

if res**exp<start
lower=res+1
else
upper=res
end
end

distlow=(start - lower**exp).abs
distupp=(start - upper**exp).abs

if distlow<distupp
return lower
else
return upper
end
end
end

def powers number
ret=[]
skip=[]

maxexp=(Math.log2 number).floor
prev=nil

2.upto(maxexp) do |exp|
next if skip[exp]

rt=root number, exp, prev
if number==rt**exp
ret<<"#{rt}^#{exp}"
else
(exp..maxexp).step(exp){|i| skip[i]=true} # if it's not 2nd power, it cant be 4th power etc
end

prev=rt
end

"#{number} = #{ret.reverse.join ' '}"
end

def bench n=10
require 'benchmark'

Array.new(n){Benchmark.realtime{powers rand 1e30}}.inject(:+)
end

 Can't you just calculate roots as `a**(1/b)`? – eBusiness Apr 4 '11 at 12:11 @eBusiness Whoa, true. I've never though of it. It reduces execution time to ~10 seconds. – Matma Rex Apr 4 '11 at 15:30