A function (or program) which takes inputs and provides outputs can be said to have a cycle if calling the function on its own output repeatedly eventually reaches the original number. For instance, take the following function:
Input: n 1 2 3 4 5 6
Output: f(n) 5 7 1 3 4 9
If we start with n=1
, f(n)=5
, f(f(n))=f(5)=4
, f(f(f(n)))=f(4)=3
, f(f(f(f(n))))=f(3)=1
.
This is written (1 5 4 3)
. Since there are 4 unique numbers in this loop, this is a cycle of length 4.
Your challenge is to write a program or function which has cycles of every possible length. That is, there must be a cycle of length 1, of length 2, and so on.
In addition, your function/program must be from the positive integers to positive integers, and it must be bijective, meaning that there must be a exactly one input value for every possible output value, over all positive integers. To put it another way, the function/program must compute a permutaion of the positive integers.
Details: Any standard input/output system is allowed, including STDIN, STDOUT, function argument, return, etc. Standard loopholes prohibited.
You do not need to worry about the limitations of your data types - the above properties need only hold under the assumption that an int
or float
can hold any value, for instance.
There are no restrictions on the behavior of the function on inputs which are not positive integers, and those inputs/outputs will be ignored.
Scoring is code golf in bytes, shortest code wins.