In number theory, a Carmichael number is a composite number n which satisfies the modular arithmetic congruence relation:
b^(n-1) ≡ 1 mod n
for all integers b which are relatively prime to n.
//https://en.wikipedia.org/wiki/Carmichael_number
(letn (fattori (factor x)
unici (unique fattori))
(transpose (list unici (count unici fattori)))))
;(map list unici (count unici fattori))))
(fattorizza 45)
;-> ((3 2) (5 1))
(fattorizza 561)
;-> ((3 1) (11 1) (17 1))
(define (carmichael? n)
(local (out fattori)
(setq out true)
(cond ((or (= n 1) (even? n) (= 1 (length (factor n)))) (setq out nil))
(true
(setq fattori (fattorizza n))
(dolist (f fattori (= out nil))
(if (> (f 1) 1) (setq out nil))
(if (!= (% (- n 1) (- (f 0) 1)) 0) (setq out nil))
)
)
)
out
)
)
(define (carmichael n)
(let (out '())
(for (i 3 n 2)
(if (carmichael? i) (push i out -1))
)
out
)
)
(carmichael 1000000)
;-> (561 1105 1729 2465 2821 6601 8911 10585 15841 29341 41041 46657 52633 62745 63973
;-> 75361 101101 115921 126217 162401 172081 188461 252601 278545 294409 314821
:-> 334153 340561 399001 410041 449065 488881 512461 530881 552721 656601 658801
;-> 670033 748657 825265 838201 852841 997633)
(time (carmichael 1000000))
;-> 2043.545
(define (carmichael n)
(filter carmichael? (sequence 3 n 2)))
(time (carmichael 1000000))
;-> 3510.422