Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindNestedTransientRepeat

Source Notebook

Decompose a nested iteration into its transient and repeating parts

Contributed by: Bradley Klee

ResourceFunction["FindNestedTransientRepeat"][fun,init]

returns a pair of lists {transient,repeat} whenever nested evaluation of fun beginning at init produces a transient part followed by a repeat part satisfying the closure constraint fun[Last[repeat]]==First[repeat].

ResourceFunction["FindNestedTransientRepeat"][fun,init,n]

for an atypical function fun, requires repeat to occur successively at least n times.

ResourceFunction["FindNestedTransientRepeat"][fun,init,n,m]

terminates after at most m steps.

Details

The default value n=1 assumes a typical use case where x=y implies that fun[x]=fun[y], thus n=1 already guarantees periodic repeating. It is possible to define atypical functions where n=1 does not guarantee periodic repeating, so the parameter n can be set to values greater than one.
ResourceFunction["FindNestedTransientRepeat"] accepts two options "ValuesEncoding" and "ValuesDecoding", with default values Identity and Automatic. Either Option should be a Function or a Symbol.
For "ValuesEncoding"→encode and "ValuesDecoding"→decode, when iterating evaluation of fun around init, successive intermediary values vali are stored as encode[vali] and later returned as decode[encode[vali]]. Repeating subsequences are then searched for in the sequence of encode[vali] rather than the sequence of vali.
The default for decode, Automatic, uses extra memory and may be less efficient than setting decode explicitly.

Examples

Basic Examples (4) 

Test the Collatz conjecture for n=23:

In[1]:=
ResourceFunction["FindNestedTransientRepeat"][ Function[{x}, Piecewise[{ {x/2, EvenQ[x]}, {3 x + 1, ! EvenQ[x]}}] ], 23]
Out[1]=

Rational inputs to the tent map always end up repeating:

In[2]:=
ResourceFunction["FindNestedTransientRepeat"][ Function[(1 - 2 Abs[# - 1/2])], 13/37]
Out[2]=

Inputs with even numerator have no transient part:

In[3]:=
ResourceFunction["FindNestedTransientRepeat"][ Function[(1 - 2 Abs[# - 1/2])], 8/37]
Out[3]=

Prove the elementary CellularAutomaton Rule 30 is not reversible:

In[4]:=
Module[{res}, TrueQ[SelectFirst[Tuples[{0, 1}, 5], UnsameQ[First[ResourceFunction["FindNestedTransientRepeat"][ CellularAutomaton[30], #]], {}] &, True]]]
Out[4]=

Test Rule 240 reversibility and cycle lengths:

In[5]:=
Subtract[{0, #}, Length /@ ResourceFunction["FindNestedTransientRepeat"][ CellularAutomaton[240], RandomInteger[1, #]]] & /@ RandomInteger[{5, 100}, 5]
Out[5]=

Scope (2) 

Find repeat runs in a sequence of random integer digits:

In[6]:=
SeedRandom[0927340923]; ResourceFunction["FindNestedTransientRepeat"][ Function[{null}, RandomInteger[5]], 0, 4]
Out[3]=

But the next digit is not another 1:

In[7]:=
SeedRandom[0927340923]; Table[Function[{null}, RandomInteger[5]][0], {287}]
Out[8]=

Options (2) 

Encode and decode hash functions allow more efficient data structures:

In[9]:=
ResourceFunction["FindNestedTransientRepeat"][ CellularAutomaton[30], {1, 0, 0, 0, 1, 0, 1, 0}, "ValuesEncoding" -> (FromDigits[#, 2] &), "ValuesDecoding" -> Identity]
Out[9]=

Setting the decode function to Automatic keeps an extra dictionary in memory:

In[10]:=
ResourceFunction["FindNestedTransientRepeat"][ CellularAutomaton[30], {1, 0, 0, 0, 1, 0, 1, 0}, "ValuesEncoding" -> (FromDigits[#, 2] &), "ValuesDecoding" -> Automatic]
Out[10]=

Properties and Relations (2) 

Compare with FindTransientRepeat and NestList:

In[11]:=
FindTransientRepeat[NestList[ Function[{x}, Piecewise[{ {x/2, EvenQ[x]}, {3 x + 1, ! EvenQ[x]}}] ], 23, 50], 5]
Out[11]=

Compare again with NestList:

In[12]:=
With[{data = ResourceFunction["FindNestedTransientRepeat"][ Function[{x}, Piecewise[{ {x/2, EvenQ[x]}, {3 x + 1, ! EvenQ[x]}}] ], 23]}, SameQ[Join[First[data], Last[data], Last[data]], NestList[Function[{x}, Piecewise[{{x/2, EvenQ[x]}, {3 x + 1, ! EvenQ[x]}}]], 23, Plus[Length[data[[1]]], 2 Length[data[[2]]]] - 1 ]] ]
Out[12]=

Possible Issues (2) 

Some inputs can possibly lead to non-terminating loops:

In[13]:=
TimeConstrained[ResourceFunction["FindNestedTransientRepeat"][ Function[{x}, x + 1], 1], 5]
Out[13]=

Add a cutoff parameter for returning a purely transient result:

In[14]:=
ResourceFunction["FindNestedTransientRepeat"][ Function[{x}, x + 1], 1, 1, 10]
Out[14]=

Neat Examples (1) 

Plot the transient and repeating parts of a Rule 30 iteration:

In[15]:=
Show[ImageRotate[GraphicsColumn[ ArrayPlot[#, ImageSize -> {80, Automatic} ] & /@ ResourceFunction["FindNestedTransientRepeat"][ CellularAutomaton[30], {1, 0, 0, 0, 1, 0, 1, 0}, "ValuesEncoding" -> (FromDigits[#, 2] &), "ValuesDecoding" -> (IntegerDigits[#, 2, 8] &)]], Pi/2], ImageSize -> {500, Automatic}]
Out[15]=

Publisher

Brad Klee

Version History

  • 1.0.0 – 01 November 2022

Related Resources

Author Notes

Method suggested by TWJ.

License Information