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

[Trip Technician]

On 20 Feb, 15:39, Nigel Rantor <wig... at wiggly.org> wrote:
> 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- Hide quoted text -
>
> - Show quoted text -

yes n^n^n would be fine. agree it is connected to factorisation.
building a tree of possible expressions is my next angle.