+- 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).
RE: Carmichael Numbers (Updated 2/21/2016) - C.Ret - 04-24-2020 06:18 PM
Hello,
I just compose a code for testing if a number n is a Carmichael Number. By inadvertence, I used exactly the same ifactors instruction. By using it, we don’t need to test if n is prime. The length of the vector produce by ifactors is exactly 2 for any prime number. A prime number always decomposes in the only one factor which is exactly itself.
For example, ifactor(13) returns [ 13 1 ]
This lead to a shorter code :
Code:
EXPORT IsCARMI(n)
BEGIN
LOCAL FC,k,l,r;
FC:=ifactors(n); l:=length(FC); r:=(l>2);
FOR k FROM 1 TO l STEP 2 DO r:= r AND FC(k+1)==1 AND irem(n-1,FC(k)-1)==0; END;
RETURN r;
END;ISCARMI(561) returns 1
ISCARMI(2588653081) returns 1
ISCARMI(4991) returns 0 (is prime)
ISCARMI(1.23) returns 0 (not integer)
ISCARMI(-561) returns 0 (negative integer)