NestList

The list of x, f(x), f(f(x)), ... up to n applications of f.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageNestList!↗

NestList(f, x, n)$x$ followed by every intermediate value up to $Nest(f, x, n)$, $n + 1$ entries in all.

Typed signatures

Type	Package	Applies
(function: any, x: any, n: integer) -> list<any>	combinatorics	always

Domain: Collections

Details

• See Nest for just the final value.

Examples

Basic #

live ↗

In$\mathrm{NestList}(f, x, 3)$Out$\bigl\lbrack x, f(x), f(f(x)), f(f(f(x)))\bigr\rbrack$

Powers of 2

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦2\operatorname{\_1}, 1, 5)$Out$\bigl\lbrack1, 2, 4, 8, 16, 32\bigr\rbrack$

All intermediate results, from the start through four applications

live ↗

In$\mathrm{NestList}(f, x, 4)$Out$\bigl\lbrack x, f(x), f(f(x)), f(f(f(x))), f(f(f(f(x))))\bigr\rbrack$

Iterating cosine, which converges toward $0.739\ldots$, stays symbolic here

live ↗

In$\mathrm{NestList}(\cos, 1, 10)$Out$\bigl\lbrack1, \cos(1), \cos(\cos(1)), \cos(\cos(\cos(1))), \cos(\cos(\cos(\cos(1)))), \cos(\cos(\cos(\cos(\cos(1))))), \cos(\cos(\cos(\cos(\cos(\cos(1)))))), \cos(\cos(\cos(\cos(\cos(\cos(\cos(1))))))), \cos(\cos(\cos(\cos(\cos(\cos(\cos(\cos(1)))))))), \cos(\cos(\cos(\cos(\cos(\cos(\cos(\cos(\cos(1))))))))), \cos(\cos(\cos(\cos(\cos(\cos(\cos(\cos(\cos(\cos(1))))))))))\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦(\operatorname{\_1}+1)^2, x, 3)$Out$\bigl\lbrack x, (x+1)^2, ((x+1)^2+1)^2, (((x+1)^2+1)^2+1)^2\bigr\rbrack$

Scope #

Zero steps: just the seed

live ↗

In$\mathrm{NestList}(f, x, 0)$Out$\bigl\lbrack x\bigr\rbrack$

Each root halves the exponent; the results nest

live ↗

In$\mathrm{NestList}(\mathrm{Sqrt}, 100, 4)$Out$\bigl\lbrack100, 10, \sqrt{10}, \sqrt{\sqrt{10}}, \sqrt{\sqrt{\sqrt{10}}}\bigr\rbrack$

Applications #

3 is a primitive root mod 7: its powers visit every nonzero residue

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦3\operatorname{\_1}\bmod7, 1, 6)$Out$\bigl\lbrack1, 3, 2, 6, 4, 5, 1\bigr\rbrack$

Newton iterates converging to $\sqrt{2}$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\frac{\operatorname{\_1}+\frac{2}{\operatorname{\_1}}}{2}, 1, 3)$Out$\bigl\lbrack1, \frac{3}{2}, \frac{17}{12}, \frac{577}{408}\bigr\rbrack$

Doubling gives the powers of $2$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦2\operatorname{\_1}, 1, 10)$Out$\bigl\lbrack1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1\,024\bigr\rbrack$

Counting up from zero by repeated increment

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\operatorname{\_1}+1, 0, 10)$Out$\bigl\lbrack0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\bigr\rbrack$

Repeated squaring gives $2^{2^k}$, which explodes quickly

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\operatorname{\_1}^2, 2, 6)$Out$\bigl\lbrack2, 4, 16, 256, 65\,536, 4\,294\,967\,296, 18\,446\,744\,073\,709\,551\,616\bigr\rbrack$

Newton iterates for $\sqrt2$ stay exact rationals, with digits doubling in size

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\frac{\operatorname{\_1}+\frac{2}{\operatorname{\_1}}}{2}, 1, 5)$Out$\bigl\lbrack1, \frac{3}{2}, \frac{17}{12}, \frac{577}{408}, \frac{665\,857}{470\,832}, \frac{886\,731\,088\,897}{627\,013\,566\,048}\bigr\rbrack$

The logistic map at $r=4$ from $1/3$: exact rationals whose size roughly doubles each step

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦4\operatorname{\_1}×(1-\operatorname{\_1}), \frac{1}{3}, 5)$Out$\bigl\lbrack\frac{1}{3}, \frac{8}{9}, \frac{32}{81}, \frac{6\,272}{6\,561}, \frac{7\,250\,432}{43\,046\,721}, \frac{1\,038\,154\,236\,987\,392}{1\,853\,020\,188\,851\,841}\bigr\rbrack$

