Author 
Topic: Unusual Number Game 2.0 (Read 2026 times) 

Deedlit
Senior Riddler
Posts: 476


Unusual Number Game 2.0
« on: May 25^{th}, 2005, 3:11am » 
Quote Modify

In another thread, Barukh described a game between you and a computer: http://www.ocf.berkeley.edu/~wwu/cgibin/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 newfangled "dualcore" 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 x_{2} be the largest integer such that n >= Ack (x_{2}, b, Ack (x, b, y)). Continue in this fashion for larger x_{i}, 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 x_{i} until all numbers in the representation are less than or equal to b. Hence, R(n, b) = Ack (R(x_{i}, b), b, Ack (R(x_{i1}, 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 x_{2} and y_{2} so that n >= Ack (x_{2}, Ack (x, b, y), y_{2}), and continue in this fashion. So we have R(n, b) = Ack (R(x_{i}, b), Ack (R(x_{i1}, b), ... Ack (R(x, b), b, R(y, b) ), ... ), R(y_{i1}) ), R(y_{i}) ) + 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 28^{th}, 2005, 7:49am by Deedlit » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Unusual Number Game 2.0
« Reply #1 on: May 25^{th}, 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 25^{th}, 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 statementa 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 25^{th}, 2005, 11:12am » 
Quote Modify

on May 25^{th}, 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 25^{th}, 2005, 11:47am » 
Quote Modify

on May 25^{th}, 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 statementa 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 x_{2} = 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 25^{th}, 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 25^{th}, 2005, 5:00pm » 
Quote Modify

on May 25^{th}, 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/cgibin/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 26^{th}, 2005, 5:27am » 
Quote Modify

Just nitpicking 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^(z1)+y^(z2)+...+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 26^{th}, 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 28^{th}, 2005, 5:37am » 
Quote Modify

Hmm, within the given ruleswithout sometimes allowing y < 2there doesn't seem to be any notation for n < b + 2. 1) There is no representation of the number 1 within the given rulesAck(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 rulesAck(x, b, y) is never > 1 and < b. 3) There is no representation for b within the rulesAck(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 28^{th}, 2005, 5:44am by SMQ » 
IP Logged 
SMQ



Deedlit
Senior Riddler
Posts: 476


Re: Unusual Number Game 2.0
« Reply #9 on: May 28^{th}, 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 28^{th}, 2005, 7:48am by Deedlit » 
IP Logged 



