# Now solve this

Sameer Jamal

Ranch Hand

Posts: 1870

posted 11 years ago

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 ]

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 ]

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

(((((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.

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 ]

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

Posts: 1105

7

posted 10 years ago

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

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.

posted 10 years ago

And if you allow decimal points? Since 9/.9 = 10, you should be able to go a lot farther.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 ]

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

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

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

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.

*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.

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

Ryan McGuire

Ranch Hand

Posts: 1105

7

posted 10 years ago

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.)

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?

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

Sheriff

Posts: 18671

posted 10 years ago

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.

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.

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.

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

[ March 01, 2006: Message edited by: Jim Yingst ]

**[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.

[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 ]

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

posted 10 years ago

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 ]

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 ]