Topic: How to find a Integer number's prime root and exponent

[chlh_jd]

Hi All
There is a Ineger number , how to find it's prime root and exponent ?
If function Foo to solve it .

Code: [Select]

(Foo 19683) --> '(3 9) ;;(expt 3 9) = 19683
(Foo 19487171) -->'(11 7) ;; (expt 11 7) = 19487171
(Foo 48828125 ) -->'(5 11) ;; (expt 5 11) = 48828125
(Foo 256) --> '(2 8)  ;; (expt 2 8) = 256
(Foo 144) --> NIL ;;(expt 12 2) = 144 , But 12 is not Prime Number .


[chlh_jd]

my version

Code: [Select]

(defun is-prime (n / foo)
  (defun foo  (n try)
    (if (= n try)
      T
      (if (zerop (rem n try))
nil
(foo n (+ try 1))
)
      )
    )
  (foo n 2)
  )
(defun is-power (num n / foo)
  (setq num (float num))
  (defun foo (num n i)
     (cond ((= num 1)
    i)
   ((> num 1)
    (foo (/ num n) n (1+ i))
    )
   )
    )
  (foo num n 0))
(defun prime-root (num / foo)
  ;; by GSLS(SS) 2012-10-10
  (defun foo (num n / i)
    (cond ((and (= (rem num n) 0)
(is-prime n)
(setq i (is-power num n))
(> i 0))
   (list n i))
  ((<= n num)
   (foo num (1+ n)))))
  (foo num 2)
  )
;;;
(prime-root 19683) ;; --> '(3 9)
(prime-root 19487171) ;; -->'(11 7)
(prime-root 48828125) ;; --> '(5 11)
(prime-root 256) ;; --> (2 8)
(prime-root 144) ;; --> NIL


[chlh_jd]

But somewhat surprisingly, this can not return value ?

Code: [Select]

(prime-root (expt 11 20))
Is it a Vlisp  BUG ?

Code: [Select]

(rem (expt 11 20) 11) --> 6
(rem (expt 11. 20) 11) --> 7.0


[dgorsman]

When you provide a number as "6" to a function, its considered an integer.  If you provide a number as "6.0" its considered a real.  When LISP does math on two integers, the result is typically an integer; when one of the values is a real the result is a real.  Sometimes you need to force values from integers to reals in order to get desired results.

[Stefan]

For reasonable integers

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors (n / x l old)
2.   (setq x 2)
3.   (while (> n 1)
4.     (if (zerop (rem n x))
5.       (setq n (/ n x)
6.             l (if (setq old (assoc x l))
7.                 (subst (list x (1+ (cadr old))) old l)
8.                 (cons (list x 1) l)
9.                 )
10.             )
11.       (if (> (setq x (if (= x 2) 3 (+ 2 x))) (sqrt n)) (setq x n))
12.       )
13.     )
14.   (reverse l)
15.   )

Code: [Select]

_$ (prime_factors 19683) ->((3 9))
_$ (prime_factors 19487171)->((11 7))
_$ (prime_factors 48828125)->((5 11))
_$ (prime_factors 256)->((2 8))
_$ (prime_factors 144)>((2 4) (3 2))

[Lee Mac]

Code - Auto/Visual Lisp: [Select]

1. (defun primefactors ( n / f i p l )
2.     (setq f 1
3.           i n
4.     )
5.     (while (< f i)
6.         (setq p (lowestprimedivisor n)
7.               f (* f p)
8.               n (/ i f)
9.               l (assoc++ p l)
10.         )
11.     )
12.     l
13. )
14.  
15. (defun assoc++ ( x l / a )
16.     (if (setq a (assoc x l))
17.         (subst (list x (1+ (cadr a))) a l)
18.         (cons  (list x 1) l)
19.     )
20. )
21.  
22. (defun lowestprimedivisor ( n / i r c )
23.     (if (= 0 (rem n 2))
24.         2
25.         (progn
26.             (setq i 1
27.                   r n
28.                   c (fix (1+ (sqrt n)))
29.             )
30.             (while (< (setq i (+ 2 i)) c)
31.                 (if (= 0 (rem n i))
32.                     (setq r i i c)
33.                 )
34.             )
35.             r
36.         )
37.     )
38. )
39.  

Code: [Select]

_$ (primefactors 19683)
((3 9))
_$ (primefactors 19487171)
((11 7))
_$ (primefactors 48828125)
((5 11))
_$ (primefactors 256)
((2 8))
_$ (primefactors 144)
((3 2) (2 4))

[Lee Mac]

Nice code Stefan (as always) 

[VovKa]

this one does not work with 144

Code: [Select]

