Check if a number is a perfect power

Started by cameyo, September 17, 2019, 02:35:51 AM

Previous topic - Next topic

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:
(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:
(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