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

[Nigel Rantor]

Luke Dunn wrote:
> yes power towers are allowed

right, okay, without coding it here's my thought.

factorise the numbers you have but only allowing primes that exist in 
your digit set.

then take that factorisation and turn any repeated runs of digits 
multiplied by themselves into power-towers

any remainder can then be created in other ways, starting with a way 
other than exponentiation that is able to create the largest number, 
i.e. multiplication, then addition...

I've not got time to put it into code right now  but it shouldn't be too 
hard...

e.g.

digits : 3, 2, 1

n : 10
10 = 2*5 - but we don't have 5...
10 = 3*3 + 1
10 = 3^2+1
3 digits

n : 27
27 = 3*3*3
27 = 3^3
2 digits

n : 33
33 = 3*3*3 + 6
33 = 3*3*3 + 3*2
33 = 3^3+3*2
4 digits

> exponentiation, multiplication, division, addition and subtraction. 
> Brackets when necessary but length is sorted on number of digits not 
> number of operators plus digits.
>  
> I always try my homework myself first. in 38 years of life I've 
> learned only to do what i want, if I wanted everyone else to do my work 
> for me I'd be a management consultant !
> On Fri, Feb 20, 2009 at 3:52 PM, Luke Dunn <luke.dunn at gmail.com 
> <mailto:luke.dunn at gmail.com>> wrote:
> 
>     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
>     <mailto: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
> 
> 
> 
>