Main Page | See live article | Alphabetical index

Conway chained arrow

Conway's chained arrow notation is a means of expressing certain large numbers. It is simply a finite sequence of positive integers separated by rightward arrows, eg 2→3→4→5→6

Table of contents
1 Interpretation/Expansion
2 Simple examples
3 More typical examples
4 See also
5 External

Interpretation/Expansion

One must be careful to treat an arrow chain as a whole. Whereas chains of other infixed symbols (eg 3+4+5+6+7) can often be considered in fragments (eg (3+4)+5+(6+7)) without a change of meaning (see associativity), that is not so with Conway's arrow.

As with most combinatorial symbologies, the definition is recursive. Here, p and q are positive integers, and X is a chain (possibly of only one element) substituted textually.

(1) A chain X→p→(q+1) of more than 2 elements not ending in 1 is the same as
   X→(X→(...X→(X)→q...)→q)→q (with p copies of X).
(2) A chain ending in 1 is unchanged by dropping that 1. X→1 = X
(3) 2-element chains terminate in exponentiation. p→q = pq
The last two rules do not conflict, since p→1 = p¹ = p

The first rule is the core: A chain of 3 or more elements ending with 2 or higher becomes a chain of the same length with a (usually vastly) increased penultimate element. But its ultimate element is decremented, eventually permitting the second rule to shorten the chain. After, to paraphrase Knuth, "much detail," the chain is reduced to two elements and the third rule terminates the recursion.

Knuth's arrow and the hyper operators equate to 3-element chains:

p→q→r = hyper(p,r+2,q) = p^…^q with r up-arrows.

Simple examples

It is impossible to give a fully worked-out interesting example since at least 4 elements are required. However 1-, 2- and 3-length chains, which are subsumed in other notations, are expanded here as illustrated examples.

n

any single integer n is just the value n, ie 7 = 7. This does not conflict with the rules since using rule 2 (backwards) then rule 3 we have 7 = 7→1 = 71 = 7.

p→q
= pq (by rule 3)
Thus 3→4 = 34 = 81
Also 123456→1 = 1234561 = 123456 (by both rules 2 and 3)

1→(any arrowed expression)
= 1 since the entire expression eventually reduces to 1number = 1
(Indeed, any chain containing a 1 can be truncated just before that 1; ie X→1→Y=X for any (embedded) chains X,Y.)

4→3→2

= 4→(4→(4)→1)→1 (by 1) and then, working from the inner parentheses outwards,
= 4→(4→4→1)→1 (remove redundant parentheses [rrp])
= 4→(4→4)→1 (2)
= 4→(256)→1 (3)
= 4→256→1 (rrp)
= 4→256 (2)
= 1.34078079299e+154 approximately (3)

4→3→2 alternatively analysed
= 4→(4→(4)→1)→1 (by 1) and then, removing trailing "→1",
= 4→(4→(4)→1) (2)
= 4→(4→(4)) (2)
= 4→(256) (rrp, 3)
= 1.34078079299e+154 approximately (rrp, 3)

2→2→4
= 2→(2)→3 (by 1)
= 2→2→3 (rrp)
= 2→2→2 (1, rrp)
= 2→2→1 (1, rrp)
= 2→2 (2)
= 4 (3) (In fact any chain beginning with two 2s stands for 4.)

2→4→3
= 2→(2→(2→(2)→2)→2)→2 (by 1) The four copies of X (which is 2 here) are in bold to distinguish them from the 2 which is q)
= 2→(2→(2→2→2)→2)→2 (rrp)
= 2→(2→(4)→2)→2 (previous example)
= 2→(2→4→2)→2 (rrp) (expression expanded in next equation shown in bold on both lines)
= 2→(2→(2→(2→(2)→1)→1)→1)→2 (1)
= 2→(2→(2→(2→2→1)→1)→1)→2 (rrp)
= 2→(2→(2→(2→2)))→2 (2 repeatedly)
= 2→(2→(2→(4)))→2 (3)
= 2→(2→(16))→2 (3)
= 2→256→2 (3,rrp)
= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (1) with 256 sets of parentheses
= 2→(2→(2→(...2→(2→(2))...)))) (2 repeatedly)
= 2→(2→(2→(...2→(4))...)))) (3)
= 2→(2→(2→(...16...)))) (3)
= 2→(very large power of 2) (3 repeatedly)
= very very big number

2→3→2→2
= 2→3→(2→3)→1 (by 1)
= 2→3→8 (2 and 3)
= 2→(2→2→7)→7 (1)
= 2→4→7 (supra)
= 2→(2→(2→2→6)→6)→6 (1)
= 2→(2→4→6)→6 (supra)
= gonna be huge but needs a couple more steps

3→2→2→2
= 3→2→(3→2)→1 (1)
= 3→2→9 (2 and 3)
= 3→3→8 (1)
= huge

More typical examples

Conway's arrow doesn't help to express Graham's number G succinctly, but:
3→3→64→2 < G < 3→3→65→2
Applying the first rule above,
3→3→64→2 = 3→3→(3→3→(...3→3→(3→3)→1...)→1)→1 with 128 threes.
Applying the second rule,
3→3→64→2 = 3→3→(3→3→(...3→3→(3→3)...))
If, for convenience, we define f(n)=3→3→n then
3→3→64→2 = f64(1) (see functional powers),
G=f64(4), and
3→3→65→2 = f65(1) = f64(27)
Since f is strictly increasing,
f64(1) < f64(4) < f64(27)
which is the given inequality.

Note that 3→3→3→3 is much greater than Graham's number.

See also

External