Check if a number is a perfect power
Posted: Tue Sep 17, 2019 9:35 am
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:
And now the final function:
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)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