This site is supported by donations to The OEIS Foundation.

Knuth's arrow notation

From OeisWiki
(Redirected from Knuth's up-arrow notation)
Jump to: navigation, search


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

with

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

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

where
log  p
is the number of iterations of the natural logarithm required such that
log  p   ≤   e
.

Now, if we have

then

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

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

0th iteration
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
3rd iteration
4th iteration
5th iteration
6th iteration
7th iteration
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. HyperoperationWikipedia.org.
  2. Grzegorczyk hierarchyWikipedia.org.
  3. 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 := ω  +  ω
    .

External links