## Carmichael numbers

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

### Carmichael numbers

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

Code: Select all

(define (fattorizza x)
(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