Natural number sets matched by unary ECMAScript regexes, ranked by length
═════════════════════════════════════════════════════════════════════════


Symbols
───────
1     z
1+    x
2+    ^
2+    $
4+    ?
4+    {N}
5+    |
7+    *
7+    +
7+    ()
8+    {N,M}
9+    (?!)
10+   {N,}
10+   \backref
      (?=)
      \B
      \b
      (?:)


Rules
─────
1. A shorter regex matching the same set takes precedence
2. A regex with unmultiplied permutations takes precedence, as long as it doesn't use symbols not needed by any other regex of the same length or shorter; e.g. /^(xx)?$/ takes precedence over /^$|^xx$/, because /^(xx)*$/ also uses parentheses and is of the same length
3. A regex of length L matching set S using only symbols needed by regexes shorter than length M takes precedence over a regex that is also of length L matching set S using symbols needed by regexes of length M or longer, except when this conflicts with Rule #2
4. A regex of greater generality (i.e., that can modified to match a larger set of sets) takes precedence, except when this conflicts with Rule #3; e.g., "x{4}" takes precedence over "xxxx"
5. Preserve equal-length synonyms of a regex is they are sufficiently interesting due to being algorithmically very different, e.g. the three different forms that match powers of 2.
6. Aside from Rule #5, if the above rules still leave a regex with synonyms of the same length, then the one that evaluates most efficiently takes precedence. If even this isn't enough to eliminate all synonyms, then use some arbitrary criterion and try to be consistent about it.


Open questions
──────────────
• Is use of "z" needed to shorten any regexes other than the one matching the empty set?
• Is the current version of this document correct about the shortest lengths up to 8 that need certain symbols?
• What is the shortest length that need "(?=)"?
• What is the shortest length that need "\B"?
• What is the shortest length that need "\b"?
• What is the shortest length that needs "(?:)"? Of course it will be a regex that uses 10+ parenthesized expressions, and thus this question will probably be extremely difficult to answer.


Regexes
───────

0:
// - ~{}

1:
/x/ - ~{0}
/z/ - {}

2:
/xx/ - {n:n≥2}
/^$/ - {0}

3:
/xxx/ - {n:n≥3}
/^x$/ - {1}

4:
/x{N}/ - {n:n≥N} where 4≤N≤9
/^xx$/ - {2}
/^x?$/ - {0, 1}

5:
/x{NN}/ - {n:n≥NN} where 10≤NN≤99
/^xxx$/ - {3}
/^xx?$/ - {1, 2}
/^$|xx/ - ~{1}

6:
/x{NNN}/ - {n:n≥NNN} where 100≤NNN≤999
/^x{N}$/ - {N} where 4≤N≤9
/^xxx?$/ - {2, 3}
/^x?x?$/ - {0, 1, 2}
/^$|xxx/ - ~{1, 2}

7:
/x{NNNN}/ - {n:n≥NNNN} where 1000≤NNNN≤9999
/^x{NN}$/ - {NN} where 10≤NN≤99
/^xxxx?$/ - {3, 4}
/^xx?x?$/ - {1, 2, 3}
/^$|x{N}/ - {0, n:n≥N} where 4≤N≤9
/^x$|xxx/ - ~{0, 2}
/^(xx)?$/ - {0, 2}
/^(xx)*$/ - {n:n≡0 mod 2} = {even numbers}
/^(xx)+$/ - {n:n≡0 mod 2}∩{n:n≥2}

8:
/x{NNNNN}/ - {n:n≥NNNNN} where 10000≤NNNNN≤99999
/^x{NNN}$/ - {NNN} where 100≤NNN≤999
/^x{N,M}$/ - {n:N≤n≤M} where 0≤N≤9 and 0≤M≤9 and N<M and no shorter regex already does this
/^x{9}x?$/ - {9, 10}
/^$|x{NN}/ - {0, n:n≥NN} where 10≤NN≤99
/^x$|x{N}/ - {1, n:n≥N} where 4≤N≤9
/^x?$|xxx/ - ~{2}
/^x(xx)?$/ - {1, 3}
/^x(xx)*$/ - {n:n≡1 mod 2} = {odd numbers}
/^x(xx)+$/ - {n:n≡1 mod 2}∩{n≥3}
/^(xxx)?$/ - {0, 3}
/^(xxx)*$/ - {n:n≡0 mod 3}
/^(xxx)+$/ - {n:n≡0 mod 3}∩{n≥3}

