code challenge: generate minimal expressions using only digits 1,2,3

[Nigel Rantor]

Trip Technician wrote:
> anyone interested in looking at the following problem.

if you can give me a good reason why this is not homework I'd love to 
hear it...I just don't see how this is a real problem.

> we are trying to express numbers as minimal expressions using only the
> digits one two and three, with conventional arithmetic. so for
> instance
> 
> 33 = 2^(3+2)+1 = 3^3+(3*2)
> 
> are both minimal, using 4 digits but
> 
> 33 = ((3+2)*2+1)*3
> 
> using 5 is not.
> 
> I have tried coding a function to return the minimal representation
> for any integer, but haven't cracked it so far. The naive first
> attempt is to generate lots of random strings, eval() them and sort by
> size and value. this is inelegant and slow.

Wow. Okay, what other ways have you tried so far? Or are you beating 
your head against the "search the entire problem space" solution still?

This problem smells a lot like factorisation, so I would think of it in 
terms of wanting to reduce the target number using as few operations as 
possible.

If you allow exponentiation that's going to be your biggest hitter so 
you know that the best you can do using 2 digits is n^n where n is the 
largest digit you allow yourself.

Are you going to allow things like n^n^n or not?

   n