A linear congruential generator mod $101$, producing a pseudo-random orbit

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦59\operatorname{\_1}\bmod101, 1, 15)$Out$\bigl\lbrack1, 59, 47, 46, 88, 41, 96, 8, 68, 73, 65, 98, 25, 61, 64, 39\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\frac{\mathrm{d}\operatorname{\_1}}{\mathrm{d}x}, x^{n}, 3)$Out$\bigl\lbrack x^{n}, nx^{n-1}, n^2x^{n-2}-nx^{n-2}, n^3x^{n-3}-3n^2x^{n-3}+2nx^{n-3}\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\mathrm{Symbol}(x), \bigl\lbrack a\bigr\rbrack, 5)$Out$\bigl\lbrack\bigl\lbrack a\bigr\rbrack, \mathrm{Symbol}(x), \mathrm{Symbol}(x), \mathrm{Symbol}(x), \mathrm{Symbol}(x), \mathrm{Symbol}(x)\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\frac{1}{\operatorname{\_1}+1}, x, 5)$Out$\bigl\lbrack x, \frac{1}{x+1}, \frac{1}{\frac{1}{x+1}+1}, \frac{1}{\frac{1}{\frac{1}{x+1}+1}+1}, \frac{1}{\frac{1}{\frac{1}{1/(x+1)+1}+1}+1}, \frac{1}{\frac{1}{\frac{1}{1/(1/(x+1)+1)+1}+1}+1}\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\text{if }\mathrm{IsEven}(\operatorname{\_1})\text{ then }\frac{\operatorname{\_1}}{2}\text{ else }\frac{3\operatorname{\_1}+1}{2}, 100, 20)$Out$\bigl\lbrack100, 50, 25, 38, 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\mathrm{Append}(\operatorname{\_1}, x), \bigl\lbrack a\bigr\rbrack, 5)$Out$\bigl\lbrack\bigl\lbrack a\bigr\rbrack, \bigl\lbrack a, x\bigr\rbrack, \bigl\lbrack a, x, x\bigr\rbrack, \bigl\lbrack a, x, x, x\bigr\rbrack, \bigl\lbrack a, x, x, x, x\bigr\rbrack, \bigl\lbrack a, x, x, x, x, x\bigr\rbrack\bigr\rbrack$

live ↗

In$\mathrm{NestList}(\mathrm{RotateLeft}, \bigl\lbrack a, b, c, d\bigr\rbrack, 4)$Out$\bigl\lbrack\bigl\lbrack a, b, c, d\bigr\rbrack, \bigl\lbrack b, c, d, a\bigr\rbrack, \bigl\lbrack c, d, a, b\bigr\rbrack, \bigl\lbrack d, a, b, c\bigr\rbrack, \bigl\lbrack a, b, c, d\bigr\rbrack\bigr\rbrack$

Properties #

Reaches the fixed point $2$ and stays there

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\lfloor\frac{\operatorname{\_1}}{2}\rfloor+1, 1\,000, 15)$Out$\bigl\lbrack1\,000, 501, 251, 126, 64, 33, 17, 9, 5, 3, 2, 2, 2, 2, 2, 2\bigr\rbrack$

Neat examples #

Power towers of increasing height

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦x^{\operatorname{\_1}}, x, 6)$Out$\bigl\lbrack x, x^{x}, x^{x^{x}}, x^{x^{x^{x}}}, x^{x^{x^{x^{x}}}}, x^{x^{x^{x^{x^{x}}}}}, x^{x^{x^{x^{x^{x^{x}}}}}}\bigr\rbrack$

$u \mapsto u^u$ blows up the expression size

live ↗

In$\mathrm{NestList}(\operatorname{\_1}↦\operatorname{\_1}^{\operatorname{\_1}}, x, 4)$Out$\bigl\lbrack x, x^{x}, (x^{x})^{x^{x}}, ((x^{x})^{x^{x}})^{(x^{x})^{x^{x}}}, (((x^{x})^{x^{x}})^{(x^{x})^{x^{x}}})^{((x^{x})^{x^{x}})^{(x^{x})^{x^{x}}}}\bigr\rbrack$

About

Examples	24
Checked against	Wolfram Language 23 agree1 differmathlib4 9 agree
Crosswalk	Wolfram Language

Implementation

mappedmathlib4packages/oracle/src/mappings.ts

The start and each of n applications, n + 1 entries. A negative or non-integer count fails to elaborate, where ours holds the call.

See also: Nest, FixedPoint