Challenge 21: Carmichael Numbers

Once again, agent Charles Carmichael ¹ has been captured by the rogue enemy spies. Fortunately, he has left clues about his location with the Nerd Herd at the Buy More ². Being the geek that he is though, agent Carmichael has encoded his information as a series of numbers.

Your mission as a top secret data analyzer is to crack the code! Being the clever and diligent programmer that you are, you have figured out that the stream of integers contains a particular type of numbers: Carmichael numbers!

These are composite numbers (non-primes) that pass the following prime test for all numbers smaller than n:

a^n mod n = a   # Fermat test

That is let a be a random number between 2 and n - 1, where n is the number we are testing. n is probably a prime if it passes the Fermat primality test several times. As noted, however, there are some composite (non-primes) that also pass this test for all numbers less than n. These numbers, of course, are called Carmichael numbers and your job is to help agent Walker ³ filter the list of numbers and determine which ones are Carmichael numbers.

Input¶

The input will consist of a series of lines, each containing a small positive number n where (2 < n < 65,000). You should read until the end-of-file.

Example Input¶

1729
17
561
1109
431

Output¶

For each number in the input, print whether it is a Carmichael number or not as shown in the sample output.

Example Output¶

The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

Submission¶

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge21               # Create and checkout challenge21 branch

$ $EDITOR challenge21/program.py            # Edit your code

$ git add challenge21/program.py            # Stage your changes
$ git commit -m "challenge21: done"         # Commit your changes

$ git push -u origin challenge21            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge21 program.py ...
  Result Success
    Time 0.06
   Score 6.00 / 6.00

$ curl -F source=@challenge21/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge21
{"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}