Insanly huge number puzzles/challenges

Challenges are way down at the bottom.

I've just read http://public.logica.com/~stepneys/cyc/b/big.htm And decided to make up a few symbols:

Here's a condensed version of Knuth's up-arrow notation: K(m,n,0) = (m+m+m...) = m*n K(m,n,1) = (m*m*m...) = m^n K(m,n,2) = (m^m^m...) = m^^n Skewe's number = K(10,3,2)^34

Graham's number is G(63), where G(1) = K(3,3,K(3,3,4)) G(i) = K(3,3,G(i-1))

I don't understand Conway's chained arrow notation. Clearly, a -> b -> c = K(a,b,c), but what is a -> b -> c -> d supposed to mean? Someone help me, please.

However, I do think I can define Ackermann's function: A(0,n) = n+1 A(1,n) = 2+(n+3)-3 A(m,n) = K(2,(n+3),m-2)-3 I could eliminate the m=1 special case, by defining K(m,n,-1) = m+n, but I'm not sure I have justification for doing that. Also, I don't think I can see what to define for K(m,n,-2), etc.

Here's my version of Moser's polygon notation: M(n,1,1) = n^n M(n,x,y) = M(M(n,x,y-1),x,1) M(n,x,1) = M(n,x-1,n) Examples: M(n,1,2) = M(M(n,1,1),1,1) = M(n^n,1,1) = (n^n)^(n^n) M(n,1,3) = M(M(n,1,2),1,1) = M((n^n)^(n^n),1,1) = ((n^n)^(n^n))^((n^n)^(n^n)) M(n,2,1) = M(n,1,n) = M(M(n,1,n-1),1,1) = M(n,1,n-1)^M(n,1,n-1)

A polygon with M(2,3,1) sides is a zeldagon. Moser's number is M(2,M(2,3,1),1)

Graham's number is significantly larger than Moser's number.

Now, here're the challenges: 1) I defined Knuth's arrow notation descriptively, such that a human can see the progression. Can anyone describe it recursively or iteratively?

2) Can Moser's number be defined in terms of K? Recursion is allowed, but try to make it so there's only one self reference in the recursion step, as in the Graham's number definition.

3) For m1 = M(n1,x1,y1) and m2 = M(n2,x2,y2), and m1 <= G(63) <= m2, find the largest possible m1 and smallest possible m2. In writing the description, try avoiding writing integers larger than, say, 64, except as terms of M or K.

4) Justify defining K(m,n,-1) = m+n, besides simplifying using K for the Ackerman function.

5) Define K(m,n,-2) which is consistent with the Ackerman function for

[...] I've just read http://public.logica.com/~stepneys/cyc/b/big.htm And decided to make up a few symbols:

Here's a condensed version of Knuth's up-arrow notation: K(m,n,0) = (m+m+m...) = m*n K(m,n,1) = (m*m*m...) = m^n K(m,n,2) = (m^m^m...) = m^^n

The 'symbol forest' that grows when using notation like K() can be greatly reduced by using operator notation instead, e.g., just write the number of Knuth up-arrows in brackets:

m[k]n = m^^...^n (k up-arrows) = your K(m,n,k)

This gives a ladder of operators [0]=*, [1]=^, [2]=^^, etc, defined recursively by

m[0]n = m*n m[k]n = m[k-1]m[k-1]...m[k-1]m (n 'm's, n-1 operators) (*)

where m, n, and k are integers, m>0, n>0, k>0, and the operators are understood to group right-to-left.

Alternatively, (*) can be replaced by m[k]1 = m m[k]n = m[k-1](m[k](n-1)) (n>1)

In your notation, K(m,n,k) = K(m,..K(m,K(m,K(m,m,k-1),k-1),k-1),..,k-1) (where there are n 'm's and n-1 'K's), or alternatively K(m,n,k) = K(m,K(m,n-1,k),k-1) (n>1), etc.

Graham's number is G(63), where G(1) = K(3,3,K(3,3,4)) G(i) = K(3,3,G(i-1)) I don't understand Conway's chained arrow notation. Clearly, a -> b -> c = K(a,b,c), but what is a -> b -> c -> d supposed to mean? Someone help me, please.

