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.d...@gmail.com > > <mailto:luke.d...@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 <wig...@wiggly.org > > <mailto:wig...@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 -- http://mail.python.org/mailman/listinfo/python-list
