Check if a number is a perfect power

Q&A's, tips, howto's
Post Reply
cameyo
Posts: 111
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy

Check if a number is a perfect power

Post by cameyo »

A perfect power is a number n of the form m^k, where m>1 is a positive integer and k>=2. If the prime factorization of n is n=p1^(a1)*p2^(a2)...pk^(ak), then n is a perfect power iff GCD(a1,a2,...,ak) > 1.
The "factor-exp-list" function calculates the list of exponents of the factorization of the number x:

Code: Select all

(define (factor-exp-list x)
  (if (= x 1) '(1)
    (letn (fattori (factor x)
           unici (unique fattori))
       (count unici fattori))))
1000 = 2^3 * 5^3
(factor-exp-list 1000)
;-> (3 3)
And now the final function:

Code: Select all

(define (checkpower n)
    (if (> (setq a (apply gcd (factor-exp-list n))) 1)
        (list (ceil (pow n (div 1 a))) a)
        nil)))
(checkpower (pow 3 12))
;-> (3 12)
(checkpower (pow 4 25))
;-> (2 50)
(checkpower (+ (pow 3 7) 1))
;-> nil

Post Reply