Golf the pseudoprimes!

Question

Introduction / Background

In a recent discussion in the crypto chat I was challenged to discuss / help with the Fermat primality test and Carmichael numbers. This test is based on the premise that a^(p-1) mod p==1 will always hold for primes p, but not always for composites. Now a carmichael number is essentially the Fermat's test worst enemy: A number for which you have to pick a to be not co-prime with p to get a^(p-1) mod p!=1. Now if a is not co-prime, you essentially found a non-trivial factor of p and as we all know factoring can be quite hard. Especially if all factors are sufficiently large. You may now realize why the Fermat test isn't used in practice as often (well there are better algorithms), it's because there are numbers for which you as a defender (in security terms) would have to do a similar amount of work as an attacker (namely factor the number).

So now that we know why these numbers are somewhat fascinating, we're gonna generate them in the shortest way possible, so we can just memorize the generating code if we ever need any!

Carmichael numbers are also known as A002997 on OEIS.
There is a related challenge already, but entries from there are not competitive here because they are optimized for speed as opposed to size. The same argument holds for the inverse direction, entries here are likely to make trade-offs against speed in favor of size.

Specification

Input

This is a standard sequence challenge, so you take a positive or non-negative integer n as input. n may be 0- or 1-indexed as you prefer (please indicate).

Output

Your output will either be the n-th carmichael number or the first n carmichael numbers, as you prefer (please indicate).

Specification

An integer x is a Carmichael number if and only if x is composite and for all integers y with gcd(x,y)=1, it holds that y^(x-1) mod x==1.

Who wins?

This is code-golf, so the shortest code in byte wins!
Standard IO and loophole rules apply.

Test Cases

The first few carmichael numbers are:

 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

Answer 1

Mathematica, 71 bytes

