Author |
Topic: 1 3 5 7 9 (Read 792 times) |
|
Leo Broukhis
Senior Riddler
Gender: 
Posts: 459
|
What is the smallest nonnegative integer that cannot be represented as an expression that involves only numbers (as opposed to digits) 1, 3, 5, 7, 9 - each one exactly once - and uses only basic four arithmetic operations? What is the largest integer that can be represented?
|
|
 IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
 |
Re: 1 3 5 7 9
« Reply #2 on: Feb 4th, 2005, 12:53am » |
 Quote  Modify
|
Single digit numbers (namely 1, 3, 5, 7 and 9) are the only numbers that are allowed.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 3 5 7 9
« Reply #3 on: Feb 4th, 2005, 2:46am » |
Quote Modify
|
so (9-7)/(5-3)-1=0
and 3*5*7*(9+1)=1050 ?
Or can we also only use each arithmetic operator only once?
|
| « Last Edit: Feb 4th, 2005, 2:47am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1 3 5 7 9
« Reply #4 on: Feb 4th, 2005, 5:23am » |
Quote Modify
|
Towr, I think you misinterpreted the first question:
on Feb 4th, 2005, 12:01am, Leonid Broukhis wrote:| What is the smallest nonnegative integer that CANNOT be represented as an expression that involves only numbers 1, 3, 5, 7, 9 - each one exactly once - and uses only basic four arithmetic operations? |
|
…and there is a better candidate for the second answer: (1+3)*5*7*9 = 1260.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
 |
Re: 1 3 5 7 9
« Reply #5 on: Feb 4th, 2005, 6:29am » |
Quote Modify
|
The first few nonnegative integers are relatively easy:
::
0 == (9-7)/(5-3)-1
1 == 9-7-5+3+1
2 == (9-7)/(5-3)+1
3 == 9-7+5-3-1
4 == 9/3+7-5-1
5 == 9-7+5-3+1
6 == 9/3+1+7-5
7 == 9+7-5-3-1
8 == 1*9+7-5-3
9 == 9+7-5-3+1
10 == 9*5/3-1*5
11 == 9-7+5+3+1
12 == (9-5-1)*(7-3)
13 == 9+7-5+3-1
14 == 9+7-5+3*1
15 == 9+7-5+3+1
16 == (9-7)*(5+3)*1
17 == 9+7+5-3-1
18 == 9+7+5-3*1
19 == 9+7+5-3+1
20 == 5*(9+7)/(3+1)
21 == 5*(7-9/3)+1
22 == 5*(9-3)-7-1
23 == 9+7+5+3-1
24 == 5*(9-3)-7+1
25 == 9+7+5+3+1
26 == (9/3)*7+5*1
27 == (7+5-3)*9/3
28 == 7*(9-1)/(5-3)
29 == 3*(9-7)*5-1
30 == 3*(9-7)*5*1
31 == 7*3*(9+1)/5
32 == (9+7)*(5-3)*1
33 == 9*(7+5-1)/3
34 == (9+7+1)*(5-3)
35 == 7*(9+1)/(5-3)
36 == (7+3-1)*(9-5)
37 == (9/3)*(7+5)+1
38 ==
39 == 9*(7+5+1)/3
40 == (9+1)*(7+5)/3
41 ==
42 == 7*3*(9+1)/5
::
I will fill in more as I figure them out.
|
| « Last Edit: Feb 4th, 2005, 11:09am by John_Gaughan » |
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
asterix
Guest
|
Just to fill in the one you skipped. 21=5*(7-(9/3))+1
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #7 on: Feb 4th, 2005, 8:13am » |
Quote Modify
|
on Feb 4th, 2005, 2:46am, towr wrote:so (9-7)/(5-3)-1=0
and 3*5*7*(9+1)=1050 ?
Or can we also only use each arithmetic operator only once? |
|
What is the smallest number that cannot be represented?
I expected the largest number part to be a "think again" question, and it worked. A cognitive scientist may be able to explain why it works.
Using each operation only once is too restrictive. 
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
 