Chained arrows are formally manipulated according to the following rules, which operate on the 'tail elements' (where, for convenience, I use ',' instead of '->':

a,...,x,1 = a,...,x (1) a,...,x,1,z = a,...,x (2) a,...,x,y,z = a,...,x,(a,...,x,y-1,z),z-1 (y>1) (3)

Rule (1) combines with Rules (2) & (3) to define chains longer than three, and the latter rules are needed to be consistent with the recursive definition above: m[k]1 = m m[k]n = m[k-1](m[k](n-1)) (n>1).

E.g., a,...,x,2,z = a,...,x,(a,...,x,1,z),z-1 by (3) = a,...,x,(a,...,x),z-1 by (2)

So (3) & (2) can be used repeatedly to reduce the final element to 1, which can then be omitted by (1), and the chain is eventually expressible in terms of (possibly deeply nested) triplets a,b,c = a[c]b.

Some examples:

a,b,c,1 = a,b,c = a[c]b by (1) a,b,c,2 = a,b,(a,b,c-1,2),1 by (3) = a,b,(a,b,c-1,2) by (2) = a,b,(a,b,(a,b,c-2)) etc ... = a,b,(a,b,(a,b,(...,(a,b,1,2)...))) = a,b,(a,b,(a,b,(...,(a,b,1)...))) (c 'a,b's)

Graham's number is g(64), with g(1) = 3,3,4 g(k) = 3,3,g(k-1) (k>1) i.e., g(64) = 3,3,(3,3,(...,(3,3,4))...)) (64 '3,3's)

On the other hand, the example for a,b,c,2 above gives 3,3,64,2 = 3,3,(3,3,(...,(3,3,1)...)) (64 '3,3's), and 3,3,65,2 = 3,3,(3,3,(...,(3,3,(3,3,1))...)) (65 '3,3's) 3,3,(3,3,(...,(3,3,27)...)) (64 '3,3's).

Therefore 3,3,64,2 < g(64) < 3,3,65,2 since 1 < 4 < 27.

Also, 3,3,3,3 is larger than any of these, since 3,3,3,3 = 3,3,(3,3,2,3),2 and 3,3,2,3 > 64.

[...] 1) I defined Knuth's arrow notation descriptively, such that a human can see the progression. Can anyone describe it recursively or iteratively?

(see above)

This is a [slightly] modified version of the earlier post, using the stuff r.e.s. explained to me.

Read http://public.logica.com/~stepneys/cyc/b/big.htm to see where i got these ideas.

The puzzles are way down at the bottom. I'd like all of you to at least try puzzle number 5, which is very easy (a proof by counterexample).

Here's an easier to read (I hope) version of Knuth's up-arrow notation, using recursion and operator notation for compactness: m[-1]n = m+n m[0]n = m*n m[k]1 = m m[k]n = m[k-1](m[k](n-1))

e.g.: m[1]3 = m[0](m[1]2) = m*(m[0](m[1]1)) = m*(m*(m)) = m^3 m[2]3 = m[0](m[1]2) = m^(m[0](m[1]1)) = m^(m^(m)) = m^^3

Graham's number is g(64), where: g(0) = 4 g(k) = 3[g(k-1)]3

Ackerman's function is A(0,n) = n + 1 A(m,n) = 2[m-2](n+3) - 3

Here's conway's chained notation, expressed with arrows as commas: a,b,c = a[c]b Longer chains are reduced as follows: a...x,1 = a...x a...x,1,z = a...x a...x,y,z = a...x,(a..x,y-1,z),(z-1)

e.g.: a...x,2,z = a...x,(a...x,1,z),z-1 = a...x,(a...x),z-1

3,3,64,2 < Graham's number < 3,3,65,2 < 3,3,3,3

Ackerman's function for (m>0) is A(m,n) = (2,(n+3),(m-2)) - 3

Here's Moser's polygonal notation: n{1}1 = n{1} = n^n n{1}m = (n{1}(m-1)){1} n{k}1 = n{k-1}n

A polygon with 2{3}1 sides is a zeldagon. Moser's number is 2{2{3}} = 2{256{1}256}

Graham's number is significantly larger than Moser's number.

Here're the puzzles/challenges:

(5) Prove that the function m[-2]n is an impossibility. This is easy.

(4) There is no puzzle 4.

(3) For x1 = n1{k1}m1, x2 = n2{k2}m2, and x1 <= g(64) <= x2, find the largest possible x1 and smallest possible x2.

(2) Can Moser's number be simply defined in [my version of] Knuth's arrow notation or Conway's chaining notation? A recursive definition is allowed (like Graham's number), but try to make it so there's no more than one self reference in the recursion step.

(1) There is no puzzle 1.

(0) Think of more puzzles!

