Regexercise: factorials

Question

_{This is an experimental new feature for StackOverlow: exercising your regex muscles by solving various classical problems. There is no one right answer, and in fact we should collect as many right answers as possible, as long as they offer educational value. All flavors accepted, but please document it clearly. As much as practical, provide testcases/snippets to demonstrate that the pattern "works".}

How can we find if a number x is a factorial using regex?

Bonus: if the pattern can determine that x = n!, can it also find n?

Answer 1

With .NET balancing groups, in C# (see also on ideone.com):

var r = new Regex(@"(?xn) 

^(
   (
     ( ^.
     | (?=  (?<temp-n> .)+ )
       (?<= (?<fact>  .+)  )
       (?<n-temp> \k<fact> )+?
       (?(temp) (?!))
     )
     (?<n>)
   )+
 )$

");

for (int x = 0; x < 6000; x++) {
   Match m = r.Match("".PadLeft(x));
   if (m.Success) {
      Console.WriteLine("{0,4} = {1}! ", x, m.Groups["n"].Captures.Count);
   }
}

Note:

The version of .NET used by ideone.com seems to have a bug in the balancing groups that made the reluctant repetition +? necessary in the above snippet. In newer versions, a simple greedy + may suffice. See also: Backtracking a balancing group in a greedy repetition may cause imbalance?

Answer 2

Java, with infinite length lookbehind and nested references (see also on ideone.com):

import java.util.regex.*;

class Factorial {
static String assertPrefix(String pattern) {
   return "(?<=(?=^pattern).*)".replace("pattern", pattern);
}
public static void main(String[] args) {
   final Pattern FACTORIAL = Pattern.compile(
      "(?x) (?: inc stepUp)+"
         .replace("inc", "(?=(^|\\1 .))")
         //                      1

         .replace("stepUp", "(?: ^. | (?<=(^.*)) (?=(.*)) (?: notThereYet \\2)+ exactlyThere )")
         //                                2          3

         .replace("notThereYet", "(?:  (?=((?=\\3) .  |  \\4 .)) (?=\\1(.*)) (?=\\4\\5)  )")
         //                                           4                  5

         .replace("exactlyThere", "measure4 measure1")
            .replace("measure4", assertPrefix("\\4(.*)"))
            .replace("measure1", assertPrefix("\\1\\6"))
   );

   for (int n = 0; n < 1000; n++) {
      Matcher m = FACTORIAL.matcher(new String(new char[n]));
      if (m.matches()) {
         System.out.printf("%3s = %s!%n", n, m.group(1).length() + 1);
      }
   }
}
}