This site is supported by donations to The OEIS Foundation.

# Knuth's arrow notation

(Redirected from Down-arrow notation)

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

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

with

${\displaystyle b\uparrow ^{1}d:=b^{d},\,}$
${\displaystyle 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

${\displaystyle 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

${\displaystyle 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

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

then

${\displaystyle 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.

#### Hierarchical list of operations pertaining to numbers [1] [2]

##### 1st 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.
##### 2nd iteration
• Multiplication:  n + (n + (⋯ "k times" ⋯ (n + (n))))
, the product  m  ⋅   k
, where  m
is the multiplicand and  k
is the multiplier.[3] (When multiplication is commutative both are simply called factors.)
• Division: the ratio  n  /  d
, where  n
is the dividend and  d
is the divisor.
##### 3rd 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
.
• Exponentiation inverses ( d
as "degree",  b
as "base",  n
as "variable").
##### 5th 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
##### 6th 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
##### 7th 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
##### 8th 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

## Notes

1. There is a lack of consensus on which comes first. Having the multiplier come second makes it consistent with the definitions for exponentiation and higher operations. This is also the convention used with transfinite ordinals:
 ω  ×  2 := ω  +  ω
.