The number 1 cannot be divided by any prime, which would make it a non-match by (?=(xx+?)\2+$), so it exits the top-level loop (the one with * at the end). It will now loop back to the first step again, with 1 as the new number.
In this example, 81 will become the new number the next loop will go as follows: Now the regex can loop back to the first step this is what the final * does. In our example, with an input of 1296, this will loop through as follows: If it is still divisible by \2 at the beginning of each iteration of the loop, then this proves that each iteration divided the number by \2. The first time this test is done it is useless, but the next 3 times, it determines if the result of implicitly dividing by \2 is still divisible by \2. We have just divided by the number's smallest prime factor if the number is still divisible by that factor, it means the original number might be divisible by the fourth power of that factor. Now it loops back to the beginning of the inner loop, where it becomes apparent why there is a test for divisibility by the prime factor. This leaves the remaining unprocessed string at the end matching \4 in length.
This is done by capturing the result of subtraction (the current number minus \4), into the capture group \5, and then, outside the lookahead, matching a portion of the beginning of the current number corresponding to \5. Since this kind of regex can only "eat away" from the string (making it smaller) by leaving a result at the end of the string, we need to "move" the result of the division to the end of the string. While it is possible to explicitly divide the current number by a number contained in a capture group (which I only discovered four days after posting this answer), doing this would make for a slower and harder-to-understand regex, and it is not necessary, since a number's smallest factor larger than 1 will always match up with its largest factor smaller than itself (such that their product is equal to the number itself). Note that the division of the current number by \2 is implicit. In effect this divides the number by its smallest prime factor, \2 for example, 1296 will initially be captured as \4 = 1296/2 = 648. Next inside this inner loop, it uses the greedy capture group \4 to capture the number's largest factor smaller than itself: (?=(x+)(\4+)$). The first time through this loop, this test is useless, but its purpose will become apparent later.
Then, at the beginning of a loop that is repeated 4 times, it tests to see if the current number is divisible by \2, with (?=\2+$). For example, with 1296 (6^4) it will initially capture \2 = 2. As such, this factor is guaranteed to be prime. Zero is also matched.įirst it uses a lazy capture group \2 to capture the number's smallest factor larger than 1. A final quotient of 1 indicates that the original value was indeed a fourth power this completes the match. As such the quotient at each step is always a fourth power, iff the original value was a fourth power. It works by repeatedly dividing away the smallest fourth power of a prime that the current value is divisible by. I need to thank deadcode for bumping it back up to the top. This is, in my opinion, one of the most interesting problems on the site.