# Golf the pseudoprimes!

## 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 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 , 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


# 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!

• Mathematica is now on TiO, so if anyone is interested you can try it online! Commented Oct 6, 2017 at 20:31
• @Mr.Xcoder Hey!That's great! I added (my first) mathematica TIO Commented Oct 6, 2017 at 20:39

# 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.

# 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:
⁹   - ...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:
⁹   - ...starting with a value of: literal 256

• Also 12 bytes but computes the first 33 in under a minute by using the Carmichael atom. Commented Oct 7, 2017 at 2:04
• 11 bytes by using the built-in Carmichael function. Commented Oct 7, 2017 at 11:44
• @Mr.Xcoder I was going to suggest miles posted separately, then saw yours then saw your comment and delete. The dv may be because someone thinks it's too similar to miles' commented one rather than this one, but I think even that is an odd reason since there is no reason to think that you did not find the same thing independently (I know I've done that kind of thing many times). I'll post your 11 if you want, but am of the opinion you or miles should take some credit. Commented Oct 7, 2017 at 12:38
• @miles too ...^ Commented Oct 7, 2017 at 12:39
• @JonathanAllan Just post it yourself. Mention miles' and my contribution, and I don't think miles minds either :-) (BTW I didn't even see miles' comment :-/ before posting my answer) Commented Oct 7, 2017 at 12:40

# RegexMathEngine (ECMAScript+(?^=)), 59 bytes

^((?=(x(x+?))\2*$)(?^=x\3*$)(?=(x+)(\4+$))\5(?!\2*$)){2,}x$ Try it on replit.com! - harness (RegexMathEngine) A regex takes a number as input in unary, as a string of x characters whose length represents the number. Its output is a match iff the number is a Carmichael number. This is launched in RegexMathEngine's sequence mode to satisfy the challenge's specifications, outputting the first n Carmichael numbers, where n can be given either as a command-line argument or through standard input. Korselt's criterion is used to identify Carmichael numbers. ^ # tail = N = input number # Assert that N has at least 2 unique prime factors, and that each of its prime # factors P are of exactly single multiplicity (i.e. that N is square-free), and # for each, P-1 divides N-1. ( (?=(x(x+?))\2*$)   # \2 = smallest prime factor of tail; \3 = \2-1
(?^=x\3*$) # Lookinto – Assert \3 divides N-1 (?=(x+)(\4+$))     # \4 = tail / \2 (implicitly); \5 = tool to make tail = \4
\5                 # tail = \4
(?!\2*$) # Assert that tail is no longer divisible by \2, i.e. that # that prime factor was of exactly single multiplicity. ){2,} # Iterate the above at least 2 times, with no maximum x$                     # Assert tail == 1


# Regex (ECMAScript 2018 or better), 59 bytes

^((?=(x(x+?))\2*$)(?=(x+)(\4+$)(?<=^\3*x))\5(?!\2*$)){2,}x$


A port of the lookinto version, to variable-length lookbehind.

harnesses:
Try it online! - ECMAScript 2018
Try it online! - Python (import regex)
Try it online! - .NET

^((?=(x(x+?))\2*$)(?<=(?=x\3*$)^.*)(?=(x+)(\4+$))\5(?!\2*$)){2,}x$ Java's lookbehind is restricted, but is able to do a simple return to start as is done here. harnesses: Try it online! - ECMAScript 2018 Try it online! - Java Try it online! - Python (import regex) Try it online! - .NET # Regex (ECMAScript), 8689 85 bytes -4 bytes by changing (?=A)(?!B) to (?!B)A; on some regex engines this results in a slowdown, but RegexMathEngine optimizes this so there is no difference in speed ^(?!(x(x+))(?!\2*$)\1*(?!(xx+)\3+$)\1$)((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$

Try it on replit.com! - harness (RegexMathEngine, ECMAScript mode)

harnesses (ECMAScript):
Try it online! (slow 85 byte version)
Try it online! (faster 89 byte version)

^                      # tail = N = input number
(?!                    # Negative lookahead – assert that neither of the
# following two alternatives can match:
# Cycle through factors \1, with \2 = \1-1, for which \2 does not divide N-1
(x(x+))            # \1 = conjectured factor of N; \2 = \1-1
(?!\2*$) # Assert N-1 is not divisible by \2 \1* # Assert N is divisible by \1 - works along with the # subsequent "\1$"; tail = \1
# If the factor \1, which already passed the above tests, is prime, then
# fail the outside negative lookahead, because N is not a Carmichael number.
(?!(xx+)\3+$) \1$
)
# 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.

