Generate regular expressions for matching natural numbers between `m` and `n` The type of regular expression is PCRE.

Write a program that output a valid PCRE such that it matches all natural numbers between m and n and does not match anything else. No leading zeros are allowed. 

For example, let m and n be 123 and 4321, then the program might output
1(2[3-9]|[3-9]\d)|[2-9]\d\d|[123]\d\d\d|4([012]\d\d|3([01]\d|2[01])).

This matches the exact string, so ^ and $ anchors are implicit. 

One should try to balance the two:


The regular expression should have a reasonable size.
The code should be short.


Let's optimize for 

code length in characters + 2*regular expression length for input 123456 and 7654321

Side Note: It be interesting if we can prove the shortest PCRE regular expression is of the size O(log n log log n) or something.
Perl, score 455 

191 chars, 132 regex length

sub b{my$a=shift;$_=(@_&gt;0&amp;&amp;$a.b(@_).($a--&gt;0&amp;&amp;'|')).($a&gt;=0&amp;&amp;($a&gt;1
?"[0-$a]":$a));/\|/?"($_)":$_}sub a{b(@a=split//,&lt;&gt;-1+$x++).(@a&gt;
1&amp;&amp;"|.{1,$#a}")}print'(?!0|('.a.')$)(?=('.a.'$))^\d{1,'.@a.'}$'


Input: 123456, 7654321

(?!0|((1(2(3(4(5[0-5]|[0-4])|[0-3])|[0-2])|1)|0)|.{1,5})$)(?=((7(6(5(4(3(21|1)|[0-2])|[0-3])|[0-4])|[0-5])|[0-6])|.{1,6}$))^\d{1,7}$


Update: I was able to further simplify this when I realized that most of the patterns ended with things like \d{3}.  These were doing nothing more than enforcing a string length--and doing so very repetitively, since they occurred on every term.  I eliminated this by using another lookahead to enforce the "less than" condition, only checking that either: 1) the first part of the number does not exceed the input or 2) the number is fewer digits than the input.  Then the main regex just verifies that it is not too many digits.

I also incorporated Peter Taylor's idea of negative look-ahead for checking the "greater than" condition.

The key to simplifying this problem (at least for me) was to break the regex in two: a look-ahead makes sure the number is not less than the minimum, then the main part of the regex checks that it is not greater than the maximum.  It is a little bit silly for small input, but it is not so bad for large input.

Note: the 0| at the beginning is to exclude anything that starts with a zero from matching.  This is required because of the recursive nature of the regex function: inner parts of the match can start with zero, but the entire number cannot.  The regex function can't tell the difference, so I excluded any number starting with zero as a special case.

Input: 1, 4

(?!0|(0)$)(?=([0-4]$))^\d{1,1}$


Unreasonably Long Regex Version, 29 chars:

print'^',join('|',&lt;&gt;..&lt;&gt;),'$'