Return to Answer

I'll assume that you have a basic understanding of balancing groups, but in short, capturing groups in .NET are stacks (so each time you reuse the capturing group the new capture is pushed on top) and (?<-x>...) pops a capture from stack x. That's very helpful for counting things.

I'll assume that you have a basic understanding of balancing groups, but in short, capturing groups in .NET are stacks (so each time you reuse the capturing group the new capture is pushed on top) and (?<-x>...) pops a capture from stack x. That's very helpful for counting things.

Uses the same I/O as n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ 's answer, i.e. unary input and it matches a substring of the length of the result.

Uses the same I/O as n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ 's answer, i.e. unary input and it matches a substring of the length of the result.

Explanation

I'll assume that you have a basic understanding of balancing groups, but in short, capturing groups in .NET are stacks (so each time you reuse the capturing group the new capture is pushed on top) and (?<-x>...) pops a capture from stack x. That's very helpful for counting things.

^ # Only look at matches from the beginning of the input. (?= # First, we'll compute the number of composites less than # or equal to the input in group 2. This is done in a # lookahead so that we don't actually advance the regex # engine's position in the string. ( # Iterate through the input, one character at a time. (?=(..+)\2+$)? # Try to match the remainder of the input as a # composite number. If so the (..+) will add one # one capture onto stack 2. Otherwise, this lookahead # is simply skipped. . )+ ) (?= # It turns out to be more convienient to work with n minus # the number of composites less than or equal to n, and to # have that a single backreference instead of the depth of # a stack. (?<-2>.)* # Match one character for each composite we found. (.+) # Capture the remainder of the input in group 3. ) (?= # Now we compute the totient function. The basic idea is # similar to how we computed the number of composites, # but there are a few differences. # a) Of course the regex is different. However, this one # is more easily expressed as a negative lookahead (i.e. # check that the values don't share a factor), so this # won't leave a capture on the corresponding stack. We # fix this by wrapping the lookahead itself in a group # and making the entire group optional. # b) We only want to search up the number of composites, # not up to the input. We do this by asserting that we # can still match our backreference \3 from earlier. ( # Iterate through the input, one character at a time. ((?! # Try not to match a number that shares a factor with # the number of composites, and if so push a capture # onto stack 5. (..+)\6* # Look for a factor that's at least 2... (?<=^\6+) # Make sure we can reach back to the input with that # factor... \3$ # ...and that we're exactly at the end of the number # of composites. ))? . )* \3 # Match group 3 again to make sure that we didn't look # further than the number of composites. ) (?<-5>.)* # Finally, match one character for each coprime number we # found in the last lookahead.