12 replies to this topic

[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

Spoiler for My answer

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]

Spoiler for I agree with Rox53

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]

Spoiler for thought I had 14

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

Spoiler for

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 by TheChad08, 29 August 2012 - 03:07 AM.

[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 by TheChad08, 29 August 2012 - 05:23 AM.

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

Spoiler for Maybe not that much work

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.