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

[Tim Wintle]

On Fri, 2009-02-20 at 16:38 +0000, Nigel Rantor wrote:
> Luke Dunn wrote:

<snip>

That was my initial thought when I read this too - but I'm not certain
that is guaranteed to find a solution (i.e. a solution that's optimal).

I'd welcome a proof that it will though, a few minutes thought hasn't
found a counter-example.

> > 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
> > 
> > 
> > 
> > 
> 
> --
> http://mail.python.org/mailman/listinfo/python-list