9:
/x{NNNNNN}/ - {n:n≥NNNNNN} where 100000≤NNNNNN≤999999
/^x{NNNN}$/ - {NNNN} where 1000≤NNNN≤9999
/^x{NN}x?$/ - {NN, NN+1} where 10≤NN≤99
/^x{N,MM}$/ - {n:N≤n≤MM} where 0≤N≤9 and 10≤MM≤99 and N<MM and no shorter regex already does this
/^$|x{NNN}/ - {0, n:n≥NNN} where 100≤NNN≤999
/^x$|x{NN}/ - {1, n:n≥NN} where 10≤NN≤99
/^x?$|x{N}/ - {0, 1, n:n≥N} where 4≤N≤9
/^xx$|x{N}/ - {2, n:n≥N} where 4≤N≤9
/^(?!xxx$)/ - ~{3}
/^xx(xx)?$/ - {2, 4}
/^xx(xx)+$/ - {n:n≡0 mod 2}∩{n≥4}
/^x(xxx)?$/ - {1, 4}
/^x(xxx)*$/ - {n:n≡1 mod 3}
/^x(xxx)+$/ - {n:n≡1 mod 3}∩{n≥4}
/^(x{N})?$/ - {0, N} where 4≤N≤9
/^(x{N})*$/ - {n:n≡0 mod N} where 4≤N≤9
/^(x{N})+$/ - {n:n≡0 mod N}∩{n:n≥N} where 4≤N≤9

10:
/x{NNNNNNN}/ - {n:n≥NNNNNNN} where 1000000≤NNNNNN≤9999999
/^x{NNNNN}$/ - {NNNNN} where 10000≤NNNN≤99999
/^x{NNN}x?$/ - {NNN, NNN+1} where 100≤NN≤999
/^x{NN,MM}$/ - {n:NN≤n≤MM} where 10≤NN≤99 and 10≤MM≤99 and NN<MM and no shorter regex already does this
/^x{N,MMM}$/ - {n:N≤n≤MMM} where 0≤N≤9 and 100≤MM≤999 and N<MMM and no shorter regex already does this
/^$|x{NNNN}/ - {0, n:n≥NNNN} where 1000≤NNNN≤9999
/^x$|x{NNN}/ - {1, n:n≥NNN} where 100≤NNN≤999
/^x?$|x{NN}/ - {0, 1, n:n≥NN} where 10≤NN≤99
/^xx$|x{NN}/ - {2, n:n≥NN} where 10≤NN≤99
/^xx?$|x{N}/ - {1, 2, n:n≥N} where 4≤N≤9
/^xxx$|x{N}/ - {3, n:n≥N} where 5≤N≤9
/^(?!x{N}$)/ - ~{N} where 4≤N≤9
/^(xx){N,}$/ - {n:n≡0 mod 2}∩{n≥2N} where 3≤N≤9
/^xxx(xx)+$/ - {n:n≡1 mod 2}∩{n≥5}
/^xx(xxx)?$/ - {2, 5}
/^xx(xxx)*$/ - {n:n≡2 mod 3}
/^xx(xxx)+$/ - {n:n≡2 mod 3}∩{n≥5}
/^x(x{N})*$/ - {n:n≡1 mod N}
/^x(x{N})+$/ - {n:n≡1 mod N}∩{n≥4}
/^(xxxx?)*$/ - ~{1, 2, 5}
/^(xxxx?)+$/ - ~{n:n≤2, 5}
/^(x{NN})?$/ - {0, NN} where 10≤NN≤99
/^(x{NN})*$/ - {n:n≡0 mod NN} where 10≤NN≤99
/^(x{NN})+$/ - {n:n≡0 mod NN}∩{n:n≥NN} where 10≤NN≤99
/^(xx+)\1+$/ - {composite numbers}

11:
/^(xxx+)\1+$/ - {composite numbers}∩{n:n≥6}

12:

13:
/^(x(xx)+)\1*$/ - ~{0, powers of 2}
/^(x+)(\1\1)+$/ - ~{0, powers of 2}
/^(x*)(\1\1)+$/ - ~{powers of 2}

14:
/^(?!(xx+)\1+$)/ - ~{composite numbers} = {0, 1, prime numbers}
/^(xx+)(\1\1)+$/ - {composite numbers}∩~{powers of 2}

15:
/^(?!(xxx+)\1+$)/ - ~({composite numbers}∩{n:n≥6}) = {0, 1, 4, prime numbers}

16:

17:
/^(?!(x(xx)+)\1*$)/ - {0, powers of 2}
/^(?!(x+)(\1\1)+$)/ - {0, powers of 2}
/^(?!(x*)(\1\1)+$)/ - {powers of 2}
/^((x+)(?=\2$))*x$/ - {powers of 2}
/^((x+)(?=\2$))+x$/ - {powers of 2}∩{n:n≥2}
/^(x(x*)(?=\2$))*$/ - {powers of 2 minus 1}
/^((x+)(?=\2$)x)*$/ - {powers of 2 minus 2}

18:
/^(?!(xx+)(\1\1)+$)/ - {powers of 2}∪~{composite numbers} = {powers of 2}∪{0, 1, prime numbers}