wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Unusual Number Game 2.0
        
(Message started by: Deedlit on May 25^th, 2005, 3:11am)

Title: Unusual Number Game 2.0
Post by Deedlit on May 25^th, 2005, 3:11am

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_hard;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 x₂ be the largest integer such that n >= Ack (x₂, 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_i-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 x₂ and y₂ so that n >= Ack (x₂, Ack (x, b, y), y₂), and continue in this fashion. So we have

R(n, b) = Ack (R(x_i, b), Ack (R(x_i-1, b), ... Ack (R(x, b), b, R(y, b) ), ... ), R(y_i-1) ), 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?

Title: Re: Unusual Number Game 2.0
Post by rmsgrey on May 25^th, 2005, 9:46am

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?

Title: Re: Unusual Number Game 2.0
Post by SMQ on May 25^th, 2005, 10:43am

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

I'm still trying to digest the problem statement--a few clarifications:

Quote:

Ack (x, y, 0) = 1

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

Title: Re: Unusual Number Game 2.0
Post by Deedlit on May 25^th, 2005, 11:12am

on 05/25/05 at 09:46:04, 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)

Title: Re: Unusual Number Game 2.0
Post by Deedlit on May 25^th, 2005, 11:47am

on 05/25/05 at 10:43:56, 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:

Can y be 2 if b > 2?

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₂ = 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.

Title: Re: Unusual Number Game 2.0
Post by Icarus on May 25^th, 2005, 5:00pm

on 05/25/05 at 03:11:14, 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1115227155)

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.

Title: Re: Unusual Number Game 2.0
Post by rmsgrey on May 26^th, 2005, 5:27am

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

Title: Re: Unusual Number Game 2.0
Post by Deedlit on May 26^th, 2005, 7:16am

Ugh! :-[ Yes, thank you, rmsgrey. I hope the mistakes don't kill off this thread. :(

Title: Re: Unusual Number Game 2.0
Post by SMQ on May 28^th, 2005, 5:37am

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

Title: Re: Unusual Number Game 2.0
Post by Deedlit on May 28^th, 2005, 6:59am

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. :)