TOPICS
Search

Folding Function


A folding function is a function that maps the integers Z={...,-3,-2,-1,0,1,2,3,...} onto the nonnegative integers Z^*={0,1,2,3,...}. This type of function arises naturally in situations where it is desirable to remove the sign of an integer (for example, to show that |Z|=|Z^*|=aleph_0, or when encoding signed integers using a technique that works only for nonnegative integers (for example, in data compression).

The usual function folding function f is given by

 f(n)={2n   if n>=0; 2|n|-1   otherwise,
(1)

with inverse

 f^(-1)(n)={-1/2(i+1)   if i=1 (mod 2); 1/2i   otherwise.
(2)
0-11-22-33-44-55-66-77-8...
^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v...
0123456789101112131415...

f(n) computes the mapping shown above.

Another variant may be defined by

 g(n)={2n-1   if n>0; 2|n|   if n<=0,
(3)

with inverse

 g^(-1)(n)={1/2(i+1)   if i=1 (mod 2); -1/2i   otherwise.
(4)
01-12-23-34-45-56-67-78...
^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v...
0123456789101112131415...

g(n) computes the mapping shown above.


See also

Pairing Function

This entry contributed by Steven Pigeon

Explore with Wolfram|Alpha

Cite this as:

Pigeon, Steven. "Folding Function." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/FoldingFunction.html

Subject classifications