(defun test (n / a b c)
  (setq a (1+ (fix (/ (log n) (log 2)))))
  (while (setq a (1- a)
       c (expt n (/ 1. a))
       b (fix (+ c 0.5))
       c (not (equal (/ c b) 1 1e-8))
)
  )
  (list b a)
)posting just to demonstrate another approach

[Lee Mac]

An optimisation of Stefan's code:

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors2 ( n / d l x )
2.     (setq x 2)
3.     (while (< 1 n)
4.         (setq d 0)
5.         (while (zerop (rem n x))
6.             (setq d (1+ d)
7.                   n (/ n x)
8.             )
9.         )
10.         (if (< 0 d)
11.             (setq l (cons (list x d) l))
12.         )
13.         (if (< 1 (sqrt n) (setq x (if (= x 2) 3 (+ 2 x))))
14.             (setq l (cons (list n 1) l)
15.                   n 0
16.             )
17.         )
18.     )
19.     (reverse l)
20. )

[Stefan]

Nice code Stefan (as always) 

Thank you very much Lee.

Looking at your code, I suggest to call lowestprimedivisor with 2 args, in which the second would be the last known divisor.
You don't need to check [again] lower than that, as they are already factorized.

[Stefan]

An optimisation of Stefan's code:

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors2 ( n / d l x )
2.     (setq x 2)
3.     (while (< 1 n)
4.         (setq d 0)
5.         (while (zerop (rem n x))
6.             (setq d (1+ d)
7.                   n (/ n x)
8.             )
9.         )
10.         (if (< 0 d)
11.             (setq l (cons (list x d) l))
12.         )
13.         (if (< 1 (sqrt n) (setq x (if (= x 2) 3 (+ 2 x))))
14.             (setq l (cons (list n 1) l)
15.                   n 0
16.             )
17.         )
18.     )
19.     (reverse l)
20. )

That make sense, since a multiple divisor  can be found in consecutive steps.
Anyway, I still looking for a better method to find the next divisor, since I think my method is highly inefficient.

[Lee Mac]

Anyway, I still looking for a better method to find the next divisor, since I think my method is highly inefficient.

The problem reduces to finding a sequence of primes... 

[chlh_jd]

When you provide a number as "6" to a function, its considered an integer.  If you provide a number as "6.0" its considered a real.  When LISP does math on two integers, the result is typically an integer; when one of the values is a real the result is a real.  Sometimes you need to force values from integers to reals in order to get desired results.

Thanks dgorsman , I there a way to solve the deviation of expt function ?

[chlh_jd]

For reasonable integers

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors (n / x l old)
2.   (setq x 2)
3.   (while (> n 1)
4.     (if (zerop (rem n x))
5.       (setq n (/ n x)
6.             l (if (setq old (assoc x l))
7.                 (subst (list x (1+ (cadr old))) old l)
8.                 (cons (list x 1) l)
9.                 )
10.             )
11.       (if (> (setq x (if (= x 2) 3 (+ 2 x))) (sqrt n)) (setq x n))
12.       )
13.     )
14.   (reverse l)
15.   )

Code: [Select]

_$ (prime_factors 19683) ->((3 9))
_$ (prime_factors 19487171)->((11 7))
_$ (prime_factors 48828125)->((5 11))
_$ (prime_factors 256)->((2 8))
_$ (prime_factors 144)>((2 4) (3 2))

Thanks Stefan , thank you very much .

Nice code Stefan (as always) 

1+

[chlh_jd]

Code - Auto/Visual Lisp: [Select]

1. (defun primefactors ( n / f i p l )
2.     (setq f 1
3.           i n
4.     )
5.     (while (< f i)
6.         (setq p (lowestprimedivisor n)
7.               f (* f p)
8.               n (/ i f)
9.               l (assoc++ p l)
10.         )
11.     )
12.     l
13. )
14.  
15. (defun assoc++ ( x l / a )
16.     (if (setq a (assoc x l))
17.         (subst (list x (1+ (cadr a))) a l)
18.         (cons  (list x 1) l)
19.     )
20. )
21.  
22. (defun lowestprimedivisor ( n / i r c )
23.     (if (= 0 (rem n 2))
24.         2
25.         (progn
26.             (setq i 1
27.                   r n
28.                   c (fix (1+ (sqrt n)))
29.             )
30.             (while (< (setq i (+ 2 i)) c)
31.                 (if (= 0 (rem n i))
32.                     (setq r i i c)
33.                 )
34.             )
35.             r
36.         )
37.     )
38. )
39.  

Code: [Select]

_$ (primefactors 19683)
((3 9))
_$ (primefactors 19487171)
((11 7))
_$ (primefactors 48828125)
((5 11))
_$ (primefactors 256)
((2 8))
_$ (primefactors 144)
((3 2) (2 4))

Nice code , Lee . Thank you very much .
This is the second time I saw this function 'Assoc++' is a wonderful application , (First in LM:give_change)