Large Numbers

How can we build a large number ?

Let us start with addition, the simplest operation with two numbers. If we have two numbers a and b, we can build a third number c = a + b by adding a and b. This number c is greater than a and than b.

Then we can add repetitively a to itself b times : a + a + ... + a. This is called the product a * b. It can be defined recursively :

a * 1 = a
a * (b+1) = (a * b) + a

We can consider the operation "*" as the result of a "meta-operation" (an operation on operations) applied to the operation "+", this meta-operation consisting in iterating the original operation, and write it "* = ,+" where "," represents the iteration meta-operation. So we have a * b = a ,+ b.

We can go on by iterating the product : a * a * ... * a with a repeated b times. This is the exponentiation a^b, and the exponentiation is the iteration of the product : ^ = ,* = ,,+ which we can write more simply 2,+.

If we want to iterate exponentiation, we must be careful because it is not commutative and we have for example (a^a)^a = a^(a*a) = a^(a^2). So we get larger numbers if we apply exponentiation from right to left and we define an operation called "tetration" by a^^b = a^(a^(a^(...^(a^a)))) with a repeated b times. We have ^^ = ,^ = ,,,+ = 3,+.

We can define very large numbers starting with addition and repetitively iterating it a large number of times, and applying it to some large numbers, for example : 1000 1000,+ 1000.

The number of times we apply the iteration meta-operator to addition can itself be built this way, giving successively :

1000 1000,+ 1000
1000 (1000 1000,+ 1000),+ 1000
1000 (1000 (1000 1000,+ 1000),+ 1000),+ 1000
...

We will introduce another meta-operator called "nesting", represented by "@" and defined by (where # represents any operator) :

a @# 1 = a
a @# 2 = a a,# a
a @# 3 = a (a a,# a) a
...
a @# (b+1) = a (a @# b),# a

With this notation we have :

1000 = 1000 @+ 1
1000 1000,+ 1000 = 1000 @+ 2
1000 (1000 1000,+ 1000),+ 1000 = 1000 @+ 3
1000 (1000 (1000 1000,+ 1000),+ 1000),+ 1000 = 1000 @+ 4
...

Here is a Haskell definition of these notations :

module Main where

 add a b = a + b

 iter 0 x a b = x a b
 iter (n+1) x a 1 = a
 iter (n+1) x a (b+1) = iter n x a (iter (n+1) x a b)

 nest x a 1 = a
 nest x a (b+1) = iter (nest x a b) x a a

There is a correspondence between these notations and other notations invented by Jonathan Bowers called Extended Operator Notation and Array Notation or Bower Exploding Array Function defined by the following rules :

Rule 1: Condition - only 1 or 2 entries - {a} = a, {a,b} = a+b. (in other words take the sum of the entries).
Rule 2: Condition - last entry is 1 - {a,b,c,...,k,1} = {a,b,c,...,k} (in other words remove trailing 1's).
Rule 3: Condition - 2nd entry is 1 - {a,1,c,d,..,k} = a.
Rule 4: Condition - 3rd entry is 1 - {a,b,1,..,1,d,e,..,k} = {a,a,a,..,{a,b-1,1,..,1,d,e,..,k},d-1,e,..,k} - the ".." between the 1's represent 1's - there can be any number of ones, from 1 "1" (3rd entry alone) to a string of 1s - the last 1 of this string is what becomes {a,b-1,1,..,1,d,e,..,k} all entries prior becomes "a". For an array like this{3,2,1,1,1,5,1,2} the last 1 in the string is the one before the 5 (not the one after - since it is a different string of 1s).
Rule 5: Condition - Rules 1-4 doesn't apply - {a,b,c,d,...,k} = {a,{a,b-1,c,d,...,k},c-1,d,..,k}.

Bowers extended operator notation is related to his array notation in this way:

a {c} b = {a,b,c}, where c=1,2,3,4,5 etc represents adding, multiplying, exponentiation, tetration, pentation, etc. (I first encountered the names tetration, pentation, etc. in a book which I no longer remember the name).
a {{c}} b = {a,b,c,2}
a {{{c}}} b = {a,b,c,3} etc.
a {{1}} b = a { a { a....a { a { a } a } a.... a } a } a (b a's from center out) - I call this a expanded to b
a {{2}} b = a expanded to itself b times (or a multiexpanded to b) = a {{1}} (a {{1}} (a {{1}} (a .... (b times)
a {{3}} b = a multiexpanded to itself b times (or a powerexpanded to b)
a {{4}} b = a powerexpanded to itself b times (or a expandotetrated to b)
etc.
a {{{1}}} b = a {{ a {{ a ... a {{ a {{ a }} a }} a ... a }} a }} a ( b a's from center out) - I call this a exploded to b.
a {{{2}}} b = a exploded to itself b times (a multiexploded to b)
a {{{3}}} b = a multiexploded to itself b times (a powerexploded to b)
a {{{4}}} b = a powerexploded to itself b times (a explodotetrated to b)
etc.

For example, we have :

{a,b,c} = a {c} b = a (c-1),+ b
a {{1}} b = {a,b,1,2} = a {a { ... a {a} a ... } a} a with b levels of nesting < a @+ b
a {{2}} b = {a,b,2,2} = a {{1}} (a {{1}} ... {{1}} a) with a repeated b times = a ,{{1}} b < a ,@+ b
a {{3}} b = {a,b,3,2} = a {{2}} (a {{2}} ... {{2}} a) with a repeated b times = a ,{{2}} b < a ,,@+ b = a 2,@+ b
a {{c}} b = {a,b,c,2} < a (c-1),@+ b
a {{{1}}} b = {a,b,1,3} = a {{ a {{ ... a {{ a }} a ... }} a }} a with b levels of nesting < a @@+ b
a {{{2}}} b = {a,b,2,3}= a {{{1}}} (a {{{1}}} ... {{{1}}} a) with a repeated b times = a ,{{{1}}} b < a ,@@+ b
a {{{3}}} b = {a,b,3,3} = a {{{2}}} (a {{{2}}} ... {{{2}}} a) with a repeated b times = a ,{{{2}}} b < a ,,@@+ b = a 2,@@+ b
a {{{c}}} b = {a,b,c,3} <f a (c-1),@@+ b

Links about Bowers notation :