Gender:
Posts: 2873
|
|
Re: 1 3 5 7 9
« Reply #8 on: Feb 4th, 2005, 8:34am » |
Quote Modify
|
I can get ::1260=(1+3)*5*7*9:: for "largest possible"
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 1 3 5 7 9
« Reply #9 on: Feb 4th, 2005, 9:59am » |
Quote Modify
|
on Feb 4th, 2005, 8:13am, Leonid Broukhis wrote:
What is the smallest number that cannot be represented?
|
|
-[infty]?
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #10 on: Feb 4th, 2005, 10:17am » |
Quote Modify
|
on Feb 4th, 2005, 9:59am, Grimbal wrote:
I did say "nonnegative integer" in the original posting.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1 3 5 7 9
« Reply #11 on: Feb 5th, 2005, 12:19am » |
Quote Modify
|
I get 122 for the first question.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1 3 5 7 9
« Reply #12 on: Feb 5th, 2005, 12:30am » |
Quote Modify
|
on Feb 4th, 2005, 8:13am, Leonid Broukhis wrote:
What is the smallest number that cannot be represented? |
|
I get 122.
Leonid, do you know what is second smallest such number?
on Feb 4th, 2005, 8:13am, Leonid Broukhis wrote:
I expected the largest number part to be a "think again" question, and it worked. A cognitive scientist may be able to explain why it works. |
|
Could you explain this (are you a cognitive scientist?  )
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #13 on: Feb 5th, 2005, 11:49am » |
Quote Modify
|
on Feb 5th, 2005, 12:30am, Barukh wrote:
I get 1xx.
Leonid, do you know what is second smallest such number?
Could you explain this (are you a cognitive scientist? )
|
|
1xx is right. Second smallest is 1xx + 16. If you're asking, does it mean that you have not automated the search process? 
I have a list of all numbers that can be represented.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #14 on: Feb 5th, 2005, 11:52am » |
Quote Modify
|
on Feb 5th, 2005, 12:30am, Barukh wrote:
Could you explain this (are you a cognitive scientist? )
|
|
Not rigorously, but I guess that the subconscious "make biggest part bigger to make the whole look bigger" has something to do here.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: 1 3 5 7 9
« Reply #15 on: Feb 5th, 2005, 5:20pm » |
Quote Modify
|
And the next such number is 1xx+24.
Nice problem, Leonid.
As an extension...
(1) Up to the maximum value expressible using the odd numbers: 1, 3, 5, 7, 9, what percentage of numbers can be obtained?
(2) What if the even numbers: 0, 2, 4, 6, 8, are used instead?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #16 on: Feb 5th, 2005, 6:36pm » |
Quote Modify
|
on Feb 5th, 2005, 5:20pm, Sir Col wrote:And the next such number is 1xx+24.
Nice problem, Leonid.
|
|
Inspired by making 24 out of 1, 3, 4, 6.
Quote:
As an extension...
(1) Up to the maximum value expressible using the odd numbers: 1, 3, 5, 7, 9, what percentage of numbers can be obtained?
|
|
I get 28.47%
Quote:
(2) What if the even numbers: 0, 2, 4, 6, 8, are used instead? |
|
20.52%
And if numbers 1, 2, 3, 4, 5 are used, then it is 67.40%
For 1, 2, 3, 4 it is 86.49%
For 1, 2, 3 it is 100%
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: 1 3 5 7 9
« Reply #17 on: Feb 6th, 2005, 2:53am » |
Quote Modify
|
I'm intrigued to know what approach you used.
I used postfix (reverse Polish) notation with permutations of the given numbers. For those unfamiliar, a couple of examples will demonstrate how this system allows for unambigous stack/array calculations without the need for brackets/parentheses:
3 4 + 2 * = 7 2 * = 14
2 17 13 - / 11 + = 2 4 / 11 + = 0.5 11 + = 11.5
Then using a collection of masks I inserted all combinations of the arithmetic symbols at the appropriate places.
For example, when working with four numbers: a, b, c, d, the three arithmetic symbols (#) can legally be placed in the following places:
a b c d # # #
a b c # d # #
a b c # # d #
a b # c d # #
a b # c # d #
It turns out that the number of masks for a set of n numbers is given by C(2n-2,n-1)/n, which is the (n-1)th Catalan number [nth Catalan = C(2n,n)/(n+1)]. So I used fourteen masks for a set of five numbers.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #18 on: Feb 6th, 2005, 10:17pm » |
Quote Modify
|
I used putting 1 3 5 7 9 or whatever set of numbers in a vector, randomly taking two elements (== shuffling the vector and taking 1st and 2nd elements), applying a random operation and putting the result back, then iterating until the vector has one element (keeping track of how it was achieved, of course). If its value is an integer and it has not been seen before, the generating expression is output. Not strict, but does the job. I take it that my percentages match yours, right?
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: 1 3 5 7 9
« Reply #19 on: Feb 7th, 2005, 6:30am » |
Quote Modify
|
They're very close, but not quite the same as mine. I get:
358/1260~=28.413% for 1, 3, 5, 7, 9
78/384=20.3125% for 0, 2, 4, 6, 8
121/180=67.222...% for 1, 2, 3, 4, 5
31/36=86.111...% for 1, 2, 3, 4
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 1 3 5 7 9
« Reply #20 on: Feb 7th, 2005, 8:40am » |
Quote Modify
|
I've included 0 as well. 359/1261, etc. I thought that giving 4 significant digits of the percentages will allow to find out the cause of the possible discrepancy.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove