Knuth's arrow notation

This article page is a stub, please help by expanding it.

This article describes Knuth's up-arrow notation to represent iterated exponentiation with base 

b

(power towers with base 

b

) and a down-arrow notation to represent the iterated logarithm (with base 

b

) inverse of iterated exponentiation.

Knuth's up-arrow notation

In 1976, Donald Knuth introduced the following up-arrow notation for power towers

$p=b\uparrow ^{n}d=b\uparrow ^{n-1}[b\uparrow ^{n}(d-1)],\quad n\geq 2,\,$

with

$b\uparrow ^{1}d:=b^{d},\,$

$b\uparrow ^{n}0:=1,\,$

where 

d

is the order of the power tower with base 

b

, and 

p

is the result of the power tower evaluation.

Down-arrow notation

The down-arrow notation defines a logarithmic-type inverse of the up-arrow notation

$d=b\downarrow ^{n}p:=\log _{b}^{*}p,\,$

where 

log ⁎b p

is the number of iterations of the logarithm (base 

b

) required such that 

log ⁎b p   ≤   b

.

In particular, we have

$d=e\downarrow ^{n}p:=\log _{e}^{*}p=\log ^{*}p,\,$

where 

log ⁎ p

is the number of iterations of the natural logarithm required such that 

log ⁎ p   ≤   e

.

Now, if we have

$p=b\uparrow ^{n}d,\quad d\geq 1,\,$

then

$d=b\downarrow ^{n}p,\,$

where 

d

is a positive integer. How could we generalize 

d

to integers, rational numbers, real numbers or complex numbers for all 

n

? For 

n = 1

, we do have a generalization.

See also

• Large numbers

Hierarchical list of operations pertaining to numbers

0^th iteration

• Successor: 

  S(n)

  .
• Predecessor: 

  P(n)

  .

1^st iteration

• Addition: 

  S(S(⋯ "a times" ⋯ (S(n))))

  , the sum 

  n  +  a

  , where 

  n

  is the augend and 

  a

  is the addend. (When addition is commutative both are simply called terms.)
• Subtraction: 

  P(P(⋯ "s times" ⋯ (P(n))))

  , the difference 

  n  −  s

  , where 

  n

  is the minuend and 

  s

  is the subtrahend.

2^nd iteration

• Multiplication: 

  n + (n + (⋯ "k times" ⋯ (n + (n))))

  , the product 

  m  ⋅   k

  , where 

  m

  is the multiplicand and 

  k

  is the multiplier. (When multiplication is commutative both are simply called factors.)
• Division: the ratio 

  n  /  d

  , where 

  n

  is the dividend and 

  d

  is the divisor.
  • Quotient: (integer division).
  • Remainder: (modulo and congruences).

3^rd iteration

• Exponentiation ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Powers: 

    n  ⋅   (n  ⋅   (⋯ "d times" ⋯ (n  ⋅   (n))))

    , written 

    n d

    .
  • Exponentials: 

    b  ⋅   (b  ⋅   (⋯ "n times" ⋯ (b  ⋅   (b))))

    , written 

    b n

    .
    • Exponential function: 

      e n

      , where 

      e

      is Euler's number.
• Exponentiation inverses ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Roots: 

    d √  n

    .
  • Logarithms: 

    logb n

    .
    • Natural logarithm function: 

      log n

      , or 

      loge n

      , where 

      e

      is Euler's number.

4^th iteration

• Tetration ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Tetra-powers (super-powers): 

    n ^ (n ^ (⋯ "d times" ⋯ (n ^ (n))))

    , written 

    n ^^ d or n ↑↑ d

    .
  • Tetra-exponentials (super-exponentials): 

    b ^ (b ^ (⋯ "n times" ⋯ (b ^ (b))))

    , written 

    b ^^ n or b ↑↑ n

    .
• Tetration inverses ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Tetra-roots (super-roots)
  • Tetra-logarithms (super-logarithms): 

    slogb n

    .
    • Iterated logarithm: 

      log ⁎b n = ⌈slogb n⌉

      .

5^th iteration

• Pentation ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Penta-powers: 

    n ^^ (n ^^ (⋯ "d times" ⋯ (n ^^ (n ^^ (n)))))

    , written 

    n ^^^ d or n ↑↑↑ d

    .
  • Penta-exponentials: 

    b ^^ (b ^^ (⋯ "n times" ⋯ (b ^^ (b ^^ (b)))))

    , written 

    b ^^^ n or b ↑↑↑ n

    .
• Pentation inverses
  • Penta-roots
  • Penta-logarithms

6^th iteration

• Hexation ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Hexa-powers: 

    n ^^^ (n ^^^ (⋯ "d times" ⋯ (n ^^^ (n))))

    , written 

    n ^^^^ d or n ↑↑↑↑ d

    .
  • Hexa-exponentials: 

    b ^^^ (b ^^^ (⋯ "n times" ⋯ (b ^^^ (b))))

    , written 

    b ^^^^ n or b ↑↑↑↑ n

    .
• Hexation inverses
  • Hexa-roots
  • Hexa-logarithms

7^th iteration

• Heptation ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Hepta-powers: 

    n ^^^^ (n ^^^^ (⋯ "d times" ⋯ (n ^^^^ (n))))

    , written 

    n ^^^^^ d or n ↑↑↑↑↑ d

    .
  • Hepta-exponentials: 

    b ^^^^ (b ^^^^ (⋯ "n times" ⋯ (b ^^^^ (b))))

    , written 

    b ^^^^^ n or b ↑↑↑↑↑ n

    .
• Heptation inverses
  • Hepta-roots
  • Hepta-logarithms

8^th iteration

• Octation ( 

  d

  as "degree", 

  b

  as "base", 

  n

  as "variable").
  • Octa-powers: 

    n ^^^^^ (n ^^^^^ (⋯ "d times" ⋯ (n ^^^^^ (n))))

    , written 

    n ^^^^^^ d or n ↑↑↑↑↑↑ d

    .
  • Octa-exponentials: 

    b ^^^^^ (b ^^^^^ (⋯ "n times" ⋯ (b ^^^^^ (b))))

    , written 

    b ^^^^^^ n or b ↑↑↑↑↑↑ n

    .
• Octation inverses
  • Octa-roots
  • Octa-logarithms

External links

• Knuth's up-arrow notation—Wikipedia.org.