[...] Here's an easier to read (I hope) version of Knuth's up-arrow notation, using recursion and operator notation for compactness: m[-1]n = m+n m[0]n = m*n m[k]1 = m

For consistency, I think m[k]1 should be

m[ k]1 = m if k &gt; -1 m[-1]1 = m+1 m[-2]1 = 2 (if I haven&#039;t erred below)

m[k]n = m[k-1](m[k](n-1)) (*)

. . . . . . . . . . . . . . . . .

[...] (5) Prove that the function m[-2]n is an impossibility. This is easy.

Well, maybe I&#039;ve missed something ...

Define m[-2]n = 1 + n. Then by the recursion (*) above, m[-1]n = m[-2]m[-1](n-1) = 1 + m[-1](n-1) = 1 + m[-2]m[-1](n-2) = 1 + 1 + m[-1](n-2) ... = (n-1) + m[-1]1 = n - 1 + m + 1 = m + n where we&#039;ve defined m[-1]1 = m + 1.

Continuing, m[0]n = m[-1]m[0](n-1) = m + m[0](n-1) = m + m + m[0](n-2) ... = m*(n-1) + m[0]1 = m*n where we&#039;ve defined m[0]1 = m.

Etc for [k] (k&gt;0), producing the ladder of operators [-1] = +, [0] = *, [1] = ^, ... .

Maybe a consistent [-3]1 should be

m[ k]1 = m if k > -1 m[-1]1 = m+1 m[-2]1 = 2 (if I haven't erred below)

m[k]n = m[k-1](m[k](n-1)) (*)

. . . . . . . . . . . . . . . . .

[...] (5) Prove that the function m[-2]n is an impossibility. This is easy.

Well, maybe I've missed something ...

Define m[-2]n = 1 + n. Then by the recursion (*) above, m[-1]n = m[-2]m[-1](n-1) = 1 + m[-1](n-1) = 1 + m[-2]m[-1](n-2) = 1 + 1 + m[-1](n-2) ... = (n-1) + m[-1]1 = n - 1 + m + 1 = m + n where we've defined m[-1]1 = m + 1.

Continuing, m[0]n = m[-1]m[0](n-1) = m + m[0](n-1) = m + m + m[0](n-2) ... = m*(n-1) + m[0]1 = m*n where we've defined m[0]1 = m.

Etc for [k] (k>0), producing the ladder of operators [-1] = +, [0] = *, [1] = ^, ... .

Maybe a consistent [-3] is impossible?

Wow, I never would have though of that.

The proof I was thinking of was to do something like: Because m[-1]n should be m+n, and 3[-1]1, calculated using the recurive step ends up as 3, when it should be 4, and 3 != 4, there is no way you can have m[-2]n.

The idea of having m[-2]n NOT having both m and n as its terms in the general case never occured to me.

So: m[-2]n = 1 + n m[-1]1 = m+1 m[ k]1 = m (for k &gt; -1) m[ k]n = m[k-1](m[k](n-1))

This produces m[-1]n = n+m, n[0]m = n*m, n[1]m = n^m, n[2]m = n^^m, etc.

Now about what r.e.s. said about k = -3: Is there any way that you can find m[-3]n such that: m[-2]n = 1 + n = m[-3]m[-2](n-1)

I think it&#039;s possible. Simple substitution results in: m[-2]n = 1 + n = m[-3]( 1+n-n ) = m[-3]n And we need a limiting case: m[-3]0 = 1

I think I see a pattern here! Putting things together: m[ k]1 = m (for k &gt; -1) m[-1]1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive 1 = m+1 m[ k]1 = m (for k > -1) m1 = m+1 m[ k]1 = m (for k &gt; -1) m[ k]n = m[k-1](m[k](n-1))

This produces m[-1]n = n+m, n[0]m = n*m, n[1]m = n^m, n[2]m = n^^m, etc.

Now about what r.e.s. said about k = -3: Is there any way that you can find m[-3]n such that: m[-2]n = 1 + n = m[-3]m[-2](n-1)

I think it&#039;s possible. Simple substitution results in: m[-2]n = 1 + n = m[-3]( 1+n-n ) = m[-3]n And we need a limiting case: m[-3]0 = 1

I think I see a pattern here! Putting things together: m[ k]1 = m (for k &gt; -1) m[-1]1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive 1 = m+1 m[ k]1 = m (for k > -1) m[ k]n = m[k-1](m[k](n-1))

This produces m[-1]n = n+m, n[0]m = n*m, n[1]m = n^m, n[2]m = n^^m, etc.

Now about what r.e.s. said about k = -3: Is there any way that you can find m[-3]n such that: m[-2]n = 1 + n = m[-3]m[-2](n-1)

I think it's possible. Simple substitution results in: m[-2]n = 1 + n = m[-3]( 1+n-n ) = m[-3]n And we need a limiting case: m[-3]0 = 1

I think I see a pattern here! Putting things together: m[ k]1 = m (for k &gt; -1) m[-1]1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any i0 = 1

I think I see a pattern here! Putting things together: m[ k]1 = m (for k > -1) m[-1]1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positiv1 = 1 + m m[ k]1 = 2 (for k < -1) m1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positiv1 = 1 + m m[ k]1 = 2 (for k < -1) m[ k]n = 1 + n (for k < -1) m1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positiv1 = 1 + m m[ k]1 = 2 (for k < -1) m1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positiv1 = 1 + m m[ k]1 = 2 (for k < -1) m[ k]n = 1 + n (for k < -1) m[ k]n = m[k-1](m[k](n-1)) (for k >= -1)

Well, we've got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

[...] Putting things together: m[ k]1 = m (for k &gt; -1) m[-1]1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

Formally, it&#039;s neat that all the operators (not just the ones for k &gt;= -1) are related by the above recursion. (For all k &lt; -1, the recursion reduces to m[k]n = 1 + n because of the condition m[k]1 = 2.)

On the other hand, all those below [-1] are really one and the same operator; that is, [-2] = [-3] = ..., since they all satify m[k]n = n+1; furthermore, this operator is unlike all the other Putting things together: m[ k]1 = m (for k > -1) m[-1]1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

Formally, it&#039;s neat that all the operators (not just the ones for k &gt;= -1) are related by the above recursion. (For all k &lt; -1, the recursion reduces to m[k]n = 1 + n because of the condition m[k]1 = 2.)

On the other hand, all those below [-1] are really one and the same operator; that is, [-2] = [-3] = ..., since they all satify m[k]n = n+1; furthermore, this operator is unlike all the others by not being t1 = 1 + m m[ k]1 = 2 (for k < -1) m1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

Formally, it&#039;s neat that all the operators (not just the ones for k &gt;= -1) are related by the above recursion. (For all k &lt; -1, the recursion reduces to m[k]n = 1 + n because of the condition m[k]1 = 2.)

On the other hand, all those below [-1] are really one and the same operator; that is, [-2] = [-3] = ..., since they all satify m[k]n = n+1; furthermore, this operator is unlike all the others by not being t1 = 1 + m m[ k]1 = 2 (for k < -1) m[ k]n = 1 + n (for k < -1) m1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

Formally, it&#039;s neat that all the operators (not just the ones for k &gt;= -1) are related by the above recursion. (For all k &lt; -1, the recursion reduces to m[k]n = 1 + n because of the condition m[k]1 = 2.)

On the other hand, all those below [-1] are really one and the same operator; that is, [-2] = [-3] = ..., since they all satify m[k]n = n+1; furthermore, this operator is unlike all the others by not being t1 = 1 + m m[ k]1 = 2 (for k < -1) m1 = 1 + m m[ k]1 = 2 (for k &lt; -1) m[ k]n = 1 + n (for k &lt; -1) m[ k]n = m[k-1](m[k](n-1)) (for k &gt;= -1)

Well, we&#039;ve got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

Formally, it&#039;s neat that all the operators (not just the ones for k &gt;= -1) are related by the above recursion. (For all k &lt; -1, the recursion reduces to m[k]n = 1 + n because of the condition m[k]1 = 2.)

On the other hand, all those below [-1] are really one and the same operator; that is, [-2] = [-3] = ..., since they all satify m[k]n = n+1; furthermore, this operator is unlike all the others by not being t1 = 1 + m m[ k]1 = 2 (for k < -1) m[ k]n = 1 + n (for k < -1) m[ k]n = m[k-1](m[k](n-1)) (for k >= -1)

Well, we've got rather alot more special cases to terminate the recursion, but I think our operator is quite fully defined, for k as any integer, positive or negative, and m, n as any positive integers.

Formally, it's neat that all the operators (not just the ones for k >= -1) are related by the above recursion. (For all k < -1, the recursion reduces to m[k]n = 1 + n because of the condition m[k]1 = 2.)

On the other hand, all those below [-1] are really one and the same operator; that is, [-2] = [-3] = ..., since they all satify m[k]n = n+1; furthermore, this operator is unlike all the others by not being truly dyadic