276 205 201 193 189 177 174 bytes
Comparing the multiplicities (exponents) of different prime factors is an interesting problem for solving with ECMAScript regex – the lack of backreferences that persist through iterations of a loop makes it a challenge to count anything. Even if counting the numerical trait in question is possible, often a more indirect approach makes for better golf.
As with my other ECMA regex posts, I'll give a spoiler warning: I highly recommend learning how to solve unary mathematical problems in ECMAScript regex. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. See this earlier post for a list of consecutively spoiler-tagged recommended problems to solve one by one.
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 ECMAScript regex as outlined in that post linked above.
The main payload from a regex I previously developed turned out to be very applicable to this challenge. That is the regex that finds the prime(s) of highest multiplicity. My first solution for that was very long, and I later golfed it way down in stages, first rewriting it to use molecular lookahead, and then porting it back to plain ECMAScript using an advanced technique to work around the lack of molecular lookahead, and subsequently golfing it down to be much smaller than the original plain ECMAScript solution.
The part from that regex that applies to this problem is the first step, which finds Q, the smallest factor of N that shares all of its prime factors. Once we have this number, all we have to do to show that N is a "constant-exponent number" is divide N by Q until we can't any longer; if the result is 1, all primes are of equal multiplicity.
After submitting an answer using my previously developed algorithm for finding Q, I realized that it could be calculated in an entirely different way: Find the largest square-free factor of N (using the same algorithm as my Carmichael number regex). As it turns out, this poses no difficulty at all in terms of stepping around the lack of molecular lookahead and variable-length lookbehind (no need to pull in the advanced technique previously used), and is 64 bytes shorter! [Note, at the time, molecular lookahead still offered a slight benefit, but thanks to later golfs, it no longer does at all.] Additionally it eliminates the complexity of treating square-free N and prime N as different special cases, dropping another 7 bytes from this solution.
(There still remain other problems that require the advanced technique formerly used here to golf down the calculation of Q, but currently none of them are represented by my PPCG posts.)
I put the multiplicity test before the consecutive-primes test because the latter is much slower; putting tests that can fail more quickly first makes the regex faster for uniformly distributed input. It's also better golf to put it first, because it uses more backreferences (which would cost more if they were double-digit). [The multiplicity test is now split in two for golf, with the consecutive-primes test sandwiched inside.]
I was able to drop 4 bytes from this regex (193 → 189) using a trick found by Grimmy that can futher shorten the form of division in which the assertion that \$dividend-quotient\$ is divisible by \$divisor-1\$ can be skipped. (Skipping this assertion was already saving 4 bytes, so now it's saving 8 bytes.) This algorithm (in both its 4 byte longer form and the currently used one) is guaranteed to match the correct quotient when at least one of these constraints is met (along with satisfying the assertion that \$dividend\$ is divisible by \$divisor\$):
- \$divisor^2+2(divisor)+1 < 4(dividend)\$
- \$quotient=1\$ or equivalently \$divisor=dividend\$
- \$divisor\$ is a prime power
- One of the cases in which this must be true is when \$dividend\$ is semi-prime and neither of the two other conditions are met. It also must be true if \$dividend\$ is a prime power.
We're actually not guaranteed in this context that any of those constraints will be met. Most notably, we're not even asserting that \$quotient\$ (which will become the next \$dividend\$) is still divisible by \$divisor\$ after each iteration of the loop. But an additional fact comes to the rescue: if the division algorithm matches an incorrect quotient (which it doesn't always do even when none of the above constraints are met), the incorrect answer is guaranteed to be less than \$divisor\$ but greater than \$1\$.
So if this happens when repeatedly dividing N by Q, the loop will terminate, and the final result will not be 1, thus guaranteeing no false positives. If N is actually a constant-exponent number, the correct quotient will always be greater than or equal to Q, so this doesn't cause any false negatives either.
- -3 bytes by dividing by N just like any other largest square-free factor, instead of treating N being square-free as a special case (inspired by H.PWiz but goes farther then what he did, saving 1 extra byte – he made it so the regex attempted to divide by 0 in the case that Q=N, and then asserted that the end result of the repeated division was Q rather than 1)
- -6 bytes by changing
(?!B)A (some of this is from multiple uses of backrefs changing from double to single digit, with less of the opposite occurring) – thanks to H.PWiz
- -2 bytes by capturing the smallest prime as \$\ge 2\$ instead of augmenting the non-composite test to be a full prime test – thanks to H.PWiz
- -2 bytes by removing an extraneous pair of parentheses – thanks to H.PWiz
- -2 bytes by changing an outermost
(|x*)\1*(?=\1\b), similarly to what I did in the alternate answer here; one of these bytes is from a backref changing from double to single digit
And the regex:
Try it online!
^ # tail = N = input number
# Assert that all of N's prime factors are of equal multiplicity. There are two stages
# to this, which we will call Step 1 and Step 2. For golf reasons, a negative assertion
# is inserted between them.
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N).
(|x*)\1*(?=\1\b) # cycle tail through all of the divisors of N, including N,
# from largest to smallest;
# \1 = the divisor, or zero if the divisor is N itself
# Assert that tail is square-free (its prime factors all have single multiplicity)
( # \2 = tail = the divisor
(?=(xx+?)\4*$) # \4 = smallest prime factor of tail
(?=(x+)(\5+$)) # \5 = tail / \4 (implicitly); \6 = tool to make tail = \5
\6 # tail = \5
(?!\4*$) # Assert that tail is no longer divisible by \4, i.e. that
# that prime factor was of exactly single multiplicity.
# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
( # \7 = a factor of N
( # \8 = a non-factor of N between \7 and \9
(xx+)(?=\9+$) # \9 = a factor of N smaller than \7 and greater than 1
(x+) # \10 = tool (with \11) to make tail = \9
(x+) # \11 = tool to make tail = \8
\7*(?=\7$) # tail = \7
# Assert that \7, \8, and \9 are all prime
(\11\10?)? # tail = either \7, \8, or \9
(xx+)\13+$ # Assert tail is not composite; no need to test against
# 0 and 1, because we captured \9 > 1
# Step 2: Require that the result of repeatedly dividing N by \2 is 1.
# In this division calculation \15 = N / \2, we can skip the test for N-\15 being
# divisible by \2-1. (Actually doing that test would make the regex 8 bytes larger.)
# The quotient matched by this abbreviated algorithm is guaranteed to be correct if
# the real quotient is 1 or is not less than the divisor, or if the divisor is a
# prime power. Our input here is not guaranteed to satisfy any of those constraints.
# But if none of those constraints are met, and the quotient matched by the algorithm
# is incorrect, the incorrect quotient is guaranteed to be less than the divisor and
# greater than 1. And once that happens, this loop will terminate, as the current
# value will no longer be divisible by our divisor \2.
( # \15 = tail / \2
(x*) # \16 = \15-1
(\15*$) # \17 = tool to make tail = \15
\17 # tail = \15
x$ # Require that the end result is 1
195 187 183 bytes
Obsoleted by no longer treating N being square-free as a special case (i.e. is now identical to the above).
Regex (ECMAScript 2018),
198 195 194 186 182 bytes
Obsoleted by no longer treating N being square-free as a special case and changing
(?!B)A (i.e. is now identical to the above).
x = Pn^mpart. I'm assuming you meant Pn is the n-th prime \$\endgroup\$