 Carmichael Numbers (Updated 2/21/2016) - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: HP Prime Software Library (/forum-15.html) +--- Thread: Carmichael Numbers (Updated 2/21/2016) (/thread-5691.html) Carmichael Numbers (Updated 2/21/2016) - Eddie W. Shore - 02-16-2016 02:05 PM Blog entry: http://edspi31415.blogspot.com/2016/02/hp-prime-carmichael-numbers.html Program (Updated 2/21/2016: I was mistaken on the definition of squarefree integers, the program is now corrected.) Code: ```EXPORT ISCARMICHAEL(n) BEGIN // EWS 2016-02-21 // Thanks: Hank LOCAL l1,s,flag,k; LOCAL vect; flag:=0; // composite test IF isprime(n)==1 THEN RETURN 0; KILL; END; // setup vect:=ifactors(n); l1:=SIZE(vect); s:=l1(1); // square-free number test FOR k FROM 2 TO s STEP 2 DO IF vect(k)>1 THEN flag:=1; BREAK; END; END; // factor test FOR k FROM 1 TO s STEP 2 DO IF FP((n-1)/(vect(k)-1))≠0 THEN flag:=1; BREAK; END; END; // final result IF flag==0 THEN RETURN 1; ELSE RETURN 0; END; END;``` The commands isprime and ifactors are generated from the CAS-Integer (Options 6 then 1 for isprime; option 3 for ifactors) submenu. However, I think in order for this program to work properly, the “CAS.” must be deleted and the command should be in all-lowercase. Introduction An integer n is a Carmichael number (1910) when the following holds: a^n ≡ a mod n (or for a>0 and n>0) a^n – integer(a^n/n) * n = a For all integers a. The program ISCARMICHAEL tests whether an integer n qualifies as a Carmichael number based on the Korselt’s Criterion: 1. n is a positive, composite integer. That is, n can be factored into a multiplication of prime numbers. 2. n is square-free. 3. For each prime factor p dividing n (not 1 or n), the following is true: (p-1) divides (n-1) evenly (without fraction).