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

[Luke Dunn]

I am teaching myself coding. No university or school, so i guess its
homework if you like. i am interested in algorithms generally, after doing
some of Project Euler. Of course my own learning process is best served by
just getting on with it but sometimes you will do that while other times you
might just choose to ask for help. if no one suggests then i will probably
shelve it and come back to it myself when I'm fresh.

no it's not a real world problem but my grounding is in math so i like pure
stuff anyway. don't see how that is a problem, as a math person i accept the
validity of pure research conducted just for curiosity and aesthetic
satisfaction. it often finds an application later anyway

Thanks for your helpful suggestion of trying other methods and i will do
that in time. my motive was to share an interesting problem because a human
of moderate math education can sit down with this and find minimal solutions
easily but the intuition they use is quite subtle, hence the idea of
converting the human heuristic into an algorithm became of interest, and
particularly a recursive one. i find that the development of a piece of
recursion usually comes as an 'aha', and since i hadn't had such a moment, i
thought i'd turn the problem loose on the public. also i found no online
reference to this problem so it seemed ripe for sharing.

On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor <wiggly 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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090220/aba68c4d/attachment-0001.html>