This is, in my opinion, one of the most interesting problems on the site. I need to thank deadcode for bumping it back up to the top.
39 bytes, without any conditionals or assertions... sort of. The alternations, as they're being used (
^|), are a type of conditional in a way, to select between "first iteration," and "not first iteration."
This regex can be seen to work here: http://regex101.com/r/qA5pK3/1
Both PCRE and Python interpret the regex correctly, and it has also been tested in Perl up to n = 128, including n4-1, and n4+1.
The general technique is the same as in the other solutions already posted: define a self-referencing expression which on each subsequent iteration matches a length equal to the next term of the forward difference function, Df, with an unlimited quantifier (
*). A formal definition of the forward difference function:
Additionally, higher order difference functions may also be defined:
Or, more generally:
The forward difference function has a lot of interesting properties; it is to sequences what the derivative is to continuous functions. For example, Df of an nth order polynomial will always be an n-1th order polynomial, and for any i, if Dfi = Dfi+1, then the function f is exponential, in much the same way that the derivative of ex is equal to itself. The simplest discrete function for which f = Df is 2n.
f(n) = n2
Before we examine the above solution, let's start with something a bit easier: a regex which matches strings whose lengths are a perfect square. Examining the forward difference function:
Meaning, the first iteration should match a string of length 1, the second a string of length 3, the third a string of length 5, etc., and in general, each iteration should match a string two longer than the previous. The corresponding regex follows almost directly from this statement:
It can be seen that the first iteration will match only one
x, and each subsequent iteration will match a string two longer than the previous, exactly as specified. This also implies an amazingly short perfect square test in perl:
This regex can be further generalized to match any n-gonal length:
f(n) = n3
Moving on to n3, once again examining the forward difference function:
It might not be immediately apparent how to implement this, so we examine the second difference function as well:
So, the forwards difference function does not increase by a constant, but rather a linear value. It's nice that the initial ('-1th') value of Df2 is zero, which saves an initialization on the second iteration. The resulting regex is the following:
The first iteration will match 1, as before, the second will match a string 6 longer (7), the third will match a string 12 longer (19), etc.
f(n) = n4
The forward difference function for n4:
The second forward difference function:
The third forward difference function:
Now that's ugly. The initial values for Df2 and Df3 are both non-zero, 2 and 12 respectively, which will need to be accounted for. You've probably figured out by now that the regex will follow this pattern:
Because the Df3 must match a length of 12 on the second iteration, a is necessarily 12. But because it increases by 24 each term, the next deeper nesting must use its previous value twice, implying b = 2. The final thing to do is initialize the Df2. Because Df2 influences Df directly, which is ultimately what we want to match, its value can be initialized by inserting the appropriate atom directly into the regex, in this case
(^|xx). The final regex then becomes:
A fifth order polynomial can be matched in with the following regex:
f(n) = n5 is a fairly easy excercise, as the initial values for both the second and fourth forward difference functions are zero:
For six order polynomials:
For seventh order polynomials:
Note that not all polynomials can be matched in exactly this way, if any of the necessary coefficients are non-integer. For example, n6 requires that a = 60, b = 8, and c = 3/2. This can be worked around, in this instance:
Here I've changed b to 6, and c to 2, which have the same product as the above stated values. It's important that the product doesn't change, as a·b·c·… controls the constant difference function, which for a sixth order polynomial is Df6. There are two initialization atoms present: one to initialize Df to 2, as with n4, and the other to initialize the fifth difference function to 360, while at the same time adding in the missing two from b.