Author |
Topic: Unusual Number Game 2.0 (Read 2016 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Unusual Number Game 2.0
« on: May 25th, 2005, 3:11am » |
 Quote  Modify
|
In another thread, Barukh described a game between you and a computer:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1115227155
(I don't know how to do that thing where the name is the link...)
Anyway, we found out that the computer always won. However, you discover that in practice, you can just name a big number, and the computation takes so long that the computer just gives up in frustration. Sick of losing, the computer gets itself one of them new-fangled "dual-core" chips. Now, the computer can evaluate the Goodstein sequence of the biggest number you can think of!
Well, you aren't going to take this lying down, so you invent a new game, using the generalized Ackermann function instead of exponentiation.
The generalized Ackermann function is defined by:
Ack (0, y, z) = y + z.
Ack (1, y, 0) = 0
Ack (x + 2, y, 0) = 1.
Ack (x + 1, y, z + 1) = Ack (x, y, Ack (x + 1, y, z)).
Note that
Ack (1, y, z) = y * z.
Ack (2, y, z) = y ^ z.
Ack (3, y, z) = (y ^ (y ^ ... (y ^ y) ... )) with z y's.
There are many ways of representing a number in terms of the Ackermann function. We'll describe three methods:
Method 1:
Given a number n and a base b, if n > b, pick the largest x, and then the largest y > 2, such that n >= Ack (x, b, y). Write n = Ack (x, b, y) + m, and then recursively apply the same process to x, y, and m for any of them that are greater than b. That is, if R(n,b) stands for the representation of n in base b, then
R(n,b) = Ack (R(x,b), b, R(y, b)) + R(m, b)
Method 2:
We pick x and y the same way; then, if n >= Ack (1, b, Ack (x, b, y)), let x2 be the largest integer such that n >= Ack (x2, b, Ack (x, b, y)). Continue in this fashion for larger xi, until we can no longer continue without exceeding n. Let m be the remainder again, and recursively apply the algorithm to x, y, m, and all xi until all numbers in the representation are less than or equal to b. Hence,
R(n, b) = Ack (R(xi, b), b, Ack (R(xi-1, b), b, ... Ack (R(x, b), b, R(y, b) ) ... ) + R(m, b)
Method 3:
Similar to method 2, but instead we choose the maximum x2 and y2 so that n >= Ack (x2, Ack (x, b, y), y2), and continue in this fashion. So we have
R(n, b) = Ack (R(xi, b), Ack (R(xi-1, b), ... Ack (R(x, b), b, R(y, b) ), ... ), R(yi-1) ), R(yi) ) + R(m, b).
Again, recurse over all numbers that are greater than b, until there are none.
The game is played the same way as before - we start by representing the game in base 2. Each step, we bump the base up by 1, and subtract 1 from the new number.
So, we have two questions, for each of the above three methods:
1. Does the sequence eventually come to an end, for any starting n?
2. How long is the sequence, as a function of n?
|
| « Last Edit: May 28th, 2005, 7:49am by Deedlit » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2873
|
|
Re: Unusual Number Game 2.0
« Reply #1 on: May 25th, 2005, 9:46am » |
Quote Modify
|
Just looking at your definition of Ack(x,y,z):
Ack(0,y,0) = Ack(0,y,z=0) = y+0 = y
Ack(0,y,0) = Ack(x=0,y,0) = 1
So what happens when y=1 doesn't hold?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Unusual Number Game 2.0
« Reply #2 on: May 25th, 2005, 10:43am » |
Quote Modify
|
So, Prof. Deedit, I guess it's time for us to try to apply our new knowledge of ordinal hierarchies from the other thread, eh? 
I'm still trying to digest the problem statement--a few clarifications:
Quote:Where x >= 1, right?
Quote:| Method 1: ...the largest x, and then the largest y > 2, such that... |
|
Can y be 2 if b > 2?
Quote:| Method 1: ...then recursively apply the same process to b, y, and m |
|
You meant x, y, and m (as the example would seem to indicate), right?
Quote:| Method 3: Similar to method 3... |
|
Erm, similar to method 2? (or did you mean 1? does it even matter?)
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Unusual Number Game 2.0
« Reply #3 on: May 25th, 2005, 11:12am » |
Quote Modify
|
on May 25th, 2005, 9:46am, rmsgrey wrote:Just looking at your definition of Ack(x,y,z):
Ack(0,y,0) = Ack(0,y,z=0) = y+0 = y
Ack(0,y,0) = Ack(x=0,y,0) = 1
So what happens when y=1 doesn't hold? |
|
Yeah, I should have said x + 1 for the second statement (x, y, z are all nonnegative integers)
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Unusual Number Game 2.0
« Reply #4 on: May 25th, 2005, 11:47am » |
Quote Modify
|
on May 25th, 2005, 10:43am, SMQ wrote:So, Prof. Deedit, I guess it's time for us to try to apply our new knowledge of ordinal hierarchies from the other thread, eh? ;D
|
|
Something like that, except I'm being a poor professor here. This is too challenging for an exercise, but I posted it because it's the problem I found interesting. ;D
I'm still trying to digest the problem statement--a few clarifications:
Quote:
It looks like you found the reason for the y > 2 restriction - it's that Ack(x, 2, 2) = 4 for all x, so there would be no maximum x in that case. So we could allow y = 2 for b > 2, but I left it out to avoid adding complexity. But let's go ahead and allow y=2 if b > 2. :)
Quote:| You meant x, y, and m (as the example would seem to indicate), right? |
|
Er, yes. Basically, recurse on everything bigger than b.
Quote:| Erm, similar to method 2? (or did you mean 1? does it even matter?) |
|
Oops again. Similar to the other two methods. :)
Perhaps some examples will help. (and not screwing up might help as well.)
Let's say we have a number n. The largest pair (x,y) we can find base 2 is (132, 5498), because
n < Ack (133, 2, 3)
n < Ack (132, 2, 5499)
n >= Ack (132, 2, 5498)
So, using method 1, we write
n = Ack (132, 2, 5498) + 2340932
Recursing on x, y, and m, we get
n = Ack (Ack(3, 2, 3) + 116, 2, Ack(3, 2, 3) + 5482) + Ack(4, 2, 3) + 2275396
Recursing again gives
n = Ack (Ack (Ack (0, 2, 1), 2, Ack (0, 2, 1) ) + Ack (3, 2, 3) + 100, 2, Ack (Ack (0, 2, 1), 2, Ack (0, 2, 1) ) + Ack (3, 2, 3) + 5466) + Ack (Ack (0, 2, 2), 2, Ack (0, 2, 1)) + Ack(4, 2, 3) + 2209860
(I should have said that y <= 2 is allowed when x = 0.)
For method 2, say we have a different n, but (132, 5498) is still the highest pair we can pick. We don't just subtract yet - next we see if there is some lower Ackermann function we can use with y as set to Ack (132, 2, 5498). Say x2 = 127 is the maximum value, meaning
n < Ack (128, 2, Ack (132, 2, 5498) )
n >= Ack (127, 2, Ack (132, 2, 5498) )
we then see what the highest value of x > 0 we can use with y = Ack (127, 2, Ack (132, 2, 5498) ). (I forgot to exclude x = 0 in the description) We keep going until even x = 1 doesn't work. Then we write n as a succession of nested Ackermann functions, plus a remainder, then recurse on all values bigger than 2.
Method 3 is similar, the previous number goes into the b value of the next Ackermann function. So, we want the highest value of x, then y, such that
n >= Ack (x, Ack (132, 2, 5498), y)
Say it's (127, 834) (meaning (128, 2) and (127, 835) are too big). Then we next want to find (x, y) such that
n >= Ack (x, Ack (127, Ack (132, 2, 5498), 834), y)
we keep going until even x = 1, y = 2 is too big. So we right n as another set of nested Ackermann functions, this time over the middle variable, plus some remainder, then we recurse over all numbers bigger than b.
|
| « Last Edit: May 25th, 2005, 11:53am by Deedlit » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unusual Number Game 2.0
« Reply #5 on: May 25th, 2005, 5:00pm » |
Quote Modify
|
on May 25th, 2005, 3:11am, Deedlit wrote:| (I don't know how to do that thing where the name is the link...) |
|
Code:| [url=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1115227155]Another (unusual) Number Game[/url] |
|
gives the link Another (unusual) Number Game
A good trick for finding out how something is done is to find a post it was done in, and "Quote" the post. In the message window, you will see the post as originally entered (except for any quotes in it). After you've seen it, just back out of the post window, instead of posting.
Actually, I was surprised to see that you hadn't used the url tags at all. In the old version of YaBB, you had to use them to post a link, but the "default" link the buttons would give you was of the form [ url ]address[ /url ], which would display the address just as yours was. Apparently, the new version of YaBB automatically recognizes addresses and displays them as links.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Unusual Number Game 2.0
« Reply #6 on: May 26th, 2005, 5:27am » |
Quote Modify
|
Just nit-picking the definition of the generalised Ackermann function a little further - the definition as given gives:
Ack(1,y,z)=y*z+1
Ack(2,y,z)=y^z+y^(z-1)+y^(z-2)+...+y+1
And I assume even more interesting things happen for higher x.
Some quick research turns up the correct boundary conditions for the nice forms for constant x:
Ack (0, y, z) = y + z.
Ack (1, y, 0) = 0
Ack (x + 2, y, 0) = 1.
Ack (x + 1, y, z + 1) = Ack (x, y, Ack (x + 1, y, z)).
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Unusual Number Game 2.0
« Reply #7 on: May 26th, 2005, 7:16am » |
Quote Modify
|
Ugh!  Yes, thank you, rmsgrey. I hope the mistakes don't kill off this thread. 
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Unusual Number Game 2.0
« Reply #8 on: May 28th, 2005, 5:37am » |
Quote Modify
|
Hmm, within the given rules--without sometimes allowing y < 2--there doesn't seem to be any notation for n < b + 2.
1) There is no representation of the number 1 within the given rules--Ack(x, b, y) = 1 implies x > 1 and y = 0.
2) Without a representation for 1 there is no representation for 1 <= n < b within the rules--Ack(x, b, y) is never > 1 and < b.
3) There is no representation for b within the rules--Ack(x, b, y) = b implies either x = y = 0 or y = 1.
I propose, therefore, the following change: Given a number n and a base b, pick the largest x, then the largest y > 2, such that n >= Ack(x, b, y) smallest x such that n < Ack(x+1, b, (3 if b = 2, 2 otherwise)) and there exists y such that 0 < Ack(x, b, y) <= n < Ack(x, b, y+1).
Now we have:
1 = Ack(2, b, 0)
1 < n < b = 1 + 1 + ... + 1 with n 1's
b = Ack(0, b, 0)
b + m < 2b = Ack(0, b, m)
2b = Ack(1, b, 2)
etc.
Alternatively, for n < b, we could choose any Ack(0, m, n - m): m <= n which would eliminate the long string of 1's ugliness without materially affecting the problem statement...
--SMQ
|
| « Last Edit: May 28th, 2005, 5:44am by SMQ » |
IP Logged |
--SMQ
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Unusual Number Game 2.0
« Reply #9 on: May 28th, 2005, 6:59am » |
Quote Modify
|
Hmmmm... I was just going to leave all numbers less than or equal to b as they are (I'll emphasize that in the original post). It looks like your modification results in the same procedures - anything less than b gets fixed by the base bumping. So whatever you like the best should be fine. 
|
| « Last Edit: May 28th, 2005, 7:48am by Deedlit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print