only allowed 1

[phil1882]

you have the following allowable operations, addition, multiplication, and parenthesis.

further more the only number you are allowed to use is 1. for example, the number 15 could be

(1+1+1)*((1+1)*(1+1)+1)

express 137 with the fewest number of 1's in a single expression.

[Pankaj Varma]

(1+1)^((1+1)^(1+1+1)-1)+(1+1+1)^(1+1) does it in 13 ones.

[Rox53]

I reached the same conclision - but then I thought that the problem seems to exclude using powers (or factorials, for that matter). So, here's my attempt at a solution

I think 16 one's are needed. See below (1+1) x (1+1) x (1+1) x([1+1+1+1] x [1+1+1+1]+1)+1

[kappak1020]

I got {[(1+1)*(1+1)*(1+1)] * [((1+1)(1+1)(1+1)(1+1))+1]} +1 giving you sixteen ones. Its the same answer as Rox53 i think, just written differently

[BobbyGo]

^{...but I forgot about the two at the end}

^{((1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1))+1+1}

[jim]

EXTENSION PROBLEM. What is the smallest number that requires at least 16 ones--and what is the largest number that can be expressed with no more than 16 ones?

[TheChad08]

EXTENSION PROBLEM. What is the smallest number that requires at least 16 ones--and what is the largest number that can be expressed with no more than 16 ones?

Well, the smallest number to use 16 ones is... 1

1*1*1*1*etc.

Without even really trying, I think 256 might be the largest you can get with 16 ones.

(1+1+1+1)*(1+1+1+1)*(1+1+1+1)*(1+1+1+1)

EDIT: If you don't like my answer for the smallest one that requires at 16 ones, then I'll say 16

1+1+1+1+1

Or do you mean the smallest number that can be uniquely obtained with 16 ones?

Technically 16 can be obtained with fewer ones.

Edited August 29, 2012 by TheChad08

[bonanova]

EXTENSION PROBLEM. What is the smallest number that requires at least 16 ones--and what is the largest number that can be expressed with no more than 16 ones?

Let's restate to avoid misinterpretation (given the conditions set forth in OP about 1's +, x and parentheses):

1. What is the smallest number that cannot be expressed using fewer than 16 1's?

2. What is the largest number that can be expressed using 16 1's or fewer?

Since we can add any leftover 1's if fewer than 16 are used, precisely 16 1's applies in the second case.

[TheChad08]

Let's restate to avoid misinterpretation (given the conditions set forth in OP about 1's +, x and parentheses):

1. What is the smallest number that cannot be expressed using fewer than 16 1's?

Well, that requires a LOT of work.

We would need to know what numbers are possible for the other combinations.

Sounds like more work than I want to do.

Someone will write a code with all possible combinations of numbers to get it.

I see 32 768 combinations of addition and multiplication between the 15 ones. This doesn't include the brackets.

Lots of these will be mirror images though and can be discounted.

Edited August 29, 2012 by TheChad08

[bonanova]

Well, that requires a LOT of work.

We would need to know what numbers are possible for the other combinations.

Sounds like more work than I want to do.

Someone will write a code with all possible combinations of numbers to get it.

I see 32 768 combinations of addition and multiplication between the 15 ones. This doesn't include the brackets.

Lots of these will be mirror images though and can be discounted.

Here are the smallest numbers (first one in each group) that require 1-15 1's.

We can continue this process until 16 is reached.

1. 1

2. 2

3. 3

4. 4

5. 5 6

6. 7 8 9

7. 10 12

8. 11 13 14 15 16 18

9. 17 19 20 21 24 27

10. 22 23 25 26 28 30 32 36

11. 29 31 33 34 35 37 38 39 40 42 45 48 54

12. 41 43 44 46 47 49 50 51 52 53 55 56 57 59 60 63 64 72 81 87

13. 58 61 62 65 66 68 70 71 73 74 75 76 78 80 82 84 86 88 90

14. 67 69 77 79 83 85 89 91 92 93

15. 94 (2 x 47)

So 94 appears to require 15 1's

And so on. Find the most compact representation of each number, using the info for the smaller numbers already found, and place them in the table. Eventually, 16 1's will be needed, and that will be the answer.

[jim]

Comments. The smallest number does require a lot of messy testing. But the largest number is another matter. As noted above, we can do 256. There are also two larger numbers we can also do. What are they?

[BobbyGo]

Comments. The smallest number does require a lot of messy testing. But the largest number is another matter. As noted above, we can do 256. There are also two larger numbers we can also do. What are they?

I've gotten...

270 = (1+1)*(1+1+1)*(1+1+1)*(1+1+1)*(1+1+1+1+1)

288 = (1+1)*(1+1+1)*(1+1+1)*(1+1+1+1)*(1+1+1+1)

324 = (1+1+1)*(1+1+1)*(1+1+1)*(1+1+1)*(1+1+1+1)

Edited August 29, 2012 by BobbyGo

[jim]

Bobby Go . Nice answer. I missed 270. There is a general method to find the largest such number with 3n-1, 3n, or 3n+1 as the number of ones--where n= m+1. It is easiest for 3n.