How does this regex find triangular numbers?

Viewed 2590

Part of a series of educational regex articles, this is a gentle introduction to the concept of nested references.

The first few triangular numbers are:

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

There are many ways to check if a number is triangular. There's this interesting technique that uses regular expressions as follows:

  • Given n, we first create a string of length n filled with the same character
  • We then match this string against the pattern ^(\1.|^.)+$
    • n is triangular if and only if this pattern matches the string

Here are some snippets to show that this works in several languages:

PHP (on ideone.com)

$r = '/^(\1.|^.)+$/';

foreach (range(0,50) as $n) {
  if (preg_match($r, str_repeat('o', $n))) {
     print("$n ");
  }
}

Java (on ideone.com)

for (int n = 0; n <= 50; n++) {
    String s = new String(new char[n]);
    if (s.matches("(\\1.|^.)+")) {
        System.out.print(n + " ");
    }
}

C# (on ideone.com)

Regex r = new Regex(@"^(\1.|^.)+$");

for (int n = 0; n <= 50; n++) {
    if (r.IsMatch("".PadLeft(n))) {
       Console.Write("{0} ", n);
    }
}

So this regex seems to work, but can someone explain how?

Similar questions

1 Answers
Related