This week's book giveaway is in the OCPJP forum. We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line! See this thread for details.

Combining nine 9s with any number of the operators +, -, *, /, (, ) , what is the smallest positive integer that cannot be expressed? Hints: 1)The answer isn't zero. You can express zero like this: (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9) Also, zero isn't a positive integer. 2) The answer isn't one. You can express one like this: 9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9 [ February 25, 2006: Message edited by: Sameer Jamal ]

If we allow only the operations explicitly stated and shown in the examples, I get 195 as the first unsolvable number.

If we also allow nines to be concatenated as decimal numbers, such that two nines can form 99, then I get 430.

If we also allow exponentiation, e.g. x^y = Math.pow(x, y) (which could be indicated positionally by placing y slightly above and to the right of x), then I get 438. [ February 28, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012

3

posted

0

Originally posted by Jim Yingst: (((((9+9)*9)+9)/(9+9+9))+9)*9 = (171/27+9)*9 = 138

If we allow only the operations explicitly stated and shown in the examples, I get 195 as the first unsolvable number.

Ahh yes, fractional division.

After a slight adjustment, I come up with 195 also.

I like how the expression for 138 reduces to 9 * (18 + (-72/27)) = 138

One a side note: if you use only integer division (9/2 = 4), the answer is still 195.

Originally posted by Jim Yingst: If we also allow nines to be concatenated as decimal numbers, such that two nines can form 99, then I get 430.

If we also allow exponentiation, e.g. x^y = Math.pow(x, y) (which could be indicated positionally by placing y slightly above and to the right of x), then I get 438.[ February 28, 2006: Message edited by: Jim Yingst ]

And if you allow decimal points? Since 9/.9 = 10, you should be able to go a lot farther.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

Ah, but a decimal point requires writing an extra symbol, not listed in the original problem. Concatenating nines as decimal numbers wasn't listed either, nor exponentiation - but both are operations which can be expressed using position, with no extra symbols. So they may reasonably fall under the "nine nines" description, or they may reasonably be excluded; it's ambiguous. I can't see any way to justify adding a decimal point though without changing the problem.

All of which is my way of stalling you because adding a decimal point seems to make this considerably harder. My current program will take several hours to run, at least. From what I've seen so far, I'll guesstimate maybe a day. Adding a binary operator like ^ doesn't expand the search space too much, since every time you use it, you're also reducing the number of available operands remaining. But adding that roving decimal point just adds orders of magnitude to the search space, it seems.

Additionally it raises issues with accuracy - I'm doing calculations with doubles, and assuming that any result within 0.000000000001 of an integer is, in fact, an integer. But with all these extra decimals floating around I'm not sure how valid that will be. It might be necessary to create (or borrow) a RationalNumber class to represent a rational number exactly. That will probably run even slower of course, and if allowed in combination with exponentiation, creates other issues - the result may not be rational. Unless additional restrictions are assumed.

Eh, I think I'll just stick with saying that the decimal symbol is not allowed for this problem.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012

3

posted

0

Originally posted by Jim Yingst: My current program will take several hours to run, at least.

Holy crap, dude! Is that for the original, four-operator problem?

I'm on a 1.73 GHz Pentium with 1 GB RAM and it only takes me 53 secs for the answer to the original problem. (Plus I have Outlook, Eclipse, a couple of Notepads, and some other things running too.)

It might be necessary to create (or borrow) a RationalNumber class to represent a rational number exactly.

Yeah, I just wrote my own.

What's your algorithm like?

And lastly... If you're going to include exponentiation, why not include log() to a given base?

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

[Ryan]: Holy crap, dude! Is that for the original, four-operator problem?

Oh, no. I'm talking about the latest version to handle Paul's decimal point. Which also of course includes concatenating digits, so possible operands include 9, .9, 99, 9.9, .99, etc. In the current run I'm eliminated the power operand, since that has its own increase in runtime.

My 1.5 GHz PowerBook is busy right now thanks to Paul, but on my ancient 500 MHz Dell desktop, the program for the original problem runs in about ten minutes. Aside from the speed difference, seems like there's still some room for improvement there. Oh well. I spent a little time optimizing, but once I had the answer and it would've taken more than ten minutes to optimize it further, I figured there were diminishing returns from there on.

[Jim]: It might be necessary to create (or borrow) a RationalNumber class to represent a rational number exactly.

[Ryan]: Yeah, I just wrote my own.

I considered it earlier, but since I also wanted to allow power operations (including non-integer powers), I figured it would be better to just use doubles. To be fair, I suspect the non-integer powers have never led to a solution that wasn't already reachable by simpler techniques, so I could probably just drop that.

[Ryan]: What's your algorithm like?

Fairly simple brute force. It's structured after RPN notation, like the traditional HP calculators - there's a stack of operands, and at every decision point, you can either push another nine on the stack, or apply an operator to the two latest elements and replace them with the result. If it leads to a new integer solution, I make a string representation of the operators and operands and save it.

[Ryan]: And lastly... If you're going to include exponentiation, why not include log() to a given base?

Because that would require a new symbol, not originally listed among the operators for this problem. To be clear, when I said exponentiation, I meant Math.pow() rather than Math.exp(). The point is that to indicate raising one number to the power of another, I don't need any additional symbol; I can just position the numbers appropriately. But for either an exponential function or a log function, I'd need additional symbols. I figure that using powers this way is probably outside the intended scope of the problem, but not necessarily. Given nine nines, I think it's not unreasonable to take two of them and write 9 to the 9th power, with no other symbols needed. [ March 01, 2006: Message edited by: Jim Yingst ]

Is this a mathematical question or a programing question?

Of course this would leed to the observation: if ++(n) is allowed, then ++(++(n)) is allowed, so if we can express 1, we can express everything. (q.e.d.)

[ March 02, 2006: Message edited by: Stefan Wagner ] [ March 02, 2006: Message edited by: Stefan Wagner ]