In this paper by Igor Pak, he mentions the following definition of wilfian formulas, which basically aim at characterising what amounts to a good enumeration formula, the classification goes as follows :
-$(W_1)$ There is an algorithm that computes $a_n$ in time $poly(n)$.
-$(W_2)$ There is an algorithm that computes $a_n$ in time $o(a_n)$.
I am unable to understand what definition $W_2$ means? The author only gives negative examples of $W_2$.
Can anyone give me an example fo $W_2$ ?
If you have a way of iterating over all the things you want to enumerate in order in constant time then you have a $W_2$ algorithm.
One possible example of this is to enumerate all the values that can be reached from a starting value $S$ in the collatz sequence, for example (where we restrict ourselves to values $S$ such that the collatz sequence cycles).