Tuesday, February 16, 2016

HP Prime: Carmichael Numbers (Update 2/21/2016)

HP Prime:  Carmichael Numbers

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.  That is, √n is not an integer.
3. For each prime factor p dividing n (not 1 or n), the following is true: (p-1) divides (n-1) evenly (without fraction). 


Update:  I was mistaken about the definition of squarefree.  A squarefree integer are integers that are not divisible by perfect squares (I thought the number was square free itself).  I am to update ISCARMICHAEL this week.  Apologizes and many appreciations to Hank for pointing this out to me.  -  EWS 

HP Prime Program ISCARMICHAEL  (Updated 2/21/2016)

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;

Notes:
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.

Examples:

ISCARMICHAEL(561) returns 1.  561 is a Carmichael number.  The prime factors of 561 are 3, 11, 17.

ISCARMICHAEL(778) returns 0, hence 778 is not a Carmichael number.  The prime factors of 778 are 2 and 389.

Source:

Crandall, Richard and Pomerance, Carl.  Prime Numbers: A Computational Perspective  2nd Ed.  Springer: New York.  2005

Eddie



This blog is property of Edward Shore.  2016