# Regex (ECMAScript), 979392 90 bytes

-4 bytes by changing (?=A)(?!B) to (?!B)A; on some regex engines this results in a slowdown
-1 byte by using \b to streamline searching through all divisors of N
-2 bytes by excluding 1 as a divisor in the square test rather than the divisor search

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

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 explained in this post, adapted to asserting that $$\A^2=C\$$.

Using that algorithm on this problem does not provide any benefit, however. It results in a slower regex, with a larger size. 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.

Try it on replit.com! - harness (RegexMathEngine, ECMAScript mode)

harnesses (ECMAScript):
Try it online! (Slow 90 byte version)
Try it online! (Faster 94 byte version)

^                      # tail = N = input number
(?!                    # Negative lookahead – assert that neither of the
# following two alternatives can match:
# Cycle through factors \1, with \2 = \1-1, for which \2 does not divide N-1
(x(x+))            # \1 = conjectured factor of N; \2 = \1-1
(?!\2*$) # Assert N-1 is not divisible by \2 \1* # Assert N is divisible by \1 - works along with the # subsequent "\1$"; tail = \1
# If the factor \1, which already passed the above tests, is prime, then
# fail the outside negative lookahead, because N is not a Carmichael number.
(?!(xx+)\3+$) \1$
|
# Assert that N isn't square-free, i.e. has at least one divisor >1 that is
# a perfect square (outside the negative lookahead, assert the opposite).
(x*)\4*(?=\4\b)    # cycle tail through all divisors of N, including N itself

# Match iff tail is a perfect square
(x(x+))            # \5 = potential square root >= 2; \6 = \5 - 1
(?=
(\5*)\6+$# iff \5 * \5 == our number, then the first match here must result in \7 == 0 ) \5*$\7             # test for divisibility by \5 and for \7 == 0 simultaneously
)
(xx+)\8+$# Assert that N is composite  • (Strictly speaking, this is a decision-problem answer, but the challenge is a sequence challenge.) Presumably in a more powerful regex variant there would be a more direct test for square divisors available? – Neil Commented Jan 25, 2019 at 0:31 • @Neil You're right, I can golf it down by directly testing for square divisors. In ECMA, no extra features needed. But that will make it much slower (and I'll also want to hide it under a spoiler tag). I'll want to include both versions, I think. Commented Jan 25, 2019 at 0:34 • Yes, it's very annoying finding questions for regexes I've already written, that are not right right type of challenge. Should I delete my answer? Commented Jan 25, 2019 at 0:34 • @Neil Here you go. I implemented the algorithm using your idea. This is probably why I didn't think to pursue it on my own though; it actually results in a longer regex, because an is-composite test is needed. Commented Jan 25, 2019 at 2:44 • (Under site rules you should delete your answer, yes.) My idea was that using extra features of, say, Retina regexes, you could golf it down to ^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$, or maybe even less than 72 bytes.
– Neil
Commented Jan 25, 2019 at 9:20

# J, 7259 51 bytes

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


Try it online!

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)modx==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


# Retina, 9490 81 bytes

\d*$x "$+"}/^((?=(x(x+?))\2*$)(?=(x+)(\4+$)(?<=^\3*x))\5(?!\2*$)){2,}x$/^+$x x  Try it online! 1-indexed. Edit: Saved 4 13 bytes by porting @Deadcode's latest Carmichael test, which is also slightly less slow, but still times out for n>6 on TIO. crossed out 4 is still regular 4 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*$)(?=(x+)(\4+$)(?<=^\3*x))\5(?!\2*$)){2,}x$/  Test whether the current value is a Carmichael number. This uses @Deadcode's latest 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.

• You can save 4 bytes by using a golf I just applied to my regex. Commented Mar 23, 2021 at 0:48
• You should also be able to get another -1 byte by changing (^x|xx\5){2,} to (^x\B|xx\5)+, but it doesn't seem to be working. Any idea why? Commented Mar 23, 2021 at 0:55
• @Deadcode But then it will only solve n=1 on TIO... I guess that's technically still valid...
– Neil
Commented Mar 23, 2021 at 1:16
• @Deadcode (^x\B|xx\5)+ only enforces 2 xs but you need to enforce 4.
– Neil
Commented Mar 23, 2021 at 1:18
• Oh, I get it now. It's not quite what you said, because even (^x(?=xxx)|xx\5)+ wouldn't work. It can see 4 xs but still only loop for 1 iteration thus capturing only 1 x. Commented Mar 23, 2021 at 1:30