On 4/1/10, Robert K. [email protected] wrote:

As long as you do not limit the number of unary operations that

program is not guaranteed to terminate - especially if there is no

solution for given X, Y and Z. Am I missing something?

It should be interesting to see what solution strategy you are picking.

Thanks, and thanks to everyone else who replied.

You’re right: I hadn’t thought of this.

If I start with 4 and allow sqrt, I get sqrt(4),

sqrt(sqrt(4)), sqrt(sqrt(sqrt(4))) and so on. Of

course, these aren’t integers after the first sqrt, but

they could theoretically combine with other 4

combinations later to form an integer.

I incorrectly thought one iteration of a unary operator would suffice.

I originally got interested in this problem because I

thought factorial was a cheat. Some of the solutions on

http://mathforum.org/ruth/four4s.puzzle.html use the

gamma function, integer 4th root, etc. Where do you

draw the line? If you allow constant functions (eg,

f(x) = 56), the solution is trivial.

My new goal is to solve the simpler problem, very

similar to http://www.rubyquiz.com/quiz7.html (thanks,

Brian!).

Given X copies of the digit Y and the 5 mathematical

operators plus, minus, multiply, divide, and exponent,

along with concatenation and decimals (see below), can

you construct the number Z?

My approach for 5 copies of the digit 7 (example):

% With one 7, you have {7, 0.7} (the latter because we

allow decimals-- but not 0.07)

% With two 7s, we union two sets:

% {77, 7.7, .77} (from decimals and concatenation)

% Apply + - * / ^ to every ordered pair of elements

in the resultset for one 7 (including “pairs” like

{7,7}). Not showing the results, but you get the

idea.

% We then recurse. For n 7s, we union:

% {777…[n times], 777…[n-1 times].7, 777…[n-2 times].77, etc}

% Applying + - * / ^ to every ordered pair of the

resultset for n-1.

It might still be interesting to create a website that does this.