I have written a Delphi application to brute force a solution. Unfortunately I see no way of solving the problem: what expression(s) results in number N? That is I see no solution other than generating all expressions and then seeing what natural numbers they result in.
So I can't really help with Bobson's crowd-sourcing approach.
I am following klm123's idea, and I have ran the application with:
N = 3 : 0,1,2
Execution time: 00:00:00
Expressions processed: 441 [Average: 27.562,5/sec]
Expressions calculated: 34 [Average: 2.125,0/sec]
Natural numbers calculated: 28 [Average: 1.750,0/sec]
Distinct natural numbers found: 14 [Average: 875,0/sec]
Highest natural found: 210
Lowest natural not found: 4
N = 4 : 0,1,2,3
Execution time: 00:00:00
Expressions processed: 22.924 [Average: 363.873,0/sec]
Expressions calculated: 1.464 [Average: 23.238,1/sec]
Natural numbers calculated: 871 [Average: 13.825,4/sec]
Distinct natural numbers found: 110 [Average: 1.746,0/sec]
Highest natural found: 3.210
Lowest natural not found: 25
N = 5 : 0,1,2,3,4
Execution time: 00:00:04
Expressions processed: 1.679.977 [Average: 401.812,2/sec]
Expressions calculated: 98.228 [Average: 23.493,9/sec]
Natural numbers calculated: 45.423 [Average: 10.864,1/sec]
Distinct natural numbers found: 884 [Average: 211,4/sec]
Highest natural found: 43.210
Lowest natural not found: 89
N = 6 : 0,1,2,3,4,5
Execution time: 00:08:39
Expressions processed: 159.888.346 [Average: 307.590,0/sec]
Expressions calculated: 8.867.950 [Average: 17.060,0/sec]
Natural numbers calculated: 3.236.479 [Average: 6.226,3/sec]
Distinct natural numbers found: 8.661 [Average: 16,7/sec]
Highest natural found: 543.210
Lowest natural not found: 653
N = 7 : 0,1,2,3,4,5,6
Execution time: 19:36:02
Expressions processed: 18.788.082.577 [Average: 266.262,5/sec]
Expressions calculated: 1.014.272.742 [Average: 14.374,2/sec]
Natural numbers calculated: 308.146.445 [Average: 4.367,0/sec]
Distinct natural numbers found: 93.219 [Average: 1,3/sec]
Highest natural found: 6.543.210
Lowest natural not found: 5.683
Now on to N=8. I got a few small optimizations in mind, but nothing that will cut this drastically, I presume.
Explanation of what the application is doing
I have two input parameters: Digits and Operators. I also have some other parameters to handle output dump to disk, but they have nothing to do with the algo.
The application starts processing the empty expression: 0 length string.
Every time an expression E is processed, I do the following:
1. check all Digits - for any single digit D not already included in E, I process the expression E+D (concatenation, not sum). To optimize a bit I avoid this step if E ends with a closed parenthesis. I also avoid this if D is 0 and E does not end with any other Digit.
2. check all Operators - for any single operator O, I process the expression E+O. To optimize I avoid this step if E is empty or ends with another operator or with an open parenthesis.
3. check ")" - if E ends with a Digit or a closed parenthesis, and it has a pending unclosed parenthesis, and this contains at least one operatore, then I process the expression E+).
4. check "(" - if E is empty or ends with an Operator or an open parenthesis, then I process the expression E+(. To avoid infinite recursion there is some magic here... I do it only if the number of Digits still unused in E is greater the number of pending unclosed parenthesis in E plus 1.
5. calculate the expression - if E ends with a Digit or a closed parenthesis, and all parenthesis are balanced and are useful (contain at least one operator), and it does not start with ( and end with ) then I calculate the expression. If it turns out to be a natural number, then I check it with the highest found natural and lowest unfound natural.
Processing of derived expressions is obviously done through recursion. The algo seems quite efficient, apart from the parenthesis part. I have made some changes to this code and it now validates parenthesis better, avoiding some recursion in useless branches and evaluation os redundant expressions. It's not perfect, but it does cut times as N goes up. (I am using Artem V. Parlyuk's ArtFormula package of nonvisual Delphi component for symbolic expression parsing and evaluation).
As an aside, I also keep track of the shortest expression that can generate each natural number found. The shortest is meaningful, as it is usually the most immediate and readable. It is also always the one with no useless parenthesis ;)
Tweaking the parenthesis logic, I have stumbled upon a small bug. It was generating a lot of useless expressions (with redundant parenthesis) but it was not generating some useful expressions. With N<=5 this bug did not have any effects. With N=6 I did find 6 more natural numbers, though the lowest unfound natural is 653.