Determining if n is of the form m^k?



Am 26 Apr 2006 um 16:29 hat Raymond Toy geschrieben:

> 
> I think it would be nice if 6*2^k became 3*2^(k+1), but that would
> require factoring 6 (easy).  In general, factoring would be hard, and
> perhaps not worth the effort.
> 
> Maybe a separate function could be made available to try much harder
> to simplify these numerical products.
> 
> Ray
> 

Hello Ray,
factoring isn't as hard as you might think. There is a new implementation of integer factoring 
in cvs now.
In src/ifactor.lisp you will find a function `get-factor-list', which could possibly fit your needs. 
Give it a try.
Remark: there will be version 1.3 of ifactor.lisp in a couple of days. Some things will change 
a little bit, but `get-factor-list' will remain unchanged.
Volker

(%i1) showtime:true$Evaluation took 0.00 seconds (0.00 elapsed)

(%i2) factor(123456791*123456791)$Evaluation took 59.96 seconds (59.96 elapsed)

(%i3) load("D:/ifactor.lisp")$Evaluation took 00.10 seconds (00.10 elapsed)

(%i4) factor(123456791*123456791)$Evaluation took 0.21 seconds (0.21 elapsed)

The evaluation time varies a little bit, the factoring uses probabilistic methods.

(%i5) :lisp(get-factor-list 123456789)
((3803 1) (3607 1) (3 2))

(%i5) :lisp(get-factor-list 1024)
((2 10))