(t=s=1;While[t<=#,If[++s~Mod~CarmichaelLambda@s==1&&!PrimeQ@s,t++]];s)&  

Try it online!

50->1461241 Try it online!

Answer 2

Python 2, 92 bytes

f=lambda j,n=1:j and f(j-([(k/n)**~-n%n for k in range(n*n)if k/n*k%n==1]<[1]*~-n),n+1)or~-n

Try it online!

1-indexed and slow as molasses.

In the list comprehension, I use Dennis’s method for generating all integers coprime to n (n’s totatives), and then I compute x**~-n%n for all of them. Let’s call this list L.

To detect a Carmichael number, I compare this list lexicographically to a list consisting of n-1 ones. Why does this work?

Each element of L is a positive integer: (k/n) is coprime to n, so (k/n)**~-n also is, so (k/n)**~-n%n > 0. Thus, the only possible values of L that are lexicographically less than [1]*(n-1) are the ones consisting entirely of less than n-1 ones. (L can’t contain more than n-1 values, as n can’t have more than n-1 totatives! So comparisons like [1,1,1,1,3] < [1,1,1,1] are out.)

Checking that there are less than n-1 entries in L ensures that n is composite. (Having n-1 totatives is an equivalent condition to primality.) And then, the condition for being a Carmichael number is exactly that every element of L equals 1. So this lexicographic comparison detects exactly the Ls we’re interested in.

Mr. Xcoder saved a byte by switching to recursive lambda form: j counts down every time we hit a Carmichael number, and n counts up every time we recurse. So once j hits zero, n-1 equals the original_value_of_j’th Carmichael number.

Answer 3

Jelly,  12  11 bytes

-1 byte thanks to miles & Mr. Xcoder (use of Carmichael function atom & a golf thereof)

%Æc’=ÆP
⁹Ç#

A monadic link taking n and returning a list of the first n Carmichael numbers.

Try it online!

How?

Much like the previous (below) except that there is a built-in for the Carmichael function - which yields the smallest power such that the input raised to that power is congruent to one modulo that power for all integers co-prime to that integer. Thus we may exclude the false-positives (primes) in less bytes and have faster code!

%Æc’⁼ÆP - isCarmichael: number, n (any integer)
 Æc     - Carmicael function of n
%       - n modulo that
   ’    - decremented (0 for Carmichael numbers and primes)
     ÆP - is n prime? (1 for primes 0 otherwise)
    ⁼   - equal?

⁹Ç# - Main link: number, n
  # - count up finding the first n values satisfying:
 Ç  - ...condition: call the last link as a monad
⁹   - ...starting with a value of: literal 256

---

Previous 12 bytes:

Ṗ*%⁼Ṗ_ÆP
⁹Ç#

Try it online! (Yeah, it times out for n=3).

How?

A number, c, is a Carmichael number if it is composite and it is true that any integer, x, raised to c is congruent to x modulo c.

We only need to check this for positive x up to x=c itself.

Note also that at x=c the check is whether x raised to the power of x is congruent to x modulo x, which is true - so we don't need to check this (this makes for shorter code).

Ṗ*%⁼Ṗ_ÆP - Link 1, isCarmichaelNumber: integer c (greater than 1)
Ṗ        - pop c (uses the implicit range(c)) = [1, 2, 3, ..., c-1]
 *       - raise to the power of c (vectorises) = [1^c, 2^c, 3^c, ..., (c-1)^c]
  %      - modulo by c (vectorises) = [1^c%c, 2^c%c, 3^c%c, ..., (c-1)^c%c]
    Ṗ    - pop c = [1, 2, 3, ..., c-1]
   ⁼     - equal? (non-vectorising) = 1 if so, 0 if not
      ÆP - isPrime?(c) = 1 if so, 0 if not
     _   - subtract = 1 if Carmichael 0 if not
         -     (Note the caveat that c must be an integer greater than 1, this is because
         -      popping 1 yields [] thus the equality check will hold; same for 0,-1,...)

⁹Ç# - Main link: number, n
  # - count up finding the first n values satisfying:
 Ç  - ...condition: call the last link as a monad
⁹   - ...starting with a value of: literal 256

Answer 4

ECMAScript Regex, 86 89 bytes

Warning: Do not read this if you don't want some unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex: see this earlier post for a list of consecutively spoiler-tagged recommended problems to solve one by one.

^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$))((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$

Try it online!

# Match Carmichael numbers in the domain ^x*$ using Korselt's criterion
# N = input number (initial value of tail)
^
(?!
    # Iterate through factors \1, with \2 = \1-1, for which \2 does not divide into N-1
    (x(x+))
    (?!\2*$)           # Assert N-1 is not divisible by \2
    \1*(?=\1$)         # Assert N is divisible by \1; tail = \1
    # If the factor \1, which already passed the aboved tests, is prime, then fail the
    # outside negative lookahead, because N is not a Carmichael number.
    (?!(xx+)\3+$)
)
# Assert that N has at least 2 unique prime factors, and that all of its prime factors
# are of exactly single multiplicity (i.e. that N is square-free).
(
    (?=(xx+?)\5*$)     # \5 = smallest prime factor of tail
    (?=(x+)(\6+$))     # \6 = tail / \5 (implicitly); \7 = tool to make tail = \6
    \7                 # tail = \6
    (?!\5*$)           # Assert that tail is no longer divisible by \5, i.e. that that
                       # prime factor was of exactly single multiplicity.
){2,}
x$

The main magic of this regex is in the part that asserts that all of the prime factors of N are of exactly single multiplicity. It is the same trick as used by my Match strings whose length is a fourth power and Find the Smoothest Number regexes: repeated implicit division by the smallest prime factor.

It's also possible to directly test that N has no perfect-square factors (i.e., that N is square-free). This uses a variant of the multiplication algorithm briefly described in a paragraph of my abundant numbers regex post to test if a number is a perfect square. This is a spoiler. So do not read any further if you don't want some advanced unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in the list of consecutively spoiler-tagged recommended problems in this earlier post, and trying to come up with the mathematical insights independently.

Using that algorithm on this problem does not provide any benefit, however. It results in a slower regex, with a larger size of 97 bytes. Without the prime multiplicity test (which in one loop asserts both that there are at least 2 prime factors and that they are each of single multiplicity), we have to separately assert that N is composite.

^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((xx+)\5*(?=\5$))?(x(x*))(?=(\6*)\7+$)\6*$\8)(xx+)\9+$

Try it online!

 ^
 (?!
     # Iterate through factors \1, with \2 = \1-1, for which \2 does not divide into N-1
     (x(x+))
     (?!\2*$)           # Assert N-1 is not divisible by \2
     \1*(?=\1$)         # Assert N is divisible by \1; tail = \1
     # If the factor \1, which already passed the aboved tests, is prime, then fail the
     # outside negative lookahead, because N is not a Carmichael number.
     (?!(xx+)\3+$)
 |
 # Assert that N is square-free, i.e. has no divisor >1 that is a perfect square.
     ((xx+)\5*(?=\5$))?  # cycle tail through all of the divisors of N, including N itself
     # Match iff tail is a perfect square
     (x(x*))             # \6 = potential square root; \7 = \6 - 1
     (?=
         (\6*)\7+$       # iff \6 * \6 == our number, then the first match here must result in \8 == 0
     )
     \6*$\8              # test for divisibility by \6 and for \8 == 0 simultaneously
 )
 (xx+)\9+$               # Assert that N is composite
 

Answer 5

J, 72 59 51 bytes

1{(((0>.-)0&p:*~:@q:-:0=q:|&<:])([,(+*)~)])/^:_@,&2

Try it online!

Answer 6

Retina, 94 bytes

\d*$
x
"$+"}/^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$/^+`$
x
x

Try it online! 1-indexed. Not fast, so will time out for n>5 on TIO. Explanation:

\d*$
x

Increment the current value. On the first pass, this also deletes n from the output buffer (but $+ can still access it).

/^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$/

Test whether the current value is a Carmichael number. This uses @Deadcode's alternative algorithm, as the square detection is shorter when written using .NET/Perl/PCRE regex.

^+`

Repeat until the current value is a Carmichael number.

$
x

Increment the current value.

"$+"}

Repeat the initial increment and above loop n times.

x

Convert the result to decimal.

Answer 7

Haskell, 95 bytes

s=filter
c n=s(\x->let l=s((1==).gcd x)f;f=[1..x-1]in l/=f&&all(\y->y^(x-1)`mod`x==1)l)[1..]!!n

Try it online!

Degolfed:

-- function to filter out Carmichael numbers
filterFunction x = 
    let coprimes = filter ((1 ==) . gcd x) lesserNumbers
        lesserNumbers = [1 .. x - 1]
    in
        -- the number x is Carmichael if it is not prime
        lesserNumbers /= coprimes && 
            -- and all of its coprimes satisfy the equation
            all (\y -> y ^ (x - 1) `mod` x == 1) coprimes

-- get n'th Carmichael number (zero-based)
c n = filter filterFunction [1..] !! n