^((?=(x(x+?))\2*$)(?^=x\3*$)(?=(x+)(\4+$))\5(?!\2*$)){2,}x$
Try it on replit.com! - sequence 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.
decision-problem harnesses:
Try it online! - ECMAScript 2018
Try it online! - Python (import regex)
Try it online! - .NET
Regex (ECMAScript 2018 or better / Java), 66 bytes
^((?=(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.
decision-problem harnesses:
Try it online! - ECMAScript 2018
Try it online! - Java
Try it online! - Python (import regex)
Try it online! - .NET
Regex (ECMAScript), 86 89 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! - sequence harness (RegexMathEngine, ECMAScript mode)
decision-problem 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), 97 93 92 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! - sequence harness (RegexMathEngine, ECMAScript mode)
decision-problem 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
